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

Question

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

15

我试图理解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)). 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

我在数学方面是个普通人，必须先理解什么是泊松分布。感谢那个简单的视频向我解释了它。

现在即使我理解如何使用泊松分布计算概率，我仍然无法理解上面所描述的内容。

有人能否用更简单的语言解释一下，并且如果可能的话附带一个例子？这将使我的任务更加有趣。

- Asif

2个回答

2

答案已经很好了，但我想补充一下为什么特别使用泊松分布是合理的，因为当我阅读这段代码时也有同样的问题。

在我们有一个固定数量的项目 k 被插入到固定数量的桶 n 中的情况下，固定桶中的项目数应该遵循二项式分布，其中有 k 次试验和成功概率为 1/n。这很容易理解；如果哈希是随机的，则每个项目以概率 1/n 放入我们的桶中，并且有 k 个项目。

当k很大且二项分布的平均值很小时，一个好的近似值是具有相同平均值的泊松分布。在这种情况下，平均值为k / n，即哈希表的负载因子。将平均值设为0.5是合理的，因为在重新调整大小之前，表最多可以容��0.75的负载因子，所以在负载因子约为0.5时表将被广泛使用。

- mrmcgreg

我认为take 0.5是基于这个假设的：由于哈希冲突，0.25％的项在同一个桶中。你觉得呢？ - Jason

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stuart Marks · Accepted Answer

HashMap是一个基于元素hashCode的“桶”数组组织。每个桶默认情况下都是一个元素的链表。每个桶中应该只有很少的元素（理想情况下最多只有一个），这样查找特定元素时需要搜索链表的次数就非常少。

举个简单例子，假设我们有一个容量为4、负载因子为0.75（默认值）的HashMap，意味着在重新调整大小之前它最多可以容纳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 所要避免的。

一个问题是，用于将元素分配到桶中的 hashCode 是由对象本身决定的，而对象的 hashCode 实现并不总是很好。如果 hashCode 不是很好，则元素可能会聚集在某些桶中，HashMap 将开始表现不佳。

代码中的注释谈论了出现在每个桶中的不同长度的链接列表的可能性。首先，它假设 hashCode 是随机分布的 - 这并不总是正确的！ - 我认为它还假设 HashMap 中的元素数量为桶数量的50％。在这些假设下，根据泊松分布，有 60.6％的桶为空，30.3％的桶只有一个元素，7.5％的桶有两个元素，1.2％的桶有三个元素，依此类推。

换句话说，在这些（理想）假设下，每个桶中的链表通常会非常短。

在 JDK 8 中，有一个优化，可以在超过某个阈值大小的情况下将链接列表转换为树，以便在最坏情况下至少性能下降到 O（log n）而不是 O（n）。问题是，应该选择什么值作为阈值？这就是这个讨论所涉及的内容。当前的阈值 TREEIFY_THRESHOLD 是 8。同样，在这些理想的假设下，具有长度为 8 的链表的桶将仅出现 0.000006％的时间。因此，如果我们得到了这么长的链接列表，显然不太理想！例如，可能意味着被存储的对象具有异常差的 hashCode，因此 HashMap 必须从链接列表切换到树，以避免过度的性能下降。

包含所讨论注释的源文件链接在此：

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