Java 集合类 - 扩容机制（三）HashTable

前言：通过源码分析 HashTable 的扩容机制。

调用链

rehash 方法源码

/**
 * Increases the capacity of and internally reorganizes this
 * hashtable, in order to accommodate and access its entries more
 * efficiently.  This method is called automatically when the
 * number of keys in the hashtable exceeds this hashtable's capacity
 * and load factor.
 */
@SuppressWarnings("unchecked")
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

分析

• 计算新容量，新容量为 旧容量 * 2 + 1

int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;

// overflow-conscious code
// 新容量为 旧容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;

• 对计算得到的新容量进行修正

/**
 *  如果新容量大于最大的数组长度（Integer的最大值 - 8），
 *  则判断是否旧容量就是最大值了，如果是，直接返回，如果不是，则将新容量改为最大值后进行扩容操作
 */
if (newCapacity - MAX_ARRAY_SIZE > 0) {
    if (oldCapacity == MAX_ARRAY_SIZE)
        // Keep running with MAX_ARRAY_SIZE buckets
        return;
    newCapacity = MAX_ARRAY_SIZE;
}

• 生成新 Entry 数组

生成新的大容量 Entry 数组，注意还未赋值，所以里面只是一堆 null 引用，占用不了多大的空间

Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

• 结构修改计数加 1

// 这个字段表明 HashTable 的内部结构被修改的次数，用于 Collection-views 中有关 HashTable 的 fast-fail 机制
modCount++;

• 计算负载容量

threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

• 将新数组赋给 table

table = newMap;

• 将旧数组的内容复制到新数组中

for (int i = oldCapacity ; i-- > 0 ;) {
    for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
        Entry<K,V> e = old;
        old = old.next;

        // 重新计算在新数组中的索引位置
        int index = (e.hash & 0x7FFFFFFF) % newCapacity;

        // 头插法，故新数组中链顺序与旧链相反
        e.next = (Entry<K,V>)newMap[index];
        newMap[index] = e;
    }
}

头插法具体过程如下图

小结

通过源码分析 HashTable 的扩容机制：

• 扩容后数组大小为 2 * 旧容量 + 1

• 头插法，新链顺序与旧链相反