14

我试图了解 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

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

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

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

4

2 回答 2

13

HashMap 根据被插入元素的 hashCode 组织为“桶”数组。每个存储桶（默认情况下）是一个元素的链表。每个桶只有很少的元素（理想情况下，最多一个），因此找到一个特定的元素只需要很少的搜索链表。

举个简单的例子，假设我们有一个容量为 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 试图避免什么。

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

代码中的注释是关于在每个桶中出现不同长度的链表的可能性。首先，它假设 hashCodes 是随机分布的——情况并非总是如此！——而且我认为它还假设 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

于 2013-12-10T03:18:59.780 回答
2

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

如果我们有固定数量的项目k被插入到固定数量的桶n中，那么固定桶中的项目数量应该遵循具有 试验和成功概率的二项分布。这很容易看到；如果哈希是随机的，那么每个项目都有概率放入我们的桶中，并且有项目。k1 / n1 / nk

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

于 2016-09-29T16:55:58.247 回答