无法理解 Sun 文档中哈希表的泊松部分

hashmap java poisson

2022-09-04 03:02:25

我试图理解HashMap是如何在Java中实现的。我决定尝试理解该类的每一行（代码和注释），显然我很快就会遇到阻力。以下片段来自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)). The first values are:
 0:    0.60653066
 1:    0.30326533
 2:    0.07581633
 3:    0.01263606
 4:    0.00157952
 5:    0.00015795
 6:    0.00001316
 7:    0.00000094
 8:    0.00000006
 more: less than 1 in ten million

我是数学界的普通人，首先必须了解泊松分布是什么。感谢向我解释的简单视频。

现在，即使在了解了如何使用泊松计算概率之后，我也无法理解上面描述的内容。

如果可能的话，有人可以用更简单的语言和例子来解释这一点吗？这将使我的任务更加有趣。

答案 1

HashMap根据要插入的元素的哈希代码组织为“存储桶”数组。每个存储桶（默认情况下）都是元素的链接列表。每个存储桶将具有非常少的元素（理想情况下，最多只有一个），因此查找特定元素几乎不需要搜索链表。

举一个简单的例子，假设我们有一个容量为4的HashMap和0.75的负载因子（默认值），这意味着在调整大小之前它最多可以容纳3个元素。将元素理想地分布到存储桶中，如下所示：

bucket | elements
-------+---------
     0 | Z
     1 | X
     2 |
     3 | Y

因此，无需在存储桶中进行任何搜索即可立即找到任何元素。另一方面，元素分布非常差，如下所示：

bucket | elements
-------+---------
     0 | 
     1 | Z -> X -> Y
     2 |
     3 |

如果所有元素碰巧都散列到同一存储桶中，则会发生这种情况，因此搜索元素Y将需要向下遍历链表。

这似乎没什么大不了的，但是如果你有一个容量为10，000个元素的HashMap，并且在链接列表上的单个存储桶中有7，500个元素，那么搜索特定元素将降级为线性搜索时间 - 这就是使用HashMap试图避免的。

一个问题是，用于将元素分发到存储桶中的哈希码是由对象本身决定的，而对象的哈希码实现并不总是很好。如果哈希码不是很好，那么元素可能会堆积在某些桶中，HashMap将开始表现不佳。

代码中的注释是讨论每个存储桶中出现不同长度的链接列表的可能性。首先，它假设哈希码是随机分布的 - 情况并非总是如此！- 我认为它还假设HashMap中的元素数量是桶数量的50%。在这些假设下，根据泊松分布，60.6%的桶将是空的，30.3%将具有一个元素，7.5%将具有两个元素，1.2%将具有三个元素，依此类推。

换句话说，给定这些（理想）假设，每个桶中的链接列表通常非常短。

在JDK 8中，有一个优化，将链表变成超过一定阈值大小的树，因此在最坏的情况下，性能至少会降低到O（log n）而不是O（n）。问题是，应该选择什么值作为阈值？这就是本次讨论的全部内容。TREEIFY_THRESHOLD的当前阈值为 8。同样，在这些理想假设下，链表长度为 8 的存储桶在 0.000006% 的时间内仅出现。因此，如果我们得到一个那么长的链接列表，那么显然有些地方并不理想！例如，这可能意味着存储的对象具有异常糟糕的哈希码，因此HashMap必须从链表切换到树，以避免过度的性能下降。

带有相关注释的源文件的链接在这里：

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b119/src/share/classes/java/util/HashMap.java

答案 2

被接受的答案很好，但我只想填写为什么特别使用泊松分布是合理的，因为我在阅读那段代码时遇到了完全相同的问题。

如果我们将固定数量的项目插入到固定数量的存储桶中，则固定存储桶中的项目数量应遵循二项式分布，并进行试验和成功概率。这很容易看到;如果哈希是随机的，那么每个项目都以概率被放入我们的桶中，并且有项目。knk1 / n1 / nk

当为大且二项分布的均值较小时，则良好的近似值是具有相同均值的泊松分布。在这种情况下，均值是，哈希表的负载因子。取 0.5 作为平均值是合理的，因为在调整大小之前，表最多允许 0.75 的负载因子，因此在负载因子约为 0.5 的情况下，该表将大量使用。kk / n