Java Hashtable如何实现扩容

Java中的Hashtable是一个线程安全的哈希表实现，它基于数组和链表（或红黑树）来存储数据。当Hashtable中的元素数量达到一定阈值时，它会自动进行扩容以容纳更多的元素。扩容的过程主要包括以下几个步骤：

1. 确定新的容量：当Hashtable中的元素数量达到阈值（容量 * 负载因子）时，会触发扩容操作。新的容量通常是当前容量的两倍。

2. 创建新的数组：根据新的容量，创建一个新的数组，用于存储哈希表中的元素。

3. 重新哈希：遍历旧数组中的每个元素，对每个元素进行哈希计算，然后将元素放入新数组中。在这个过程中，可能需要处理哈希冲突，即不同的元素具有相同的哈希值。Hashtable使用链表（或红黑树）来解决哈希冲突。

4. 更新引用：将Hashtable内部的数组引用指向新创建的数组。

以下是Java Hashtable扩容的关键代码片段：

// 扩容方法
void rehash() {
    int oldCapacity = table.length;
    Entry<?, ?>[] oldMap = table;

    int newCapacity = (oldCapacity << 1) + 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 = newMap[idx];
            newMap[idx] = e;
            e = next;
        }
    }
}

注意：Java 9以后，Hashtable已经被弃用，推荐使用ConcurrentHashMap作为线程安全的哈希表实现。