MENU

Java 集合类 - 扩容机制(三)HashTable

June 23, 2018 • Code

前言:通过源码分析 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

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

Last Modified: July 12, 2018
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment