🍳写在前边

• HashMap属于比较常用的数据结构了，面试过程中也经常会被问到，本篇就知识点，展开问答式分析，重点聊聊hash冲突、扩容死链、容量为2的n次方、1.7和1.8之间的区别等问题~

🍔如何解决Hash冲突问题

扩容

条件

1. 链表长度超过8
2. 元素个数超过数组个数的75%

树化规则

条件

1. 链表长度超过8
2. 此时看看数组长度是否超过64，超过就进行树化，否则只是单纯扩容

🍔为什么需要树化

其实一般正常的元素，都是不会超过阈值的，只有插入一堆重复的元素，hash值一样，才可能达到阈值，这个简称Dos攻击 而元素一旦多起来，链表查找的效率就远不及红黑树了

🤷‍♂️树化一定更好吗？

不是的，维护红黑树需要占用比链表更多的空间，而且当链表长度足够短的时候，链表查找的效率反而比红黑树更高？？

为什么选择0.75和8

• hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

退化规则

扩容的时候链表长度<=6

remove节点的时候

root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表（看的是移除之前的情况）

🍔为什么需要二次哈希

先获得key的hashCode的值 h，然后 h 和 h右移16位 做异或运算。 实质上是把一个数的末x位低16位与他的高16位做异或运算，因为在前面 (n - 1) & hash 的计算中，hash变量只有末x位会参与到运算。使高16位也参与到hash的运算能减少冲突

具体原因

因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为 -2147483648~2147483647，加起来大概 40 亿的映射空间。

一个 40 亿长度的数组，内存是放不下的。假如 HashMap 数组的初始大小才 16，那么做 & 运算，就只取到后xx 位【因为大小差距太大了】，前边高位都没有参与进来

就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就更难搞了。

这时候 扰动函数 的价值就体现出来了，看一下扰动函数的示意图：

右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来

🍔为什么要用2的n次方

为了方便 & 操作

只有2的n次方，去-1，才能用 & 替代 %

🎈为了方便扩容

扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 否则新位置 = 旧位置 + oldCap （oldCap：原始的容量）

因为HashMap的初始容量是2的次幂，扩容之后的长度是原来的二倍，新的容量也是2的次幂，所以，元素，要么在原位置，要么在原位置再移动2的次幂。

看下这张图，n为table的长度 图a表示扩容前的key1和key2两种key确定索引的位置 图b表示扩容后key1和key2两种key确定索引位置。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

所以在扩容时，只需要看原来的hash值新增的那一位是0还是1就行了【直接 hash & oldCap，就能知道是0还是1了】 是0的话索引没变，是1的话就变成原索引+oldCap

🍔不用2的n次方可以吗

可以的，因为2的n次方也会有缺陷，比如给定的值全是偶数，无论如何hash之后取模，都是偶数，分布就不均匀

此时如果用质数作为容量的话，就会分布得比较均匀

注意

二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash

容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

🍔并发扩容丢失数据问题

主要是第一个节点才会吧？因为第一个是new Node出来的

🍔jdk1.7 并发扩容死链问题

jdk1.7中，采用的是头插法，用一个e指针表示当前要扩容的节点，next表示接下来要扩容的节点，一直头插e更新e为next，直到e为null

假设现在有两个线程1和2，要扩容一个Map

1. 线程1的局部变量e，指向了a节点，next指向b节点
2. 线程2的局部变量也是如此，此时线程2先进行扩容，由于是头插法，最终结果变成了 b->a
3. 但此时来到线程1先进行，局部变量不会受改变，e还是指向a，next还是b，所以把a头插，并且更新e为next，也就变成了b
4. 线程1继续头插b，没问题，结果变成了[b->a]，看起来是没问题了，但是接下来判断e还没有next：
5. 发现e的next是a，又要继续头插a，插完a之后，发现a的next又是b，寄了这下，无限循环了

🍔1.7和1.8有什么不同

1.7是 数组+链表

1.8是 数组+链表【超过阈值会变成红黑树】

🍔jdk1.8对HashMap主要做了哪些优化呢？为什么？

jdk1.8 的HashMap主要有五点优化：

1. 数据结构：数组 + 链表改成了数组 + 链表或红黑树

   原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)

2. 链表插入方式：链表的插入方式从头插法改成了尾插法

   简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。

   原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。

3. 扩容rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。

   原因：提高扩容的效率，更快地扩容。

4. 扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

5. 散列函数：1.7 做了四次移位和四次异或，jdk1.8只做一次。

   原因：做 4 次的话，边际效用也不大，改为一次，提升效率。