HashMap的扩容机制以及jdk1.8之后的优化
HashMap的扩容机制以及jdk1.8之后的优化
HashMap是Java中常用的数据结构，其扩容机制和性能优化对于理解其内部原理至关重要。本文将详细介绍HashMap的扩容时机、扩容因子的选择依据，以及JDK 1.8版本中引入的重要优化措施。
什么时候扩容？扩容因子为什么是0.75呢？
为了减少哈希冲突发⽣的概率，当当前HashMap的元素个数达到⼀个临界值的时候，就会触发扩容， 把所有元素rehash之后再放在扩容后的容器中，这是⼀个相当耗时的操作。
⽽这个 临界值threshold 就是由加载因⼦和当前容器的容量大小来确定的，假如采⽤默认的构造⽅法：
临界值（threshold ）= 默认容量（DEFAULT_INITIAL_CAPACITY） * 默认扩容因⼦ （DEFAULT_LOAD_FACTOR）
为什么选择0.75为扩容因子呢?
简单来说，这是对 空间成本和 时间成本平衡的考虑。我们都知道，HashMap的散列构造⽅式是Hash取余，负载因⼦决定元素个数达到多少时候扩容。
假如我们设的⽐较⼤，元素⽐较多，空位⽐较少的时候才扩容，那么发⽣哈希冲突的概率就增加了，查找的时间成本就增加了。我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发⽣哈希碰撞的概率就降低了，查找 时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。
扩容机制的具体怎么操作呢？
HashMap是基于数组+链表和红⿊树实现的，但用于存放key值的桶数组的长度是固定的，由初始化参 数确定。那么，随着数据的插⼊数量增加以及负载因⼦的作用下，就需要扩容来存放更多的数据。⽽扩容中有一个非常重要的点，就是jdk1.8中的优化操作，可以不需要再重新计算每⼀个元素的哈希值。
因为HashMap的初始容量是2的次幂，扩容之后的长度是原来的二倍，新的容量也是2的次幂，所以， 元素，要么在原位置，要么在原位置再移动2的次幂。
看下这张图，n为table的长度，通过n-1和key进行与操作确定索引。
图a表⽰扩容前的key1和key2两种key确定索引的位置，图b表⽰扩 容后key1和key2两种key确定索引位置
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在⾼位多1bit(红⾊)，因此新的index 就会发生这样的变化：
所以在扩容时，只需要看原来的hash值新增的那⼀位是0还是1就⾏了，是0的话索引没变，是1的化变成原索引 +oldCap。
jdk1.8对HashMap主要做了哪些优化呢？为什么？
- 数据结构：数组 + 链表改成了数组 + 链表或红⿊树。
原因：发生 hash 冲突，元素会存⼊链表，链表过长转为红⿊树，将时间复杂度由O(n)降为O(logn)。
- 链表插入方式：链表的插⼊⽅式从头插法改成了尾插法
简单说就是插⼊时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节 点的后继节点，1.8 遍历链表，将元素放置到链表的最后。
原因：因为 1.7 头插法扩容时，头插法会使链表发⽣反转，多线程环境下会产⽣环。
- 扩容rehash：扩容的时候 1.7 需要对原数组中的元素进⾏重新 hash 定位在新数组的位置，1.8 采⽤更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
原因：提高扩容的效率，更快地扩容。
扩容时机：在插⼊时，1.7 先判断是否需要扩容，再插⼊，1.8 先进⾏插⼊，插⼊完成再判断是 否需要扩容。
散列函数：1.7 做了四次移位和四次异或，jdk1.8只做⼀次。
原因：做 4 次的话，边际效用也不大，改为⼀次，提升效率