1. 哈希表(Hash table)
也称为 哈希表 。是字典的一种抽象。比如说你要查一个字,通过这个字的拼音首字母,找到这个字的页码,然后翻到那页找就行了。这种方法直接把查找 时间复杂度 降到了常数。但是要牺牲一定的计算索引的时间。计算索引的那个函数称为 哈希函数 ( 散列函数)。
1.1. 常见的三种哈希结构: 数组; set(集合); map(映射);
1.2. 原理
通过哈希函数把传入的key映射到符号表的索引上,可以使查找插入 时间复杂度 达到常数级别。
1.3. 哈希函数
1 2 3 |
相等的 key 产生相等的 哈希值 计算简单方便 哈希值 均匀分布。(若过度集中,则容易使效率降低到 o(n)) |
2. Hash冲突
如果两个不同的 key 算出了同一个索引,此时就要用到一定的方法来解决哈希冲突。
哈希碰撞处理有多个key映射到相同索引上时的情景,处理碰撞的普遍方式是 拉链法 和 线性探测法。
用map确实可以,但使用map的空间消耗要比数组大一些,因为map要维护红黑树或者符号表,而且还要做哈希函数的运算。所以数组更加简单直接有效!
3. 拉链法
拉链法 的实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。这样的好处是,不怕冲突多;缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。拉链法要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。
3.1. 实现步骤
- 得到一个 key
- 计算 key 的 hashValue
- 根据 hashValue 值定位到 data[hashValue] 。( data[hashValue] 是一条链表)
- 若 data[hashValue] 为空则直接插入
- 不然则添加到链表末尾
3.2. 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class SeparateChainingHashST<Key,Value> { //这里的M需要根据实际情况调整 public SeparateChainingHashST(int M) { this.M = M; st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M]; for (int i=0;i<M;i++){ st[i]=new SequentialSearchST<Key,Value>(); } } private int hash(Key key){ return (key.hashCode() & 0x7fffffff) % M; } public void put(Key k,Value v){ int hashValue = hash(k); st[hashValue].put(k,v); } public Value get(Key k){ int hashValue = hash(k); return st[hashValue].get(k); } } |
4. 线性探测法
线性探测 直接使用数组来存储数据。可以想象成一个停车问题。若当前车位已经有车,则你就继续往前开,直到找到下一个为空的车位
使用线性探测法,一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。
4.1. 实现步骤
- 得到 key
- 计算得 hashValue
- 若不冲突,则直接填入数组
- 若冲突,则使 hashValue++ ,也就是往后找,直到找到第一个 data[hashValue] 为空的情况,则填入。若到了尾部可循环到前面。
4.2. 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public class LinearProbingHashST<Key,Value> { public LinearProbingHashST(int cap) { keys = (Key[]) new Object[cap]; values = (Value[]) new Object[cap]; M = cap; } private int hash(Key key){ return (key.hashCode() & 0x7fffffff) % M; } public void put(Key key,Value value){ //若当前数据含量超过了总容量的一半,则重新调整容量 if(N>=M/2) resize(2*M); int hashValue = hash(key); if (values[hashValue]==null){ keys[hashValue] = key; values[hashValue] = value; N++; } else if(keys[hashValue].equals(key)){ values[hashValue]=value; } else{ while (values[hashValue] != null){ hashValue = (hashValue+1)%M; } keys[hashValue] = key; values[hashValue] = value; N++; } } public Value get(Key key){ int hashValue = hash(key); if (keys[hashValue]!=null&&!keys[hashValue].equals(key)){ while (keys[hashValue]!=null &&keys[hashValue]!=key){ hashValue = (hashValue+1)%M; } } return values[hashValue]; } } |
赞赏
微信赞赏
支付宝赞赏