HashMap 中负载因子的重要性是什么？

小开

从文档:

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

这实际上取决于您的特定需求，没有“经验法则”来指定初始负载系数。

小开

最佳答案

文档很好地解释了它:

HashMap实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中桶的数量，初始容量就是哈希表创建时的容量。负载因子衡量的是在哈希表的容量自动增加之前允许达到的满度。当哈希表中的条目数量超过负载因子和当前容量的乘积时，哈希表将被重新哈希(即重新构建内部数据结构)，这样哈希表的桶数大约是原来的两倍。

作为一般规则，默认负载因子(.75)在时间和空间成本之间提供了一个很好的权衡。较高的值会减少空间开销，但会增加查找成本(反映在HashMap类的大多数操作中，包括get和put)。在设置映射的初始容量时，应考虑映射中的预期条目数及其负载因子，以使重新散列操作的数量最小化。如果初始容量大于最大条目数除以负载因子，则不会发生重新散列操作。

与所有性能优化一样，避免过早优化是一个好主意(即没有关于瓶颈在哪里的硬数据)。

小开

HashMap的默认初始容量为16，负载因子为0.75f(即当前地图大小的75%)。负载因子表示在哪个级别HashMap容量应该加倍。

例如容量与负载系数的乘积为16 * 0.75 = 12。这表示在将第12个键值对存储到HashMap中后，它的容量变成32。

小开

实际上，根据我的计算，“完美”的负载系数更接近于log 2(~ 0.7)。尽管任何负载系数小于这个值都会产生更好的性能。我觉得点75手枪可能是从帽子里拿出来的。

证明:

可以避免链和分支预测，通过预测如果a 桶是否为空。一个桶可能是空的，如果它的概率

设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...

小开

我会选择n * 1.5或n + (n >> 1)的表大小，这将给出不除法的负载因子。66666~，这在大多数系统上是很慢的，特别是在硬件中没有除法的便携式系统上。

小开

什么是载客率?

HashMap为增加其容量而消耗的容量量。

为什么是载重系数?

负载系数默认为初始容量(16)的0.75，因此在容量增加之前，25%的桶将是空闲的。这使得在桶数量增加之后，许多带有指向它们的新hashcode的新桶存在。

你为什么要保留许多免费的水桶?保留空闲桶对性能有什么影响?

如果您将加载因子设置为1.0，那么可能会发生一些非常有趣的事情。

假设你正在添加一个对象x到你的hashmap，它的hashCode是888 &在你的hashmap中，表示hashcode的bucket是空闲的，所以对象x会被添加到bucket中，但是现在再次说，如果你添加另一个对象y，其hashcode也是888，那么你的对象y肯定会被添加到bucket的末尾(因为桶只是linkedList实现，存储key,value &下一个)，现在这对性能有影响!由于您的对象y不再出现在桶的头部，如果您执行查找，所花费的时间将不再是O (1)，这取决于同一桶中有多少项。顺便说一下，这叫做哈希碰撞甚至当加载系数小于1时也会发生这种情况。

性能、哈希碰撞和amp的相关性;加载因子

低负载因数 =空闲桶多= 碰撞几率降低 =高性能=高空间需求。
更高的负载系数 =更少的空闲桶= 碰撞几率更高 =更低的性能=更低的空间需求。

小开

如果桶太满了，我们就得翻一翻

一个非常长的链表。

这有点违背了重点。

这是一个有四个桶的例子。

到目前为止，我的HashSet中有大象和獾。

这是个很好的情况，对吧?

每个元素有0个或1个元素。

现在我们将另外两个元素放入HashSet中。

     buckets      elements
-------      -------
0          elephant
1          otter
2          badger
3           cat

这也不算太糟。

每个桶只有一个元素．如果我想知道，这里面有熊猫吗?< / p >

我可以很快地看一下1号桶，它不是

那里,

我就知道这不是我们的收藏。

如果我想知道里面是否有猫，我会看桶

3号,

我找到猫，我很快就知道它是不是在我们的

收集。

如果我加上考拉，那还不错。

             buckets      elements
-------      -------
0          elephant
1          otter -> koala
2          badger
3           cat

也许现在不是在1号桶里只看

一个元素,

我需要看两个。

但至少我不用看大象，獾和

猫。

如果我再找熊猫，它只能在桶里

1号和

我什么都不用看除了水獭和

考拉。

但是现在我把鳄鱼放在1号桶里，你可以

看看接下来会发生什么。

如果1号桶变得越来越大和< / p >

更大，那么我基本上要看遍所有的

找到这些元素

应该在1号桶里的东西。

            buckets      elements
-------      -------
0          elephant
1          otter -> koala ->alligator
2          badger
3           cat

如果我开始往其他桶里添加字符串，

是的，问题越来越大，在每一个

单桶。

我们如何阻止我们的桶太满?

