别再問Hashtable了，一篇文章讓你不再死記硬背

Hashtable實作map接口，底層通過數組加連結清單實作。key值不能為null，是線程安全的map容器，裡面的方法通過synchronized修飾。預設初始容量為11，負載因子為0.75，擴容是原容量的2倍加1。

put源碼簡析

public synchronized V put(K key, V value) {

// Make sure the value is not null

if (value == null) {//key值不能為空

throw new NullPointerException();

}

Entry<?,?> tab[] = table;

int hash = key.hashCode();//計算key的hash值

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings(“unchecked”)

Entry<K,V> entry = (Entry<K,V>)tab[index];

for(; entry != null ; entry = entry.next) {//判斷目前桶是否為null，如果為空跳出循環，執行addEntry方法添加資料

if ((entry.hash == hash) && entry.key.equals(key)) {//添加的key值是否和其中的key值相等

V old = entry.value; //如果相等，則value值對原值進行覆寫

entry.value = value;

return old;

}

}

addEntry(hash, key, value, index);//添加資料

return null;

}

addEntry方法源碼簡析

private void addEntry(int hash, K key, V value, int index) {

modCount++;

Entry<?,?> tab[] = table;

if (count >= threshold) {//當數組長度大于擴容閥值執行rehash方法

// Rehash the table if the threshold is exceeded

rehash();//對Hashtable擴容，将原來的資料重新添加到新的Hashtable中

tab = table;

hash = key.hashCode();

index = (hash & 0x7FFFFFFF) % tab.length;//重新計算桶值

}

// Creates the new entry.

Entry<K,V> e = (Entry<K,V>) tab[index];

tab[index] = new Entry<>(hash, key, value, e);//添加節點

count++;//數量+1

}

rehash()方法源碼簡析

protected void rehash() {

int oldCapacity = table.length;//擷取原數組的長度

Entry<?,?>[] oldMap = table;

// overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 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 ; ) {//對每個桶的連結清單添加到新的map中
            Entry<K,V> e = old;//第一次擷取目前節點，第二次擷取目前連結清單的下一個節點
            old = old.next;//擷取下一個節點
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;//重新計算桶值
            e.next = (Entry<K,V>)newMap[index];//第一次e.next為null，第二次為上一個節點（桶值相等時）
            newMap[index] = e;//将原map中的資料添加到新的map中
        }
    }
}