深入理解HashMap扩容机制与Rehash细节原理

文
章
目
录

• 一、HashMap扩容机制的基本概念
• 二、JDK 1.7中HashMap的扩容与rehash
• （一）扩容过程
• （二）rehash细节
• （三）存在的问题：链表逆序与死循环
• 三、JDK 1.8中HashMap的扩容与rehash
• （一）扩容过程
• （二）rehash细节
• （三）优势
• 四、JDK 1.7与JDK 1.8的对比
• 五、总结

HashMap是一个极为常用的数据结构，主要用于存储键值对。它的底层实现融合了数组和链表（JDK 1.8之后还引入了红黑树）。当HashMap中的元素数量逐渐增多时，为了保证其性能，就需要进行扩容操作。今天，咱们就来深入探讨一下HashMap的扩容机制以及其中rehash的细节，同时对比JDK 1.7和JDK 1.8在这方面的不同实现。

一、HashMap扩容机制的基本概念

HashMap的容量指的是其底层数组的大小，默认初始值为16。在HashMap中有一个负载因子，默认值是0.75。当HashMap中的元素数量超过阈值（阈值 = 容量 × 负载因子）时，就会触发扩容机制。简单来说，扩容就是将数组的容量翻倍，比如从16扩大到32，并且要把原有的所有元素重新分配到新数组中，这个重新分配元素的过程就叫做rehash。

一般来说，扩容主要包含下面几个核心步骤：

1. 创建新数组：新数组的大小是旧数组的两倍。
2. rehash操作：重新计算旧数组中每个元素的哈希值，根据新的哈希值确定其在新数组中的位置。
3. 数据转移：把旧数组中的链表（或者红黑树，JDK 1.8引入）迁移到新数组中。

二、JDK 1.7中HashMap的扩容与rehash

在JDK 1.7版本中，HashMap的实现相对比较基础，底层仅仅使用了数组加链表的结构。

（一）扩容过程

当执行put操作时，如果元素数量超过了阈值，HashMap就会调用resize()方法进行扩容。在这个方法里，会创建一个大小为旧数组2倍的新数组，然后调用transfer()方法，将旧数组中的元素逐个转移到新数组中。

（二）rehash细节

JDK 1.7在rehash时采用的是头插法，具体步骤如下：

1. 针对每个键的哈希值，与新数组长度减1（newCapacity – 1）进行位与运算，以此来计算元素在新数组中的位置，计算公式为：index = hash & (newCapacity - 1) 。
2. 从旧链表中逐个取出节点，按照计算出的新位置，将其插入到新数组对应的桶中。这里使用的头插法，就是把新节点直接插入到链表的头部，原来的链表接在新节点后面。

（三）存在的问题：链表逆序与死循环

这种头插法虽然简单，但会带来一些问题。一方面，转移后链表的顺序会和原来相反。比如说，原来的链表顺序是A -> B -> C，经过转移后就变成了C -> B -> A。另一方面，在多线程环境下，头插法还存在严重的隐患。当多个线程同时进行扩容操作时，有可能会导致链表形成环。例如，线程1在扩容到一半的时候，线程2也开始进行扩容，这就可能使节点之间相互指向，最终形成死循环。这也是JDK 1.7中HashMap不是线程安全的一个典型问题。

三、JDK 1.8中HashMap的扩容与rehash

JDK 1.8对HashMap进行了优化升级，引入了红黑树（当链表长度超过8时，链表会转换为红黑树），并且在扩容和rehash的实现方式上也做了改进。

（一）扩容过程

JDK 1.8中HashMap的扩容同样是通过resize()方法来完成的。在这个方法里，会创建一个大小为旧数组2倍的新数组，然后根据元素是链表还是红黑树，分别采用不同的逻辑来处理数据转移。

（二）rehash细节

JDK 1.8摒弃了JDK 1.7中的头插法，改为使用尾插法，并且利用了容量翻倍的特性来优化计算过程。具体如下：

1. 位置计算优化：由于新数组的容量是旧数组的2倍，所以对于旧数组中的每个键，它在新数组中的位置其实只有两种可能：要么和在旧数组中的位置相同，要么是旧位置加上旧数组的容量（oldCap）。判断的方法是检查键的hash值与oldCap的位与结果（hash & oldCap） ：如果结果为0，那么新位置就和旧位置一样；如果结果为oldCap，新位置则是旧位置加上oldCap。
2. 链表拆分：在JDK 1.8中，会把旧链表拆分成两条链表，分别是低位链表（loHead）和高位链表（hiHead）。低位链表的元素会留在原位置，而高位链表的元素则会移动到新位置。在这个过程中，使用尾插法保证链表的顺序不变。比如原来的链表是A -> B -> C，转移后仍然是A -> B -> C。
3. 红黑树处理：如果桶中存储的是红黑树，在扩容时会先将红黑树拆分成链表，按照链表的处理逻辑进行拆分，最后在新位置再判断是否需要转换回红黑树。

下面是一段JDK 1.8中resize方法里的核心逻辑代码示例（简化版），帮助大家更好地理解：

// JDK 1.8 resize 方法中的核心逻辑
// 获取旧数组
Node<K,V>[] oldTab = table;
// 获取旧数组的容量
int oldCap = oldTab.length;
// 计算新数组的容量，将旧数组容量翻倍
int newCap = oldCap << 1; 
// 创建新数组
Node<K,V>[] newTab = new Node[newCap];

// 遍历旧数组
for (int j = 0; j < oldCap; j++) {
    // 获取旧数组当前位置的元素
    Node<K,V> e = oldTab[j];
    if (e != null) {
        // 释放旧数组当前位置的引用
        oldTab[j] = null;
        if (e.next == null) { // 如果只有单个节点
            // 直接计算新位置并放入新数组
            newTab[e.hash & (newCap - 1)] = e;
        } else { // 处理链表或红黑树
            // 初始化低位链表的头节点和尾节点
            Node<K,V> loHead = null, loTail = null;
            // 初始化高位链表的头节点和尾节点
            Node<K,V> hiHead = null, hiTail = null;
            do {
                // 判断该元素应在低位链表还是高位链表
                if ((e.hash & oldCap) == 0) { 
                    if (loTail == null) {
                        loHead = e;
                    } else {
                        loTail.next = e;
                    }
                    loTail = e;
                } else { 
                    if (hiTail == null) {
                        hiHead = e;
                    } else {
                        hiTail.next = e;
                    }
                    hiTail = e;
                }
            } while ((e = e.next) != null);
            if (loTail != null) {
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) {
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}

（三）优势

相比JDK 1.7，JDK 1.8的这些改进带来了不少好处。首先，尾插法避免了链表逆序的问题；其次，虽然HashMap本身依然不是线程安全的，但这种改进消除了在并发环境下形成死循环的风险；最后，利用位运算和容量翻倍的特性，减少了重复计算，提高了性能。

四、JDK 1.7与JDK 1.8的对比

为了更直观地看出JDK 1.7和JDK 1.8在HashMap扩容和rehash方面的差异，下面通过表格进行对比：

五、总结

从上面的分析可以看出，HashMap的扩容机制和rehash细节在JDK 1.7和JDK 1.8中有着明显的不同。JDK 1.7的头插法虽然简单，但是存在链表逆序和并发死循环的问题；而JDK 1.8通过采用尾插法和位运算优化，不仅提升了性能，还增强了稳定性。对于开发者来说，深入理解这些细节，能够在实际应用中更加合理地使用HashMap，有效避免潜在的问题。要是大家对HashMap的其他特性，比如红黑树转换、哈希冲突等感兴趣，欢迎一起交流探讨！