散列表的負載因子和容量

Question

當散列表中的條目數超過了負載因子和當前容量的乘積時，容量如何增加？

Answer 1

它取決於底層的實現。例如，在HashMap中，底層存儲是一個數組：

transient Entry[] table; 

Entry對象包含鍵和值。當容量不足時（正如您所說的，超過負載因子和當前容量的乘積），將創建一個新數組並將舊值複製到其中。

查看OpenJdk 7的sourcecode of HashMap並查找void resize(int newCapacity)。在該方法中最重要的行是：

Entry[] newTable = new Entry[newCapacity]; //create the new table 
transfer(newTable);       //transfer and rehash the data 
table = newTable;       //from now on use the new table 
threshold = (int)(newCapacity * loadFactor); //compute the new threshold 

threshold是可再次增加尺寸之前被包含的元素的最大數量。 transfer()也會重新排列元素，因此與原始位置相比，元素可能會存儲在不同的數組索引中。您可以查看代碼，閱讀起來非常簡單。

Answer 2

加載因子是衡量散列表在其容量自動增加之前能夠獲得的滿量程。當哈希表中的條目數超過負載因子與當前容量的乘積時，通過調用rehash方法增加容量。

這裏是翻版方法

int oldCapacity = table.length; 
Entry[] oldMap = table; 

int newCapacity = oldCapacity * 2 + 1; 
Entry[] newMap = new Entry[newCapacity]; 

一瞥正如你可以看到它的實際倍增入口[]一旦負載因數和電流容量的乘積增加了閾值的能力。

查看hashtable的rehash方法以獲取更多詳細信息。

Rehash Method

Answer 3

當您創建它，使用默認的尺寸和負荷因子創建一個新的哈希表。

源代碼

public Hashtable() { 
     this(11, 0.75f); 
} 

當添加元素進入它

它檢查

if (count >= threshold) { 

} 

分別創建新的數組和作爲拷貝所述Stivlo。

private transient Entry [] table;