在哈希地图中，我们如何获得桶被空的概率为0.5

Question

Java官方文件说：“理想情况下，在随机的哈希码中，垃圾箱中的节点的频率遵循泊松分布（），默认调整大小为0.75”的参数平均约为0.5。我想知道我们如何使桶被空为0.5。如何数学证明它。

Answer 1

这是关于0.5可能来自何处的讨论。

上下文在Java Hashmap 实现中，就应该将链接（“树”）从链接列表转换为红黑树的点。这应该在典型的操作下很少发生。选择“极少”的好价值是什么？ Hashmap实施中的实施评论基于泊松分布的理由：

 Ideally, under random hashCodes, the frequency of
 nodes in bins follows a Poisson distribution
 (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 parameter of about 0.5 on average for the default resizing
 threshold of 0.75, although with a large variance because of
 resizing granularity. Ignoring variance, the expected
 occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 factorial(k)).

https://github.com/openjdk/jdk/jdk/blob/jdk-17-ga/src/src/java/java.base/share/share/classes/java/java/java/util一下/hashmap.java#l181

它得出的结论是，具有8个或更多碰撞的桶发生，概率少于一千万分之一，因此选择8个被选为“ Treeify Threshold”。

0.5的参数从何而来？在这种情况下，参数是指哈希图的平均负载（或填充度），即映射的数量除以“容量”（表长度或存储桶的数量）。因此，问题可以重述为：hashmap的平均负载是多少？这不能从数学上得出，因为它取决于程序使用hashmap，程序的输入等的方式。但是我们可以做出一些合理的假设，并得出一些可能适用于典型情况的结论。

• 首先，假设大多数哈希图使用的负载系数为0.75。我认为这是真的，因为我很少看到代码使用明确的负载因子的情况。

• 第二，假设哈希图中的映射数量均匀分布。我几乎很肯定这是不是 true，但让我们从此开始作为一个工作的假设开始，然后重新审视它。

• 第三，让我们搁置hashmap包含超过十亿个元素的案例，其中诸如Java的数组尺寸限制之类的元素。

• 第四，为简单起见，让我们仅考虑在没有预先关联容量的情况下创建的hashmaps，并带有一些未知数的映射。

回想负载因子的定义：如果hashmap的负载超过了负载因子，则将施加尺寸更大，以使负载保持在负载因子以下。

显然，正常操作中的哈希图的负载不能超过0.75。哈希图的负载也不会小于0.375，因为它直到负载达到0.75，并调整了一半的负载大小。因此，也许平均载荷中途在0.375至0.75之间，即0.5625。

可以做一些数学来弄清楚这一点，但是我更容易编写一个程序来填充1和n之间的尺寸的标签，并计算所有这些情况下的平均负载。如果N大约是两个功率的0.75（例如768），则平均负载确实接近0.5625。但是，这取决于n的选择，这有很大不同。如果选择的n在两个连续的幂之间的中间位置（例如576），则平均负载仅为0.507。 最多N映射的平均施法负载在约0.507和0.5625之间变化。

因此，根据n的选择， 。这可能不是真的，但是实际分布是​​什么？我不知道，但是我想随着尺寸变大，有指数级的损坏。如果是这样，这将使大小的分布偏向较小的数量，将平均负载降低到比0.5625的0.507偏差。我还猜测，很多人都会用默认容量（16）创建哈希图，并用六个或更少的映射填充它们。那将使平均水平降低。

总而言之，我们的模型告诉我们，平均负载在0.507和0.5625之间。一些受过良好教育的猜测告诉我们，尺寸的偏差较小，因此平均负载也较小。因此，0.5的选择似乎是合理的。

但是，我们真的不需要精确的答案来分析何时treehmap bucket。分析的目的是找到一个阈值，以便在正常运行期间不太可能发生转换。如果使用0.4或0.7而不是0.5，则泊松分析仍表明，一个桶中有8次碰撞的机会仍然少于一千万分之一。