java - 哈希桶数

Question

在HashMap文档中，提到：

• 初始容量只是创建哈希表时的 容量
• 容量是哈希表中的桶数。

现在假设我们的初始容量为 16（默认），如果我们继续将元素添加到 100 个，则 hashmap 的容量为 100 * loadfactor。

请问哈希桶的数量是100还是16？

编辑：
从我读到的解决方案：存储桶不仅仅是添加的元素。以此为观点：所以如果我们添加字符串作为键，我们将得到一个元素/桶，从而导致大量的空间消耗/复杂性，我的理解对吗？

Answer 1

既不是 100 也不是 16 桶。很可能会有 256 个存储桶，但文档并不能保证这一点。

从更新的文档链接：

负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重新哈希（即重建内部数据结构），使哈希表的桶数大约增加一倍。

（强调我的）

因此，如果我们忽略上面的“大约”一词，我们会确定每当哈希表满 75%（或您在构造函数中指定的任何负载因子）时，哈希桶的数量都会翻倍。这意味着每当您插入第 12、24、48 和 96 个元素时，桶的数量就会翻倍，总共留下 256 个桶。

然而，正如我在文档片段中强调的那样，这个数字大约是之前大小的两倍，所以它可能不完全是 256。事实上，如果倒数第二个加倍被替换为稍微大一点的增加，最后一个加倍可能永远不会发生，所以最终的哈希表可能小到 134 个桶，也可能大于 256 个元素。

注意我得到了 134 数字，因为它是最小的N整数0.75 * N > 100。

Answer 2

查看源代码HashMap我们看到以下内容：

threshold = capacity * loadfactor
size = number of elements in the map

if( size >= threshold ) {
  double capacity
}

因此，如果初始容量为 16，负载因子为 0.75（默认值），则初始阈值为 12。如果添加第 12 个元素，容量将上升到 32，阈值为 24。下一步将是容量64和阈值48等等等。

因此，对于 100 个元素，您应该有 256 个容量和 192 个阈值。

请注意，这仅适用于标准值。如果您知道地图将包含的大致元素数量，您应该使用足够高的初始容量创建它，以防止在容量增加时复制。

更新：

关于容量的一句话：即使您定义了不同的初始容量，它也始终是 2 的幂。然后哈希图会将容量设置为大于或等于提供的初始容量的 2 的最小幂。

Answer 3

从您的链接：

当哈希表中的条目数超过负载因子与当前容量的乘积时，通过调用rehash方法，容量大致翻倍。

这意味着如果我们的初始容量为 16，当超过时，容量将增加 32，下一次增加 64，依此类推。

在您的情况下，您要添加 100 个。因此，当您到达第 16 个数字时，大小将增加 32，因此现在总大小为 48。再次继续添加直到第 48 个数字，大小将增加 64。因此，在您的情况下，存储桶的总大小为 112。

Answer 4

在文档中

When the number of entries in the hash table exceeds the product of the 
load factor and the current capacity, the capacity is roughly doubled by 
calling the rehash method.

threshold=product of the  load factor and the current capacity

让我们试试.. hashmap 的初始大小是 16
，默认加载因子是0.75 所以第一个阈值是 12 所以添加 12 个元素下一个容量将是.. (16*2) =32第二个
阈值是 24 所以在添加第 24 个元素后下一个容量将是(32*2)=64

等等..

Answer 5

每个实际项目至少有一个桶。如果您添加的项目超过 16 个，则必须调整表的大小并重新散列。

现在假设我们的初始容量为 16（默认），如果我们继续将元素添加到 100 个，则 hashmap 的容量为 100 * loadfactor。

实际上它说：

如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

即，如果最多有 100 个项目并且容量为 100/0.75 = 133，则不应该发生重新散列。请注意，这意味着即使表未满，也可能必须在接近满时重新散列。因此，如果您期望 <=100 个项目，使用默认加载因子设置的理想初始容量约为 135+。