面试官：HashMap默认负载因子0.75和泊松分布有关系吗
掘客DIGGKR2020-08-29 12:45
我们在看HashMap源码时，知道HashMap默认的负载因子是0.75。那这个0.75是怎么来的呢？
通常，加载因子需要在时间和空间成本上寻求一种折中。
加载因子过高：例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本。
加载因子过低：例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。
在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数，所以一般在使用HashMap时建议根据预估值设置初始容量，减少扩容操作。
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折中选择
HashMap源码中有段注释，如下：
翻译如下：通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折中。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
有人说负载因子0.75和泊松分布有关系，那是什么关系呢？
在HashMap的源码中有这样一段注释：
泊松分布公式：
0.75作为加载因子，忽略方差，即X = λt，P(λt = k)，其中t=1，λ=0.5，λt = 0.5，带入后：
k=0,1,2…可以得出下表：
可以看到当用 0.75 作为加载因子时，桶中元素到达 8 个的时候，概率已经变得非常小，因此每个位置的链表长度超过 8 个是几乎不可能的，因此在链表节点到达 8 时才开始转化为红黑树。
加载因子是0.75，决定了桶中元素到达 8 个的时候概率很小，进而转为红黑树；而不是到达 8 个的时候概率很小所以加载因子是0.75。
欢迎小伙伴们留言交流~~
举报/反馈
0
0
收藏
分享
