Mus*_*afa 12 java hashmap poisson
我试图了解如何在Java中实现HashMap.我决定尝试理解该课程的每一行(代码和评论),显然我很快就遇到了阻力.以下代码片段来自HashMap类,并讨论泊松分布:
- 理想情况下,在随机hashCodes下,频率为
- 箱中的节点遵循泊松分布
- (http://en.wikipedia.org/wiki/Poisson_distribution)带有
- 默认大小调整的平均参数约为0.5
- 阈值为0.75,虽然因为有很大的差异
- 调整粒度.忽略方差,预期
- 列表大小k的出现是(exp(-0.5)*pow(0.5,k)/
- 阶乘(K)).第一个值是:*
- 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
- 更多:不到千万分之一
我是数学中的普通人,必须先了解泊松分布是什么.感谢简单的视频向我解释.
现在,即使了解了如何使用Poisson计算概率,我也无法理解上面描述的内容.
有人可以用更简单的语言解释一下,如果可能,请举例说明吗？这将使我的任务更有趣.
提前致谢
根据要插入的元素的hashCode,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试图避免的是什么.
一个问题是用于将元素分配到桶中的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%的时间.所以,如果我们得到一个很长的链表,那显然是不理想的!! 例如,这可能意味着存储的对象具有异常错误的hashCodes,因此HashMap必须从链表切换到树,以避免过度的性能下降.
带有相关评论的源文件的链接在这里:
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b119/src/share/classes/java/util/HashMap.java