散列表的负载因子和容量

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;