7

从 JavaDoc 的HashMap：

作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。

如果我们有更高的值，为什么会增加查找成本？

4

5 回答 5

6

哈希表的负载因子定义为

n/s，存储条目数 n 与表的桶数组大小 s 的比值。

当冲突数量较少时，哈希表的高性能得以保持。当负载因子高时，存储相同数量的条目所需的哈希桶数保持较低，从而增加了冲突的概率。

于 2012-08-25T12:16:21.657 回答
3

这里我们首先要了解一下容量和负载率是什么意思：

容量：这是任何给定时间点任何哈希表中的桶数。

负载因子：负载因子是哈希表在其容量自动增加之前允许达到的程度的度量

因此，在容量增加之前，哈希表可能会占用更多的负载因子。

  • 现在考虑到 hashCode() 的最佳实现，只有一个值会放在一个桶中，这里查找成本将是最低的
  • 在最坏的情况下，所有值都将放在同一个桶中，并且查找成本将是最大的
  • 在一般情况下，这肯定取决于 hashCode() 实现，但这里还有一个因素是负载因子，因为集合被占用的越多，冲突的机会就越大，因此更高的负载因子会增加查找非理想情况下的成本。
于 2014-10-13T18:10:12.327 回答
2

它与 HashTable 的底层实现方式有关，它使用哈希码，由于计算哈希码的算法并不完美，可能会发生一些冲突，增加负载因子会增加发生冲突的概率，从而减少查找性能...

于 2012-08-25T12:16:03.430 回答
0

默认负载系数 (0.75)。

If declare load factor as
1 the restructuring process only happens when number of elements are exceeding the capacity of the HashMap.
于 2012-08-25T12:17:18.507 回答
0

负载因子 0.75 可以使用公式（n/s，存储条目数 n 与表的存储桶数组的大小 s 的比率。）这样解释：

假设你有 75 个值需要存储在哈希表中，并且你有 100 个空数组块来存储它们，这里冲突的机会被最小化并且负载因子为 0.75。

现在假设您有 75 个值要存储并且只有 10 个空数组块（负载因子 7.5），这意味着您将遇到冲突并使用任何会增加搜索时间的冲突解决技术。

现在你有 75 个条目和 1000 个空数组块（负载因子 0.075），这将导致很多空块，这会浪费很多空间。

因此，经验法则是随着负载因子值的增加，您的搜索时间将增加，并且当它接近 0 时，会浪费更多的存储空间。

因此，这是一个时空交易。

于 2016-02-17T16:32:35.350 回答