HashMap中加载因子的意义是什么？
Pri*_*shi 218 java hashmap load-factor
HashMap有两个重要的属性:size和load factor.我浏览了Java文档,它说的0.75f是初始加载因子.但我找不到它的实际用途.
有人可以描述我们需要设置负载因子的不同场景以及针对不同情况的一些样本理想值吗？
NPE*_*NPE 250
该文档解释了它相当不错:
HashMap的一个实例有两个影响其性能的参数:初始容量和负载因子.容量是哈希表中的桶数,初始容量只是创建哈希表时的容量.加载因子是在自动增加容量之前允许哈希表获取的完整程度的度量.当哈希表中的条目数超过加载因子和当前容量的乘积时,哈希表将被重新哈希(即,重建内部数据结构),以便哈希表具有大约两倍的桶数.
作为一般规则,默认加载因子(.75)在时间和空间成本之间提供了良好的权衡.较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括get和put).在图及其负载因子条目的预期数量应设置其初始容量的情况下,以最小化翻版操作的次数加以考虑.如果初始容量大于最大条目数除以加载因子,则不会发生重新加载操作.
与所有性能优化一样,最好避免过早地优化事物(即没有关于瓶颈所在的硬数据).
- 如果地图的大小更大,则哈希冲突的概率较小.例如,如果地图的大小为4,则具有哈希码4,8,16和32的元素将放置在同一个存储桶中,但是如果地图的大小超过32,则每个项目将获得自己的存储桶.初始大小为4且载荷因子为1.0的地图(4个桶,但是单个桶中的所有4个元素)在这个示例中平均比负载因子0.75的另一个慢两倍(8个桶,两个桶填充 - 元素"4"和元素"8","16","32"). (18认同)
- 具有条目数=容量的加载因子= 1的散列映射在统计上将具有大量冲突(=当多个密钥产生相同的散列时).发生冲突时,查找时间会增加,因为在一个存储桶中将有> 1个匹配的条目,必须单独检查密钥的相等性.一些详细的数学:http://preshing.com/20110504/hash-collision-probabilities/ (17认同)
- 其他答案建议指定`capacity = N/0.75`以避免重复,但我最初的想法只是设置`load factor = 1`.这种方法会有缺点吗？为什么加载因子会影响`get()`和`put()`运算成本？ (12认同)
- 我不跟着你@atimb; loadset属性仅用于确定何时增加存储大小对吗？ - 如何使用一个负载集增加哈希冲突的可能性？ - 散列算法不知道地图中有多少项或者它获取新存储"桶"的频率等等.对于任何相同大小的对象集,无论它们如何存储,你都应该拥有重复哈希值的概率相同...... (7认同)
小智 138
take的默认初始容量HashMap为16,加载因子为0.75f(即当前地图大小的75%).负载系数表示HashMap容量应加倍的水平.
例如容量和负载系数的乘积16 * 0.75 = 12.这表示在将第12个键值对存储到其中之后HashMap,其容量变为32.
- 尽管您的回答很明确，但是能否请您说一下存储12个键值对之后容量是否变为32，还是添加第13个条目时容量改变然后插入条目。 (3认同)
- @userab 它将在第 13 条条目上，您可能不再寻找该答案，而是寻找其他答案。 (2认同)
Hel*_*rld 34
实际上,根据我的计算,"完美"载荷因子更接近log 2(~0.7).虽然任何小于此的负载系数都会产生更好的性能.我认为.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...
- 数学书呆子FTW!可能`.75`被四舍五入到最接近的易于理解的分数为`log(2)`,看起来不像一个神奇的数字.我很想看到JDK默认值的更新,上面的评论高于其实现:D (4认同)
- 我真的很想喜欢这个答案，但我是一名 JavaEE 开发人员，这意味着数学从来都不是我的强项，所以我对你写的内容知之甚少，哈哈 (3认同)
Suj*_*dal 26
什么是负载系数？
HashMap增加容量所需的容量是多少？
为什么加载因子？
负载因子默认为初始容量的0.75(16)因此,在容量增加之前,25%的桶将是空闲的,并且这使得许多带有新哈希码的新桶指向它们之后存在增加水桶数量.
现在为什么要保留许多免费存储桶以及保持免费存储桶对性能有何影响？
如果将加载因子设置为1.0,那么可能会发生一些非常有趣的事情.
假设您正在向hashmap中添加一个对象x,其hashCode为888,并且在您的hashmap中,表示哈希码的桶是空闲的,因此对象x被添加到桶中,但现在再次说明是否要添加另一个对象y,其hashCode是还有888那么你的对象y肯定会被添加到桶的末尾(因为桶只是LinkedList实现存储键,值和下一个)现在这会对性能产生影响!由于你的对象y不再存在于桶的头部,如果你执行查找,所用的时间不会是O(1),这次它取决于同一个桶中有多少项.这称为哈希冲突,当加载因子小于1时甚至会发生这种情况.
性能,哈希冲突和加载因子之间的相关性？
较低的载荷系数 =更多的自由铲斗= 更少的碰撞机会 =高性能=高空间要求.
如果我错在某处,请纠正我.
- 您可以添加一些关于如何将hashCode剥离到范围为1- {count bucket}的数字,因此它本身不是桶的数量,但是哈希算法的最终结果涵盖了范围更广.HashCode不是完整的哈希算法,它只是小到可以轻松地重新处理.所以没有"免费存储桶"的概念,而是"最小数量的免费存储桶",因为您可以将所有元素存储在同一个存储桶中.相反,它是哈希码的关键空间,它等于容量*(1/load_factor).40个元素,0.25个负载系数= 160个桶. (2认同)
For HashMap DEFAULT_INITIAL_CAPACITY = 16 and DEFAULT_LOAD_FACTOR = 0.75f
it means that MAX number of ALL Entries in the HashMap = 16 * 0.75 = 12. When the thirteenth element will be added capacity (array size) of HashMap will be doubled!
Perfect illustration answered this question:
image is taken from here:
https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html
| 归档时间： |
|
| 查看次数： |
167717 次 |
| 最近记录： |