JAVA面试HashMap的扩容机制

提示：文章先作为初版，等后续时间充足后，补充更深的内容

---

HashMap的扩容机制

一、1.7版本

1.先生成新数组
2．遍历老数组中的每个位置上的链表上的每个元素
3．取每个元素的key，并基于新数组长度，计算出每个元素在新数组中的下标
4．将元素添加到新数组中去
5．所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

二、1.8版本

1．先生成新数组
2.遍历老数组中的每个位置上的链表或红黑树
3．如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去
4．如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标位置
a.统计每个下标位置的元素个数
b.如果该位置下的元素个数超过了8，则生成一个新的红黑树，并将根节点的添加到新数组的对应位置
c.如果该位置下的元素个数没有超过8，那么则生成一个链表，并将链表的头节点添加到新数组的对应位置
5．所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

三、插入方式

在JDK 1.7和JDK 1.8中，HashMap的扩容机制有一些改变。

在JDK 1.7中，HashMap的扩容机制是“头插法”。也就是说，在链表中新的元素会插入到链表的头部，而不是尾部。这样做的目的是为了避免在扩容时链表元素的顺序反转。但是，这种方式在多线程环境下可能会出现死循环的问题。

在JDK 1.8中，HashMap的扩容机制改为了“尾插法”。也就是说，在链表中新的元素会插入到链表的尾部。这样做可以保持链表元素的相对顺序不变，同时也避免了死循环的问题。此外，在JDK 1.8中，当链表的长度超过一定阈值时，链表会自动转换成红黑树，以提高查找的效率。

除了扩容机制的改变，JDK 1.8中的HashMap还引入了一些其他的优化措施，比如“链表 红黑树”混合存储、负载因子的调整等，都使得HashMap在性能上得到了更好的提升。

三、底层变化

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

---

这篇好文章是转载于：学新通技术网