哈希表
介绍
像线性数据结构在查找的时候,⼀般都是使⽤= 或者!= ,在折半查找或者其他范围查询的时候,可能会使⽤< 和> ,理想的时候,我们肯定希望不经过任何的⽐较,直接能定位到某个位置(存储位置),这种在数组中,可以通过索引取得元素。那么,如果我们将需要存储的数据和数组的索引对应起来,并且是⼀对⼀的关系,那不就可以很快定位到元素的位置了么?
只要通过函数f(k) 就能找到k 对应的位置,这个函数f(k) 就是hash 函数。它表示的是⼀种映射关系,但是对不同的值,可能会映射到同⼀个值(同⼀个hash 地址),也就是f(k1) = f(k2) ,这种现象我们称之为冲突或者碰撞。
hash 表定义如下:散列表(Hash table,也叫哈希表),是根据键(Key)⽽直接访问在内存储存位置的数据结构。也就是说,它通过计算⼀个关于键值的函数,将所需查询的数据映射到表中⼀个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

⼀般常⽤的hash 函数有:
- 直接定址法:取出关键字或者关键字的某个线性函数的值为哈希函数,⽐如H(key) = key 或者H(key) = a * key + b
- 数字分析法:对于可能出现的数值全部了解,取关键字的若⼲数位组成哈希地址
- 平⽅取中法:取关键字平⽅后的中间⼏位作为哈希地址
- 折叠法:将关键字分割成为位数相同的⼏部分(最后⼀部分的位数可以不同),取这⼏部分的叠加和(舍去进位),作为哈希地址。
- 除留余数法:取关键字被某个不⼤于散列表表⻓m 的数p 除后所得的余数为散列地址。即h ash(k)=k mod p , p< =m 。不仅可以对关键字直接取模,也可在折叠法、平⽅取中法等运算之后取模。对p 的选择很重要,⼀般取素数或m ,若p 选择不好,容易产⽣冲突。
- 随机数法:取关键字的随机函数值作为它的哈希地址。
但是这些⽅法,都⽆法避免哈希冲突,只能有意识的减少。那处理hash 冲突,⼀般有哪些⽅法呢?
解决哈希冲突的三种方法
拉链法、开放地址法、再散列法
拉链法
HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,采用链表的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)

但是如果hash 冲突⽐较严重,链表会⽐较⻓,查询的时候,需要遍历后⾯的链表,因此JDK 优化了⼀版,链表的⻓度超过阈值的时候,会变成红⿊树,红⿊树有⼀定的规则去平衡⼦树,避免退化成为链表,影响查询效率。

但是你肯定会想到,如果数组太⼩了,放了⽐较多数据了,怎么办?再放冲突的概率会越来越⾼,其实这个时候会触发⼀个扩容机制,将数组扩容成为 2 倍⼤⼩,重新hash 以前的数据,哈希到不同的数组中。
hash 表的优点是查找速度快,但是如果不断触发重新 hash , 响应速度也会变慢。同时,如果希望范围查询, hash 表不是好的选择。
拉链法的装载因子为n/m(n为输入域的关键字个数,m为位桶的数目)
开放地址法
所谓开放地址法就是发生冲突时在散列表(也就是数组里)里去寻找合适的位置存取对应的元素,就是所有输入的元素全部存放在哈希表里。也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。
它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。
探查序列的方法:
线性探查
平方探测
伪随机探测
线性探查
di =1,2,3,…,m-1;这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

(使用例子:ThreadLocal里面的ThreadLocalMap中的set方法)
private void set(ThreadLocal<?> key, Object value) {
// We don't use a fast path as with get() because it is at
// least as common to use set() to create new entries as
// it is to replace existing ones, in which case, a fast
// path would fail more often than not.
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);
//线性探测的关键代码
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
ThreadLocal<?> k = e.get();
if (k == key) {
e.value = value;
return;
}
if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
}
tab[i] = new Entry(key, value);
int sz = ++size;
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}
但是这样会有一个问题,就是随着键值对的增多,会在哈希表里形成连续的键值对。当插入元素时,任意一个落入这个区间的元素都要一直探测到区间末尾,并且最终将自己加入到这个区间内。这样就会导致落在区间内的关键字Key要进行多次探测才能找到合适的位置,并且还会继续增大这个连续区间,使探测时间变得更长,这样的现象被称为“一次聚集(primary clustering)”。


平方探测
在探测时不一个挨着一个地向后探测,可以跳跃着探测,这样就避免了一次聚集。
di=12,-12,22,-22,…,k2,-k2;这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。虽然平方探测法解决了线性探测法的一次聚集,但是它也有一个小问题,就是关键字key散列到同一位置后探测时的路径是一样的。这样对于许多落在同一位置的关键字而言,越是后面插入的元素,探测的时间就越长。


这种现象被称作“二次聚集(secondary clustering)”,其实这个在线性探测法里也有。
伪随机探测
di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。
再散列法
再散列法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次散列,直至不发生冲突位置
缺点:每次冲突都要重新散列,计算时间增加。一般不用这种方式