为什么hashmap中更高的负载因子会增加查找成本?

uttx8gqw  于 2021-07-09  发布在  Java
关注(0)|答案(5)|浏览(367)

来自 HashMap :
作为一般规则,默认负载系数(.75)在时间和空间成本之间提供了一个很好的折衷。较高的值会减少空间开销,但会增加查找成本(反映在hashmap类的大多数操作中,包括get和put)。
如果我们有一个更高的值,为什么会增加查找成本?

myzjeezk

myzjeezk1#

在这里,我们首先应该了解容量和负载系数的含义:
容量:这是任何哈希表在任何给定时间点的存储桶数。
负载因子:负载因子是在哈希表的容量自动增加之前,允许哈希表获得的完整度的度量
因此,在容量增加之前,哈希表占用的负载因子越大。
现在给出hashcode()的最佳实现一个bucket中只会有一个值这里的查找开销将是最小
在最坏的情况下,所有值都将放在同一个bucket中,查找成本将是最大值
一般情况下,这当然取决于hashcode()实现,但这里要考虑的另一个因素是负载因子,随着集合占用的越多,冲突的可能性就越大,因此在非理想情况下,更高的负载因子将增加查找成本

rdlzhqv9

rdlzhqv92#

哈希表的负载因子定义为
n/s,存储条目数n与表的存储桶数组大小s之比。
在冲突次数较少的情况下,哈希表保持了较高的性能。当负载因子较高时,存储相同数目的条目所需的哈希桶的数目保持较低,从而增加了冲突的概率。

093gszye

093gszye3#

负载系数0.75可以用以下公式来解释(n/s,存储条目数n与表的存储桶数组大小s之比):
假设您有75个值需要存储在哈希表中,并且有100个空数组块要存储它们,这里冲突的可能性最小化,负载因子为0.75。
现在假设您有75个值要存储,只有10个空数组块(加载因子7.5),这意味着您将有冲突,并使用任何冲突解决技术,这将增加您的搜索时间。
现在换一种方式,您有75个条目和1000个空数组块(加载因子0.075),这将导致大量的空块,这是大量的空间浪费。
因此,经验法则是,随着负载因子值的增加,搜索时间会增加,当它接近0时,会浪费更多的存储空间。
因此这是一种时空交易。

shstlldc

shstlldc4#

这与哈希表是如何在引擎盖下实现的有关,它使用哈希代码,由于计算哈希代码的算法并不完美,因此可能会发生一些冲突,增加负载因子会增加发生冲突的概率,从而降低查找性能。。。

l0oc07j2

l0oc07j25#

默认负载系数(0.75)。

If declare load factor as
1 the restructuring process only happens when number of elements are exceeding the capacity of the HashMap.

相关问题