散列桶的数量 [英] number of hash buckets

问题描述

在 HashMap 文档中，它提到：

• 初始容量仅仅是哈希表创建时的容量 li>
  
• 容量是散列表中桶的数量。

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

哈希桶是100还是16？

编辑：

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

解决方案

100或16桶都不是。最有可能的是有256个桶，但这不能由文档保证。

从更新文档链接：

负载因子是衡量哈希表在其容量自动增加之前能够获得多少满的度量。当散列表中条目的数量超过了加载因子和当前容量的乘积时，散列表就会被重新映射（也就是说，内部数据结构被重建），以便散列表的大约两次桶数。

（强调我的）

如果我们忽略上面的大约这个词，我们确定每当散列表变成75％满（或者你在构造函数中指定的那个加载因子）时，散列桶的数量就会增加一倍。这意味着每当插入第12,24,48和96个元素时，桶的数量就会增加一倍，而总共会有256个桶。

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

NB我到达了134号码，因为它是最小的整数 N ，所以 0.75 * N> 100 。

In the HashMap documentation, it is mentioned that:

• the initial capacity is simply the capacity at the time the hash table is created
• the capacity is the number of buckets in the hash table.

Now suppose we have intial capacity of 16 (default), and if we keep adding elements to 100 nos, the capacity of hashmap is 100 * loadfactor.

Will the number of hash buckets is 100 or 16?

Edit:
From the solution I read: buckets are more than the elements added. Taking this as view point: so if we add Strings as key, we will get one element/bucket resulting in a lot of space consumption/complexity, is my understanding right ?

解决方案

Neither 100 nor 16 buckets. Most likely there will be 256 buckets, but this isn't guaranteed by the documentation.

From the updated documentation link:

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

(emphasis mine)

So, if we ignore the word "approximately" above, we determine that whenever the hash table becomes 75% full (or whichever load factor you specify in the constructor), the number of hash buckets doubles. That means that the number of buckets doubles whenever you insert the 12th, 24th, 48th, and 96th elements, leaving a total of 256 buckets.

However, as I emphasized in the documentation snippet, the number is approximately twice the previous size, so it may not be exactly 256. In fact, if the second-to-last doubling is replaced with a slightly larger increase, the last doubling may never happen, so the final hash table may be as small as 134 buckets, or may be larger than 256 elements.

N.B. I arrived at the 134 number because it's the smallest integer N such that 0.75 * N > 100.

这篇关于散列桶的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！