HashMap中加载因子的意义是什么？

HashMap有两个重要的属性：大小和负载因子。 我浏览了Java文档，它说0.75f是最初的加载因子。 但是我找不到它的实际用途。 有人可以描述什么是我们需要设置负载因子的不同场景，以及不同情况下的一些示例理想值？

Answer 1

文档解释得非常好：

HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子。 容量是哈希表中桶的数量，初始容量就是哈希表创build时的容量。 加载因子是散列表在其容量自动增加之前被允许得到的度量。 当哈希表中的条目数量超过了负载因子和当前容量的乘积时，散列表就被重新映射（即内部数据结构被重build），这样散列表大约有两个桶的数量。

一般来说，默认加载因子（.75）提供了时间和空间成本之间的良好折衷。 较高的值会减less空间开销，但会增加查找开销（反映在大部分HashMap类的操作中，包括get和put）。 在设置初始容量时，应该考虑映射中的条目数目及其负载因子，以尽量减less重新操作的次数。 如果初始容量大于最大入口数除以负载因子，则不会发生重新刷新操作。

与所有的性能优化一样，避免过早优化（比如，没有关于瓶颈位置的硬数据）是一个好主意。

Answer 2

HashMap默认初始容量为16，加载因子为0.75f（即当前地图大小的75％）。 负载因子表示HashMap容量应该加倍的级别。

例如容量和负载因数乘积为16 * 0.75 = 12 。 这表示在将第12个键 – 值对存储到HashMap ，其容量变为32。

Answer 3

实际上，从我的计算结果来看，“理想”负荷系数更接近log2（〜0.7）。 尽pipe任何小于这个的加载因子都会产生更好的性能。 我认为.75很可能是从帽子里拿出来的。

certificate：

通过预测桶是否为空，可以避免链接并利用分支预测。 如果空桶的概率超过0.5，那么桶可能是空的。

让我们表示大小和添加的键的数量。 使用二项式定理，桶被清空的概率是：

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

Answer 4

从文档 ：

加载因子是散列表在其容量自动增加之前被允许得到的度量

这实际上取决于您的特定要求，没有“经验法则”来指定初始加载因子。

Answer 5

什么是加载因子？

HashMap为了增加容量而耗尽的容量？

为什么加载因子？

负载因子默认是初始容量的0.75（16），因此在容量增加之前，有25％的桶将是空闲的，并且这使得许多具有新的哈希码的新桶在其增加之后存在桶数。

现在为什么要保留很多免费的存储空间，保持免费的存储空间对性能有什么影响？

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

假设你将一个对象x添加到你的hashCode的hashCode是888＆在你的hashmap中，表示hashcode的桶是空闲的，所以对象x被添加到了桶中，但是现在再说一下，如果你添加了另一个hashCode为y的对象也就是888，那么你的对象y肯定会被添加到桶的末尾（ 因为桶只是linkedList的实现存储键，值和下一个 ）现在这有一个性能的影响！ 由于你的对象y不再出现在桶的头部，如果你执行查找，所花费的时间不会是O（1），这次取决于同一个桶中有多less物品。 这就是所谓的哈希碰撞的方式，这甚至发生在你的加载因子小于1时。

性能，哈希碰撞和加载因子之间的相关性？

更低的负载率 =更多的空闲桶= 更less的碰撞机会 =高性能=高空间需求。

纠正我，如果我错了某个地方。

Answer 6

加载因子不应该从0.75改变，除非你有一些特定的优化，你要做的。 初始容量是你想要改变的唯一东西，并根据你的N值（N / 0.75）+1来设置，或者是在那个区域。 这将确保表格总是足够大，不会发生重新哈希。

Answer 7

我会select一个大小为n * 1.5或n +（n >> 1）的表格，这样可以给出一个不带划分的.66666〜的加载因子，这在大多数系统上是很慢的，尤其是在没有划分的便携式系统上硬件。