HashMap夺命连环18问，你扛得住吗？

说说你对hash的理解？

hash的基本概念就是把任意长度的输入通过一个hash算法之后映射成固定长度的输出。

hash算法会存在什么问题？

在程序中可能碰到两个值经过hash算法之后算出同样的hash值，也就是会发生hash冲突。

hash冲突能避免吗？

不能，只能尽量避免。举个例子，10个苹果放到9个盒子里，肯定有一个盒子里的苹果数大于1。

你认为好的hash算法，应该考虑的点有哪些？

1. 效率肯定得高，要做到长文本也能高效计算出hash值；
2. hash值不能让它逆推出原文；
3. 两次输入，只要有一点不同，它也得保证这个hash值是不同的；
4. 尽可能分散。

HashMap的数据结构是什么？

哈希表结构（也叫散列表）实现，即数组+链表。在JDK1.8中加入了红黑树。以JDK1.8为例，它的每个数据单元都是一个Node对象，对象中有key，value，next及hash字段。

你知道HashMap中hash的实现吗？为什么要这样实现？

JDK1.8中，是通过hashCode的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效和质量来考虑的，因为HashMap内部散列表，大多数场景下，不会特别大。也就是说table.length - 1得到的二进制数，实际有效位很有限，一般都在低16位以内，这样的话高16位就等于完全浪费了。减少系统开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。

那你说一下JDK1.7到JDK1.8HashMap发生了什么变化？

1. 在JDK1.8中，Entry被Node替代（换了个马甲）；
2. 1.7中底层是数组+链表，1.8中底层是数组+链表+红黑树，加红黑树的目的是提高HashMap插入和查询整体效率；
3. 1.7中链表插入使用的是头插法，1.8中链表插入使用的是尾插法，因为1.8中插入key和value时需要判断链表元素个数，所以需要遍历链表统计链表元素个数，所以正好就直接使用尾插法；
4. 1.7中哈希算法比较复杂，存在各种右移与异或运算，1.8中进行了简化，因为负载的哈希算法的目的就是提高散列性，来提高HashMap的整体效率，而1.8中新增了红黑树，所以可以适当的简化哈希算法，节省CPU资源。

散列表是什么时候创建的？new HashMap()的时候吗？

不是。散列表是懒加载机制，只有第一次put数据的时候，它才创建。

详细说一下HashMap的Put方法吧

1. 根据key通过哈希算法与运算得出数组下标；
2. 如果数组下标位置元素为空，则将key和value封装为Entry对象(JDK1.7中是Entry对象，JDK1.8中是Node对象)并放入该位置；
3. 如果数组下标位置元素不为空，则要分情况讨论

• 如果是JDK1.7，则先判断是否需要扩容，如果要扩容就进行扩容，如果不用扩容就生成Entry对象，并使用头插法添加到当前位置的链表中
• 如果是JDK1.8，则会先判断当前位置上的Node的类型，看是红黑树Node，还是链表Node
  • 如果是红黑树Node，则将key和value封装为一个红黑树节点并添加到红黑树中去，在这个过程中会判断红黑树中是否存在当前key，如果存在则更新value
  • 如果此位置上的Node对象是链表节点，则将key和value封装为一个链表Node并通过尾插法插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会判断是否存在当前key，如果存在则更新value，当遍历完链表后，将新链表Node插入到链表中，插入到链表后，会看当前链表的节点个数，如果超过了8，并且数组长度超过了64，那么则会将该链表转成红黑树
  • 将key和value封装为Node插入到链表或红黑树中后，再判断是否需要进行扩容，如果需要就扩容，如果不需要就结束put方法

HashMap默认的负载因子是多少？负载因子有什么用？

默认的负载因子是0.75。负载因子的作用是用于计算扩容阈值。比如使用无参构造方法创建的HashMap对象，它默认情况下扩容阈值就是16 * 0.75=12。

HashMap什么时候会扩容？

当HashMap中的元素个数超过阈值threshold时，就会进行扩容。
阈值(threshold) = 数组大小(capacity) * 负载因子(loadFactor)

触发扩容后，会扩容多大，算法是什么？

HashMap扩容时会扩容为原数组的2倍。扩容的算法是根据上一次tablesize位移运算得到的（左移1位运算），比如默认tablesize是16，那么扩容后的大小为16 << 1 = 32。

扩容算法为什么采用位移运算，而不直接乘2？

提高性能。因为cpu不支持乘法运算，所有的乘法运算最终都会在指令层面转换为加法，效率低。

扩容是如何实现的？

HashMap扩容的过程是比较复杂的，大致过程如下：

扩容需要重新分配一个新数组，新数组是老数组的2倍，然后遍历整个老数组，把所有的元素挨个重新hash分配到新结构中去。

链表转化为红黑树需要达到什么条件？

两个条件：

1. 链表长度达到8；
2. 当前散列表长度已经达到64。

如果散列表长度不到64，就算slot内部链表长度到了8，它也不会链转树，它仅仅会发生一次resize，散列表扩容。

JDK1.8 HashMap为什么引入红黑树？解决什么问题？

主要就是解决hash冲突导致链化严重的问题（链表过深）。在JDK1.7及之前版本，当slot链化非常严重的时候，严重影响get查询效率。本身散列表最理想的查询效率为O(1)，但是链化特别严重后，就会导致查询退化为O(n)。

拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线型结构（这就跟原来使用的链表一样了），遍历查找会非常慢。

而红黑树在插入新数据后可能需要通过左旋、右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题。红黑树是一种近似平衡的二叉查找树，他并非绝对平衡，但是可以保证任何一个节点的左右子树的高度不会超过二者中较低的那个的一倍。

所以树化有一个前提是长度大于8，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

红黑树有什么特点？

1. 每个节点非红即黑；
2. 根节点必须是黑色。叶子节点必须是黑色空节点；
3. 红色节点不能连续；
4. 从叶节点到根节点的路径上，每条路径都含有相同个数的黑色节点。

---

你以为HashMap的问题就这些了吗？不，这只是入门水平。还有很多疑问，比如：

• 为什么HashMap数组长度必须是2的n次幂？

• 扩容机制的细节是什么样的？

• HashMap死循环是什么？

• 红黑树写入操作，如何找到父节点？

• 高低位异或是什么？什么是高位链与低位链？

• HashMap为什么线程不安全？

关注我的公众号，带你玩转Java面试。