扩容 - 基本原理

那么就可以将这个操作转换为位运算。

static int indexFor(int h, int length) { return h & (length-1);

}

扩容 - 基本原理

设 HashMap 的 table 长度为 M，需要存储的键值对数ᰁ为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此查找的复杂度为 O(N/M)。

为了让查找的成本降低，应该使 N/M 尽可能小，因此需要保证 M 尽可能大，也就是说 table 要尽可能大。

HashMap 采用动态扩容来根据当前的 N 值来调整 M 值，使得空间效率和时间效率都能得到保证。

参数含义 capacitytable 的容ᰁ大小，默认为 16。

需要注意的是 capacity 必须保证为 2 的 n 次方。size键值对数ᰁ。thresholdsize 的临界值，当 size 大于等于 threshold 就必须进行扩容操作。

loadFactor 装载因子，table 能够使用的比例，threshold = (int)(capacity* loadFactor)。从下面的添加元素代码中可以看出，当需要扩容时，令 capacity 为原来的两倍。

void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex];

table[bucketIndex] = new Entry<>(hash, key, value, e);

if (size++ >= threshold)

resize(2 * table.length);

}

扩容使用 resize() 实现，需要注意的是，扩容操作同样需要把 oldTable 的所有键值对᯿新插入 newTable 中，因此这一步是很费时的。

扩容-重新计算桶下标

在进行扩容时，需要把键值对᯿新计算桶下标，从而放到对应的桶上。在前面提到，HashMap 使用 hash%capacity 来确定桶下标。

HashMap capacity 为 2 的 n 次方这一特点能够极大降低᯿新计算桶下标操作的复杂度。

假设原数组长度 capacity 为 16，扩容之后 new capacity 为 32：

capacity : 00010000 new capacity : 00100000

对于一个 Key，它的哈希值 hash 在第 5 位：

1. 为 0，那么 hash%00010000 = hash%00100000，桶位置和原来一致；
2. 为 1，hash%00010000 = hash%00100000 + 16，桶位置是原位置 + 16。