Hashtable哈希表如何扩容

在Java中，Hashtable 是一个同步的哈希表实现，它不允许 null 键和 null 值。当 Hashtable 中的元素数量达到其容量与负载因子的乘积时，它会自动进行扩容。

以下是 Hashtable 扩容的基本步骤：

1. 确定新容量：

   • 当 Hashtable 需要扩容时，它会根据当前容量和负载因子计算新的容量。
   • 新容量通常是当前容量的两倍（但这并不是绝对的，因为 Hashtable 使用的是一个特定的扩容策略）。

2. 创建新数组：

   • 根据计算出的新容量，创建一个新的数组来存储哈希表中的元素。

3. 重新哈希：

   • 遍历旧数组中的每个元素，并使用新的容量重新计算它们的哈希值。
   • 根据新的哈希值，将元素放入新数组中的适当位置。

4. 替换旧数组：

   • 将新数组替换为 Hashtable 的内部数组，以便后续的操作可以使用新的容量。

以下是一个简化的示例代码，展示了 Hashtable 扩容的基本逻辑：

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    int newCapacity = (oldCapacity << 1) + 1; // 新容量通常是旧容量的两倍加一
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)(newCapacity * loadFactor);
    table = newMap;

    for (int i = oldCapacity; i-- > 0;) {
        for (Entry<K,V> e = (Entry<K,V>)oldMap[i]; e != null;) {
            Entry<K,V> next = (Entry<K,V>)e.next;
            int idx = indexFor(e.hash, newCapacity);
            e.next = (Entry<K,V>)newMap[idx];
            newMap[idx] = e;
            e = next;
        }
    }
}

请注意，上述代码是一个简化的示例，实际的 Hashtable 实现可能会更复杂，并且包含更多的优化和边界条件处理。

另外，如果你正在使用 HashMap 而不是 Hashtable，那么扩容的逻辑会有所不同。HashMap 在扩容时通常会将容量增加到原来的两倍，并且使用更高效的重新哈希算法。