Java 我们如何获得哈希图中桶为空或不为空的概率为0.5

下面讨论0.5可能来自何处.

上下文在Java HashMap实现中，关于bucket应该从链表转换("树化")到红黑树的点.在典型操作下，这种情况极少发生.什么是一个好的价值 Select ，使"极为罕见"？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/blob/jdk-17-ga/src/java.base/share/classes/java/util/HashMap.java#L181

它得出结论，一个有8次或8次以上碰撞的桶发生的概率小于千万分之一，因此 Select 8作为"树阈值".

0.5的参数来自哪里？在这种情况下，该参数表示HashMap的平均负载(或完整性)，即映射数除以"容量"(表长度或桶数).因此，这个问题可以重新表述为:HashMap的平均负载是多少？这不能从数学上推导出来，因为它取决于程序使用哈希映射的方式、程序的输入等等.但我们可以做出一些合理的假设，得出一些可能适用于典型 case 的结论.

• 首先，假设大多数哈希映射使用0.75的负载因子.有趣的是，我相信这是真的，因为我很少看到代码使用显式负载因子的情况.

• 其次，假设HashMap中的映射数是均匀分布的.我几乎可以肯定这是not真的，但让我们从这一工作假设开始，稍后再重新讨论.

• 第三，让我们把HashMap包含超过十亿个元素的情况放在一边，比如Java的数组大小限制.

• 第四，为了简单起见，让我们只考虑在没有预先分配容量的情况下创建的hashmap，并且这些hashmap中填充了一些未知数量的映射.

回想一下负载因子的定义:如果HashMap的负载超过负载因子，则HashMap的大小将更大，以保持负载低于负载因子.

显然，正常操作中的HashMap的负载不能超过0.75.HashMap的负载也不会小于0.375，因为在负载达到0.75之前，它不会调整大小，而调整大小会使负载减半.因此，平均载荷可能介于0.375和0.75之间，即0.5625.

人们可以做一些数学运算来解决这个问题，但对我来说，编写一个程序来填充大小在1到N之间的哈希图并计算所有这些情况下的平均负载更容易.如果N大约是2的幂的0.75(比如768)，那么平均负载实际上非常接近0.5625.然而，这取决于人们对N的 Select .如果 Select 的N介于两个连续幂次的0.75(例如576)之间，则平均负载仅为0.507.因此，最多有N个映射的HashMaps的平均负载在0.507到0.5625之间变化，这取决于对N的 Select .(这是注释中提到的"调整粒度"变化.)

回想一下，我们假设HashMap大小是均匀分布的.这可能不是真的，但实际分布情况如何？我不知道，但我猜随着尺寸的增大，会出现指数衰减.如果是这样的话，这将使尺寸分布向较小的数字倾斜，从而将平均载荷降低到接近0.507而不是0.5625.我还猜测，许多人创建了具有默认容量(16)的哈希映射，并用六个或更少的映射填充它们.这将进一步拉低平均值.

总之，我们的模型告诉我们，平均负荷在0.507到0.5625之间.一些有根据的猜测告诉我们，尺寸偏差较小，因此平均载荷也较小.因此， Select 0.5似乎是合理的.

但我们真的不需要一个精确的答案来分析何时树化HashMap存储桶.分析的目的是找到一个阈值，以便在正常操作期间极不可能发生转换.如果使用0.4或0.7代替0.5，泊松分析仍将表明，单个铲斗中发生8次碰撞的可能性仍然小于千万分之一.