JDK1.7 版本中 HashMap 扩容

作者: 小蓝田 | 来源:发表于2021-05-27 16:20 被阅读0次

扩容
扩容是指当容器中元素的数量达到某个阈值时，容器自己进行的容量翻倍的操作。
JDK1.7 HashMap 扩容方法

void transfer(Entry[] newTable, boolean rehash) {
      int newCapacity = newTable.length;
      for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
       }
}

扩容逻辑
假设原容器中有两个元素a和b，此时原容器为 table，如下图：

根据上面的扩容逻辑，循环遍历 table 中的元素，循环刚开始时，e 指向第一个元素 a，next 指向 b，如下图：

假设扩容后元素存入下标为 3 的位置，执行 e.next = newTable[i] 后，变化如下：

由于新容器还没有任何元素，因此 newTable[i] 为空，因此 a 的 next 指向了 null。
继续执行 newTable[i] = e，此时新容器中 i 位置指向了 a 如下图：
注意：此时新容器和老容器中的 a 是同一个对象，存在堆中，因此无论是在新容器还是老容器中对 a 进行修改，两个容器都是可见的。真实指向应如下图，但为了方便看，将两个容器分开展示。

继续执行 e = next，此时 e 和 next 都指向 b 如下图：

继续下一轮循环，执行 Entry<K,V> next = e.next，此时 next 指向 null 如下图：

继续执行 e.next = newTable[i]，因为此时 e 即为 b，因此 e.next 即为 b.next，newTable[i] 现在已经有了元素 a，因此 b.next 指向了 a 如下图：

继续执行 newTable[i] = e，新容器中 i 位置存入了 b，上一步中 b.next 已经指向了 a，因此新的结构如下图：
实际真实指向应是：

继续执行 e = next，此时 e 和 next 都指向了 null，如下图：
再次进入循环时，由于 e==null 不满足条件，结束循环。