HashMap解决Hash冲突

什么是哈希冲突

当两个个不同的值，根据同一散列函数计算出相同的散列值现象，称为哈希冲突

HashMap的数据结构

HashMap是由数组+链表组成的，jdk1.8后加入了红黑树

​ 使用链地址法来解决哈希冲突，这样我们可以将具有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但是相比hashCode返回的int类型，HashMap初始的容量大小为DEFAULT_INITIAL_CAPACITY = 1 << 4（即
2的四次方16）要远小于int类型的范围，所以，如果知识单纯的使用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以需要将hashCode做一定的优化hash()函数。

​ 因为如果使用hashCode来取余，那么相当于参与运算的只有hashCode的低位，高位没有起到任何作用，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均，我们把这样的操作称为扰动。在JDK1.8中的hash函数如下

static final int hashCode(Object key){
    int h;
    //与自己右移16位进行异或运算（高低位异或）
    return (key==null)? 0 : (h==key.hashCode()) ^ (h>>>16)//
}

​ 这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行
了1次位运算和1次异或运算（2次扰动）；

jdk1.8新增红黑树

​ 通过上面的链地址法（使用散列表）和扰(img)动函数我们成功让我们的数据分布更平均，哈希碰撞减
少，但是当我们的HashMap中存在大量数据时，加入我们某个 bucket下对应的链表有n个元素，那么遍
历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使
得遍历复杂度降低至O(logn)；

总结

简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：

1. 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
2. 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快

一、简述

通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。

二、拉链法

基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

1️⃣HashMap、HashSet 其实都是采用的拉链法来解决哈希冲突的，就是在每个位桶实现的时候，采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作：

1. 插入操作：在发生哈希冲突的时候，输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构，链表或者红黑树)中去的时候，先检查待插入元素 x 是否出现在表中，很明显，这个查找所用的次数不会超过装载因子(n/m：n 为输入域的关键字个数，m 为位桶的数目)，它是个常数，所以插入操作的最坏时间复杂度为 O(1) 的。

2. 查询操作：和插入操作一样，在发生哈希冲突的时候，去检索的时间复杂度不会超过装载因子，也就是检索数据的时间复杂度也是 O(1) 的。

3. 删除操作：如果在拉链法中想要使用链表这种数据结构来实现位桶，那么这个链表一定是双向链表，因为在删除一个元素 x 的时候，需要更改 x 的前驱元素的 next 指针的属性，把 x 从链表中删除。这个操作的时间复杂度也是 O(1) 的。

2️⃣与开放定址法相比，拉链法有如下几个优点：

1. 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短。
2. 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况。
3. 开放定址法为减少冲突，要求装填因子 α 较小，故当结点规模较大时会浪费很多空间。而拉链法中可取 α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间。
4. 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

3️⃣拉链法的缺点

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

三、开放定址法

开放地址法有个非常关键的特征，就是所有输入的元素全部存放在哈希表里，换句话说，位桶的实现是不需要任何的链表来实现的，也就是这个哈希表的装载因子不会超过 1。它的实现是在插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法(探查序列)，去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。

基本思想是：当关键字 key 的哈希地址 p=H(key) 出现冲突时，以 p 为基础，产生另一个哈希地址 p1，如果 p1 仍然冲突，再以 p 为基础，产生另一个哈希地址 p2，…直到找出一个不冲突的哈希地址 pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key) +di)% m i=1，2，…，n。其中 H(key) 为哈希函数，m 为表长，di 称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

1️⃣线性探查再散列

特点：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

使用例子：ThreadLocal 里面的ThreadLocalMap

2️⃣二次探查再散列

特点：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

3️⃣伪随机探测再散列di=伪随机数序列
具体实现时，应建立一个伪随机数发生器，如 i=(i+p)%m，生成一个位随机序列，并给定一个随机数做起点，每次去加上这个伪随机数++就可以了。

4️⃣示例：

已知哈希表长度 m=11，哈希函数为：H(key)=key%11，则 H(47)=3，H(26)=4，H(60)=5，假设下一个关键字为 69，则 H(69)=3，与 47 冲突。

如果用线性探测再散列处理冲突，下一个哈希地址为 H1=(3+1)%11=4，仍然冲突。再找下一个哈希地址为 H2=(3+2)%11=5，还是冲突。继续找下一个哈希地址为 H3=(3+3)%11=6，此时不再冲突，将 69 填入 5 号单元。

如果用二次探测再散列处理冲突，下一个哈希地址为 H1=(3+1)%11=4，仍然冲突，再找下一个哈希地址为 H2=(3-1)%11=2，此时不再冲突，将 69 填入 2 号单元。

如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，………则下一个哈希地址为 H1=(3+2)%11=5，仍然冲突，再找下一个哈希地址为 H2=(3+5)%11=8，此时不再冲突，将 69 填入 8 号单元。

四、再散列法

就是在使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置。这种方法是同时构造多个不同的哈希函数：Hi=RH1(key) i=1，2，…，k。当哈希地址 Hi 发生冲突时，再计算Hi=RH2(key)……直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

五、建立公共溢出区

基本思想：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

哈希冲突，指的是当关键字集合很大时，关键字值不同的元素可能胡映像到哈希表的同一个地址。

即k1!=k2,但H（k1）=H(k2),这种现象就是哈希冲突。

那如何解决哈希冲突？

1.线性探测法

如下图，元素 15 已经占据了下标为 2 的位置，元素 2 本身也应该占据下标为 2 的位置，这时遇到哈希冲突，它就往下一个地址寻找空位。
如果遇到冲突，就往下一个地址寻找空位。新地址 = 原始位置+i(i是查找次数)

如：数据关键字：15 2 38 28 4 12   数组大小：13   哈希函数 下标=关键字 mod 13

2.平方探测法

如果遇到冲突，新地址 = 原始位置+i^2(i是查找次数)

如：数据关键字：15 2 28 19 10  数组大小：13   哈希函数 下标=关键字 mod 13

3.双哈希法

要设置第二个哈希函数,如: hash2 (key)=R- (key mod R)

如果遇到冲突.新位置=原始位置+ i*hash2