这里的解决方法是

          "the HashSet can automatically


resize the number of buckets."

HashSet意识到桶正在得到

太满了。

它失去了一次查找的优势

元素。

它只会创建更多的存储桶(通常是以前的两倍)和

然后将元素放入正确的存储桶中。

这是我们的基本HashSet实现

< p >链接。现在我要创建一个“self-resizing HashSet”

这个HashSet会意识到桶是

吃得太饱

它需要更多的桶。

loadFactor是HashSet类中的另一个字段。

loadFactor表示每个元素的平均数量

桶,

上面我们要调整大小。

loadFactor是空间和时间之间的平衡。

如果桶太满了，我们会调整大小。

这当然需要时间，但是

这可能会节省我们的时间如果桶是一个

再空一点。

让我们看一个例子。

这是一个HashSet，到目前为止我们已经添加了四个元素。

大象，狗，猫和鱼。

          buckets      elements
-------      -------
0
1          elephant
2          cat ->dog
3           fish
4
5

此时，我已经确定loadFactor和

阈值,

每个桶的平均元素数就可以了

等于0.75。

桶数就是桶数。长度是6，然后

此时我们的HashSet有四个元素，所以

当前大小为4。

我们会调整HashSet的大小，也就是说我们会添加更多的桶，

当每个桶的平均元素数超过

负载系数。

即当前大小除以桶数。长度是

大于loadFactor。

此时，每个桶的平均元素数

是4除以6。

4个元素，6个桶，等于0.67。

这比我设置的0.75的阈值要小，所以我们

好吧。

我们不需要调整大小。

现在我们加入土拨鼠。

                  buckets      elements
-------      -------
0
1          elephant
2        woodchuck-> cat ->dog
3           fish
4
5

土拨鼠会被放在第三桶里。

此时，currentSize为5。

现在是每个桶的平均元素数

是currentSize除以buckets.length。

5个元素除以6个桶等于0.83。

这超过了负荷因子0.75。

为了解决这个问题，为了使

桶可能会有一点

更空的操作，如确定是否a

桶包含

元素会变得不那么复杂，我想调整大小

我的HashSet。

调整HashSet的大小需要两个步骤。

首先我把桶数翻倍，我有6个桶，

现在我有12个桶。

注意，我设置为0.75的loadFactor保持不变。

但是改变的桶数是12，

元素的数量保持不变，是5。

5除以12大约是0.42，这比我们的

负载系数,

所以我们现在没事了。

但这还没完，因为有些元素还在

现在桶错了。

例如，大象。

大象在2号桶里，因为它的数量

大象的文字

是8。

我们有6个桶，8减6是2。

这就是为什么它最终排名第二。

但现在我们有12个桶，8对12取余是8，所以

大象不再属于第二桶了。

大象属于8号桶。

土拨鼠呢?

这一切都是土拨鼠挑起的。

土拨鼠最后在三号桶里。

因为9对6取余等于3。

现在是9对12取余。

9 mod 12 = 9，土拨鼠去了9号桶。

你可以看到这一切的好处。

现在3号桶只有两个元素，而之前它有3。

这是我们的代码，

我们的HashSet有单独的链

没有做任何大小调整。

现在，这是我们使用调整大小的新实现。

大部分代码都是一样的，

我们仍然要确定它是否包含

值了。

如果没有，我们就会找出是哪个桶

应该进入和

然后把它添加到那个bucket中，添加到LinkedList中。

但是现在我们增加currentSize字段。

currentSize是记录数字的字段

HashSet中的元素。

我们要增加它，然后我们要看

在平均负荷下，

每个桶的平均元素数。

我们在下面做除法。

我们必须在这里做一点选角来确定

我们得到了一个double。

然后，我们将平均载荷与电场进行比较

我设置为

0.75，例如，当我创建这个HashSet时

负载系数。

如果平均负载大于loadFactor，

这意味着每个桶上有太多的元素

平均，我需要重新插入。

这是我们对重新插入方法的实现

所有的元素。

首先，我将创建一个名为oldBuckets的局部变量。

这是指现在的桶吗

在我开始调整大小之前。

注意，我还没有创建一个新的链表数组。

我只是把桶重命名为oldBuckets。

现在记住水桶是我们课上的一个领域，我要走了

现在创建一个新数组

但是这个有两倍的元素

就像第一次一样。

现在我需要重新插入，

我要遍历所有的旧桶。

oldBuckets中的每个元素都是字符串的LinkedList

那是一个桶。

我将遍历这个桶，得到其中的每个元素

桶。

现在我要把它重新插入到newBuckets中。

我将得到它的hashCode。

我就能算出它是哪个下标。

现在我得到了新的桶，新的LinkedList

字符串和

我会把它添加到新桶中。

概括一下，哈希集是Linked的数组

列表或桶。

一个自调整大小的HashSet可以使用一些比例或

小开

对于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