HashMap有两个重要的性质：size和load factor。我浏览了 Java 文档，它说0.75f是初始负载因子。但我找不到它的实际用途。
有人可以描述我们需要设置负载因子的不同场景以及不同情况下的一些示例理想值吗？
问问题
221365 次
8 回答
305
该文档很好地解释了它：
HashMap 的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重新哈希（即重建内部数据结构），使哈希表具有大约两倍的桶数。
作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。
与所有性能优化一样，最好避免过早地优化事物（即没有关于瓶颈所在位置的硬数据）。
于 2012-06-05T17:17:13.727 回答
163
默认初始容量HashMap为 16，加载因子为 0.75f（即当前地图大小的 75%）。负载因子表示HashMap容量应该在什么水平上翻倍。
例如容量和负载系数的乘积为16 * 0.75 = 12。这表示将第 12 个键值对存储到 中后HashMap，其容量变为 32。
于 2013-10-17T12:33:44.950 回答
51
实际上，根据我的计算，“完美”负载因子更接近 log 2 (~ 0.7)。尽管任何小于此的负载因子都会产生更好的性能。我认为 0.75 可能是从帽子里拔出来的。
证明：
通过预测桶是否为空，可以避免链接并利用分支预测。如果桶为空的概率超过 0.5，则它可能是空的。
让 s 代表大小， n 代表添加的键的数量。使用二项式定理，桶为空的概率为：
P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)
因此，如果桶少于
log(2)/log(s/(s - 1)) keys
当 s 达到无穷大并且如果添加的键的数量是这样的 P(0) = .5，则 n/s 迅速接近 log(2)：
lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...
于 2015-07-14T08:42:10.537 回答
34
什么是负载系数？
HashMap 增加容量需要消耗多少容量？
为什么负载系数？
默认情况下，负载因子是初始容量的 0.75 (16)，因此 25% 的存储桶在容量增加之前将是空闲的，这使得许多具有指向它们的新哈希码的新存储桶在容量增加后立即存在桶数。
现在为什么要保留许多免费存储桶以及保留免费存储桶对性能的影响是什么？
如果您将加载因子设置为 1.0，那么可能会发生一些非常有趣的事情。
假设您正在将对象 x 添加到您的 hashmap 中，其 hashCode 为 888 并且在您的 hashmap 中，表示哈希码的存储桶是 free ，因此对象 x被添加到存储桶中，但现在再次说明您是否要添加另一个对象 y，其 hashCode 是还有 888 那么你的对象 y 肯定会被添加到存储桶的末尾（因为存储桶只不过是linkedList实现存储键、值和下一个）现在这会对性能产生影响！由于如果您执行查找，您的对象 y不再存在于存储桶的头部，因此所花费的时间不会是O(1)这次取决于同一个桶中有多少项目。顺便说一下，这被称为哈希冲突，甚至当您的加载因子小于 1 时也会发生这种情况。
性能、哈希冲突和加载因子之间的相关性？
更低的负载系数= 更多的空闲桶 =更少的碰撞机会= 高性能 = 高空间要求。
如果我在某处错了，请纠正我。
于 2016-08-21T02:56:45.893 回答
20
于 2012-06-05T17:16:50.710 回答
11
对于 HashMap DEFAULT_INITIAL_CAPACITY = 16和DEFAULT_LOAD_FACTOR = 0.75f
这意味着 HashMap 中所有条目的最大数量 = 16 * 0.75 = 12。当添加第 13 个元素时，HashMap 的容量（数组大小）将翻倍！完美的插图回答了这个问题：
图片取自这里：
https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html
于 2019-04-20T13:22:20.880 回答
2
如果桶太满，那么我们必须仔细检查
一个很长的链表。
这有点违背了这一点。
所以这是一个我有四个桶的例子。
到目前为止，我的 HashSet 中有大象和獾。
这是一个很好的情况，对吧？
每个元素都有零个或一个元素。
现在我们将另外两个元素放入我们的 HashSet 中。
buckets elements
------- -------
0 elephant
1 otter
2 badger
3 cat
这也不算太糟糕。
每个桶只有一个元素。所以如果我想知道，这是否包含熊猫？
我可以很快查看 1 号存储桶，但它不是
那里和
我知道它不在我们的收藏中。
如果我想知道它是否包含猫，我看一下桶
3号，
我找到了猫，我很快就知道它是否在我们的
收藏。
如果我加上考拉呢，那还不错。
buckets elements
------- -------
0 elephant
1 otter -> koala
2 badger
3 cat
也许现在而不是在 1 号桶中只看
一个元素，
我需要看两个。
但至少我不用看大象、獾和
猫。
如果我再次寻找熊猫，它只能在桶里
1号和
除了水獭，我不需要看任何东西
考拉。
但现在我把鳄鱼放在 1 号桶里，你可以
看看这可能会发生什么。
如果 1 号桶越来越大
更大，然后我基本上必须查看所有
要找到的那些元素
应该在 1 号桶中的东西。
buckets elements
------- -------
0 elephant
1 otter -> koala ->alligator
2 badger
3 cat
如果我开始向其他存储桶添加字符串，
是的，问题只是在每个方面都变得越来越大
单桶。
我们如何阻止我们的水桶变得太满？
这里的解决方案是
"the HashSet can automatically
resize the number of buckets."
HashSet 意识到桶越来越多
太满了。
它正在失去所有一个查找的优势
元素。
它只会创建更多的桶（通常是以前的两倍）和
然后将元素放入正确的桶中。
所以这是我们的基本 HashSet 实现，带有单独的
链接。现在我要创建一个“自调整大小的 HashSet”。
这个 HashSet 将意识到桶是
变得太满和
它需要更多的桶。
loadFactor 是我们 HashSet 类中的另一个字段。
loadFactor 表示每个元素的平均数量
桶，
上面我们要调整大小。
loadFactor 是空间和时间的平衡。
如果桶太满，那么我们将调整大小。
当然，这需要时间，但是
如果水桶是一个
多一点空。
让我们看一个例子。
这是一个 HashSet，到目前为止我们已经添加了四个元素。
大象、狗、猫和鱼。
buckets elements
------- -------
0
1 elephant
2 cat ->dog
3 fish
4
5
在这一点上，我已经决定 loadFactor，
临界点，
我没问题的每个桶的平均元素数
为 0.75。
桶数为 buckets.length，即 6，而
此时我们的 HashSet 有四个元素，所以
当前大小为 4。
我们将调整我们的 HashSet 的大小，即我们将添加更多的桶，
当每个桶的平均元素数超过
负载因子。
那就是当前大小除以 buckets.length 时
大于负载因子。
此时，每个桶的平均元素数
是 4 除以 6。
4 个元素，6 个桶，即 0.67。
这小于我设置的阈值 0.75 所以我们
好的。
我们不需要调整大小。
但现在假设我们添加土拨鼠。
buckets elements
------- -------
0
1 elephant
2 woodchuck-> cat ->dog
3 fish
4
5
土拨鼠最终会进入 3 号桶。
此时，currentSize 为 5。
现在每个桶的平均元素数
是 currentSize 除以 buckets.length。
即 5 个元素除以 6 个桶是 0.83。
这超过了 0.75 的 loadFactor。
为了解决这个问题，为了使
水桶也许有点
更空，这样操作就像确定一个
桶包含
一个元素会不那么复杂，我想调整大小
我的哈希集。
调整 HashSet 的大小需要两个步骤。
首先我将桶的数量增加一倍，我有 6 个桶，
现在我将有 12 个桶。
请注意，我设置为 0.75 的 loadFactor 保持不变。
但是改变的桶数是12，
元素的数量保持不变，为 5。
5 除以 12 大约是 0.42，这远低于我们的
负载因子，
所以我们现在没事了。
但我们还没有完成，因为其中一些元素在
现在错误的桶。
比如大象。
大象在 2 号桶中，因为
大象中的人物
是8。
我们有 6 个桶，8 减 6 等于 2。
这就是为什么它最终排在第二位的原因。
但是现在我们有 12 个桶，8 mod 12 是 8，所以
大象不再属于 2 号桶。
大象属于 8 号桶。
土拨鼠呢？
土拨鼠是整个问题的始作俑者。
土拨鼠最终进入了 3 号桶。
因为 9 mod 6 是 3。
但现在我们做 9 mod 12。
9 mod 12 是 9，土拨鼠去 9 号桶。
你看到了这一切的好处。
现在 3 号桶只有两个元素，而之前有 3 个。
所以这是我们的代码，
我们的 HashSet 有单独的链接
没有做任何调整大小。
现在，这是一个我们使用调整大小的新实现。
大部分代码是相同的，
我们仍然要确定它是否包含
已经值了。
如果没有，那么我们会弄清楚它是哪个桶
应该进入并且
然后将其添加到该存储桶，将其添加到该 LinkedList。
但是现在我们增加 currentSize 字段。
currentSize 是跟踪数字的字段
我们的 HashSet 中的元素。
我们要增加它，然后我们要看看
在平均负载下，
每个桶的平均元素数。
我们将在这里进行划分。
我们必须在这里做一些铸造以确保
我们得到一个双倍的。
然后，我们将平均负载与现场进行比较
我设置为
例如，当我创建这个 HashSet 时，它是 0.75
负载因子。
如果平均负载大于loadFactor，
这意味着每个桶上的元素太多
平均，我需要重新插入。
所以这是我们重新插入方法的实现
所有元素。
首先，我将创建一个名为 oldBuckets 的局部变量。
这指的是它们目前站立的桶
在我开始调整所有内容之前。
注意我还没有创建一个新的链表数组。
我只是将存储桶重命名为 oldBuckets。
现在记住水桶是我们班的一个领域，我要去
现在创建一个新数组
的链表，但这将有两倍的元素
和第一次一样。
现在我需要实际进行重新插入，
我将遍历所有旧存储桶。
oldBuckets 中的每个元素都是字符串的 LinkedList
那是一个桶。
我将遍历那个桶并获取其中的每个元素
桶。
现在我要把它重新插入到 newBuckets 中。
我会得到它的hashCode。
我会弄清楚它是哪个索引。
现在我得到了新的存储桶，新的 LinkedList
字符串和
我会将它添加到那个新存储桶中。
回顾一下，我们已经看到的 HashSet 是 Linked 的数组
列表或存储桶。
一个自调整大小的 HashSet 可以使用一些比率或
于 2018-09-27T16:44:26.803 回答
1
我会选择一个 n * 1.5 或 n + (n >> 1) 的表大小，这将给出 0.66666~ 的负载因子而不进行除法，这在大多数系统上都很慢，尤其是在没有除法的便携式系统上硬件。
于 2016-02-16T02:13:15.437 回答