当前位置：首页 > article >正文

一文讲解Java中HashMap的扩容机制

article 2025/2/3 5:42:45

HashMap扩容时，会创建一个新的数组，其容量是原数组容量的两倍。然后将键值对放到新计算出的索引位置上。一部分索引不变，另一部分索引为“原索引+旧容量”

为了便于理解，结合JDK7和JDK8两个版本来讲。

在 JDK 7 中，定位元素位置的代码是这样的：

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

其实就相当于用键的哈希值和数组大小取模，也就是 hashCode % table.length。

那我们来假设：

数组 table 的长度为 2
键的哈希值为 3、7、5

取模运算后，键发生了哈希冲突，都到 table[1] 上了。那么扩容前就是这个样子。
在这里插入图片描述
数组的容量为 2，key 为 3、7、5 的元素在 table[1] 上，需要通过拉链法来解决哈希冲突。

假设负载因子 loadFactor 为 1，也就是当元素的个数大于 table 的长度时进行扩容。
扩容后的数组容量为 4。

key 3 取模（3%4）后是 3，放在 table[3] 上。
key 7 取模（7%4）后是 3，放在 table[3] 上的链表头部。
key 5 取模（5%4）后是 1，放在 table[1] 上。

7 跑到 3 的前面了，因为 JDK 7 使用的是头插法。

e.next = newTable[i];

同时，扩容后的 5 跑到了下标为 1 的位置。

最好的情况就是，扩容后的 7 在 3 的后面，5 在 7 的后面，保持原来的顺序。

JDK 8 完全扭转了这个局面，因为 JDK 8 的哈希算法进行了优化，当数组长度为 2 的幂次方时，能够很巧妙地解决 JDK 7 中遇到的问题。

JDK 8 的扩容代码如下所示：

Node<K,V>[] newTab = new Node[newCapacity];
for (int j = 0; j < oldTab.length; j++) {
    Node<K,V> e = oldTab[j];
    if (e != null) {
        int hash = e.hash;
        int newIndex = hash & (newCapacity - 1); // 计算在新数组中的位置
        // 将节点移动到新数组的对应位置
        newTab[newIndex] = e;
    }
}

新索引的计算方式是 hash & (newCapacity - 1)，和 JDK 7 的 h & (length-1)没什么大的差别，差别主要在 hash 方法上，JDK 8 是这样：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

将键的hashCode()返回的 32 位哈希值与这个哈希值无符号右移 16 位的结果进行异或。

JDK 7 是这样：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
    //将原始哈希码h右移 20 位和 12 位，然后与h进行异或操作，接着再将结果右移 7 位和 4 位，再次与结果进行异或操作。通过这样的移位和异或操作，对原始哈希码进行了重新组合，使得最终得到的哈希值在哈希表中能够更均匀地分布，从而减少哈希冲突的概率，提高哈希表的性能。
}

我们用 JDK 8 的哈希算法来计算一下哈希值，就会发现别有洞天。
假设扩容前的数组长度为 16（n-1 也就是二进制的 0000 1111，1X2^0+ 1X2^1+ 1X2^2+ 1X2^3 =1+2+4+8=15），key1 为 5（二进制为 0000 0101），key2 为 21（二进制为 0001 0101）。

key1 和 n-1 做 & 运算后为 0000 0101，也就是 5；
key2 和 n-1 做 & 运算后为 0000 0101，也就是 5。
此时哈希冲突了，用拉链法来解决哈希冲突。

现在，HashMap 进行了扩容，容量为原来的 2 倍，也就是 32（n-1 也就是二进制的 0001 1111，1X2^0+ 1X2^1+ 1X2^2+ 1X2^3+ 1X2^4=1+2+4+8+16=31）。

key1 和 n-1 做 & 运算后为 0000 0101，也就是 5；
key2 和 n-1 做 & 运算后为 0001 0101，也就是 21=5+16，也就是数组扩容前的位置+原数组的长度。

神奇吧？
在这里插入图片描述

换句话说，在 JDK 8 的新 hash 算法下，数组扩容后的索引位置，要么就是原来的索引位置，要么就是“原索引+原来的容量”，遵循一定的规律。

当然了，这个功劳既属于新的哈希算法，也离不开 n 为 2 的整数次幂这个前提，这是它俩通力合作后的结果 hash & (newCapacity - 1)。
在这里插入图片描述

那你说说扩容的时候每个节点都要进行位运算吗，如果我这个HashMap里面有几十万条数据，都要进行位运算吗？

在 JDK 8 的新 hash 算法下，数组扩容后的索引位置，要么就是原来的索引位置，要么就是“原索引+原来的容量”，遵循一定的规律。

具体来说，就是判断原哈希值的高位中新增的那一位是否为 1，如果是，该元素会被移动到原位置加上旧容量的位置；如果不是，则保持在原位置。

假设原数组长度为 oldCap，扩容后数组长度为 newCap = oldCap * 2。在二进制表示中，newCap 比 oldCap 多了一位高位。例如，原数组长度 oldCap = 16（二进制为 0001 0000），扩容后 newCap = 32（二进制为 0010 0000）。

当进行元素迁移时，对于原数组中的每个元素，我们只需要判断其哈希值与原数组长度进行按位与运算的结果：
- 如果 (e.hash & oldCap) == 0，说明原哈希值的高位中新增的那一位为 0，元素在新数组中的位置与原数组相同。
- 如果 (e.hash & oldCap) != 0，说明原哈希值的高位中新增的那一位为 1，元素在新数组中的位置为原位置加上旧容量。