起初看 hashmap 源码的时候，最让我困惑的中央就是这里。置信很多人也有过这样的问题，置信很多人和我一样也是网上百度了一通，置信很多人和我一样百度，google 一通后，答案就那么几个而后就默认了是对的了，然而实际上还是没有懵逼的认为懂了。这篇文章就来聊聊这 0.75。

答复 1：代码正文

这是 jdk1.7 源码上的正文

As a general rule, the default load factor (.75) offers a good tradeoff between time 
and space costs. Higher values decrease the space overhead but increase the lookup
cost (reflected in most of the operations of the HashMap class, including get
and put).The expected number of entries in the map and its load factor should be
taken into account when setting its initial capacity, so as to minimize the number 
of rehash operations. If the initial capacity is greater than the maximum 
number of entriesdivided by the load factor, no rehash operations will ever occur.

大略意思就是：一般而言，默认负载因子为 0.75 的时候在工夫和空间老本上提供了很好的折衷。太高了能够缩小空间开销，然而会减少查找复杂度。咱们设置负载因子尽量减少 rehash 的操作，然而查找元素的也要有性能保障。

网上通天彻尾的根本都是这个舆论，毕竟官网的正文。只是这正文答复的未免也太过搪塞，就像我加粗的那 4 个字：“一般而言”。？(╯~Д~)╯╘═╛这个 0.75 的起因就是因为一个一般而言？这显然不够让人服气。所以很多小伙伴也就持续深究上来了。（留神加粗的字体，很鸡肋，然而却有很强的提示性）

这种答复就是：“嗯，你说的很有情理样子，也没什么错，然而为什么是 0.75 呢？这数怎么就进去了呢？”

答复 2：看了正文没过脑子，瞎扯淡

这是网上风行的第二个风行版本了，也来自官网，不过是 jdk1.8 的。

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins.  In
usages with well-distributed user hashCodes, tree bins are
rarely used.  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

简略翻一下：

因为 TreeNode 的大小约为链表节点的两倍，所以咱们只有在一个拉链曾经拉了足够节点的时候才会转为 tree（参考 TREEIFY_THRESHOLD）。并且，当这个 hash 桶的节点因为移除或者扩容后 resize 数量变小的时候，咱们会将树再转为拉链。如果一个用户的数据他的 hashcode 值散布非常好的状况下，就会很少应用到 tree 构造。在现实状况下，咱们应用随机的 hashcode 值，loadfactor 为 0.75 状况，只管因为粒度调整会产生较大的方差，桶中的 Node 的散布频率遵从参数为 0.5 的泊松散布。上面就是计算的后果：桶里呈现 1 个的概率到为 8 的概率。桶外面大于 8 的概率曾经小于一千万分之一了。

这个货色因为来自 jdk1.8，而且提到了 0.75，没有好好了解这段话的意思的话，很容易就认为这是在阐释 0.75 是怎么来的，而后就简略的把泊松散布给强关联到了 0.75 下来。然而，这段话的本意其实更多的是示意 jdk1.8 中为什么拉链长度超过 8 的时候进行红黑树转换。这个泊松散布的模型其实是基于曾经默认因子就是 0.75 的模型去模仿演算的。

我其实很长一段时间也认为这就是标准答案了，尽管不懂，然而当前有人问间接甩他一个泊松散布就行了，直到 – 我忘了泊松散布的知识点了????。其实也好了解，红黑树是 1.8 之后加进来的，所以 jdk 源码者并没有顺便为咱们解释下为啥过后设计了 0.75，而是更多是想解释一些对于退出红黑树之后一些设计的起因。

比拟靠谱的答复

其实很快乐有人能开掘到这里，我也认为这能够解答我这个问题了。

https://stackoverflow.com/que…

这是 stackoverflow 上的一个帖子。Answers 中 top1 其实就是最原始的答复，top2 用了数学的一套实践推演出了 log(2)，而后来近似于 0.75。我认为找到了真谛，惋惜写的太潦草了，没看懂这些公式列举进去别离代表的意义。起初网上找到一篇有人具体推演了计算过程，能够参考参考，说的也不是很分明，然而相对来说还是有很大的借鉴意义的。不否定，该思路的亮点将问题转变为了碰撞的概率问题。

惟一我存在疑难的点，就是这种概率问题真的遵从二项分布吗？我本人给本人解释感觉也说的通，感觉也说不通。

总结，我的答案 1

首先咱们理解下概率论的相干货色（自己大学概率论没学好，选修课，还是早上的课，所以你懂得。）

二项分布

• 什么是二项分布

  • 在做一件事件的时候，其后果的概率只有 2 中状况，和抛硬币一样，不是侧面就是背面。这些试验做了 n 次，其所有胜利的 case 离散概率的散布。

• 个性

  • 在每次试验中只有两种可能的后果
  • 每次试验是独立的，不同试验之间互不影响
  • 每次试验胜利的概率都是一样的

• 公式

  • $binom(n,k) = C_n^k \times (p)^k \times (1 – p)^{n – k} $
  • n 为试验的次数，k 为胜利的次数。下面公式就是形容该胜利概率为 p 的状况下，n 次试验，k 次胜利的概率为多少。

更具体的二项分布的内容，不懂的能够去学习下相干内容。

hashmap 的二项分布

那么，这个和咱们的这个负载因子有什么关系呢？咱们先针对一下个性，来做一下思路的转换类比：

• 试验只有 2 种后果

  • 咱们往 hash 表 put 数据能够转换为 key 是否会碰撞？碰撞就失败，不碰撞就胜利。

• 试验互相独立

  • 咱们能够构想，试验的 hash 值是随机的，并且他们通过 hash 运算都会映射到 hash 表的长度的地址空间上，那么这个后果也是随机的。所以，每次 put 的时候就相当于咱们在扔一个 16 面（咱们先假如默认长度为 16）的骰子，扔骰子试验那必定是互相独立的。碰撞产生即扔了 n 次有呈现反复数字。

• 胜利的概率都是一样的

  • 这就是我难以了解的中央，这个中央能够说的过来，也能够说不过去。

  • 说的过来

    • 每次一 put 的后面的地位咱们不晓得会在哪！可能后面始终都在一个地位上，那么咱们实践上的概率始终都是 $\frac{1}{16}$。咱们能够权且形象的认为概率 p 为 $\frac{1}{s}$（设长度为 s）。
    • 须要阐明的是：这里我并不确定是否正当，这也是过程中我认为不太谨严的中央。

  • 说不过去

    • 然而每次扔的大可能不会在同一个地位上，所以概率每次都会不一样，然而这个不一样又是咱们无法估量和猜想的。

而后，咱们的目标是啥呢？

就是掷了 k 次骰子，没有一次是雷同的概率，须要尽可能的大些，个别意义上咱们必定要大于 0.5（这个数是个现实数，然而我是能承受的）。

于是，n 次事件外面，碰撞为 0 的概率，由下面公式得：

$$
\begin{aligned}
binom(n,0) & = C_n^0 \times (\frac{1}{s})^0 \times (1 – \frac{1}{s})^{n – 0} = (1 – \frac{1}{s})^n &
\end{aligned}
$$

这个概率值须要大于 0.5，咱们认为这样的 hashmap 能够提供很低的碰撞率。所以：

$$
(1 – \frac{1}{s})^n \ge \frac{1}{2}
$$

这时候，咱们对于该公式其实最想求的时候长度 s 的时候，n 为多少次就应该进行扩容了？而负载因子则是 $n/s$ 的值。所以推导如下：

$$
\begin{aligned}
n\ln(1 – \frac{1}{s}) & \ge -\ln2 ····两边取对数 \\
n & \le \frac{-\ln2}{\ln(1 – \frac{1}{s})} \rightarrow n \le \frac{\ln2}{\ln\frac{s}{s-1}} ····提取 n \\
\frac{n}{s} & \le \frac{\ln2}{s\ln\frac{s}{s-1}} ····两边除以 s \end{aligned}
$$

所以能够失去

$$
\begin{aligned}
loadFactor & = \lim_{s \to \infty}\frac{\ln2}{s\ln\frac{s}{s-1}} \end{aligned}
$$

其中

$$
\begin{aligned}
\lim_{s \to \infty}s\ln\frac{s}{s-1}
\end{aligned}
$$

这就是一个求 $$\infty \cdot 0$$ 函数极限问题，这里咱们先令 $s = m+1（m \to \infty）$ 则转化为

$$
\begin{aligned}
\lim_{m \to \infty}(m+1)\ln(1+\frac{1}{m})
\end{aligned}
$$

咱们再令 $x = \frac{1}{m}（x \to 0）$ 则有，

$$
\begin{aligned}
\lim_{s \to \infty}s\ln\frac{s}{s-1} & = \lim_{x \to 0}（\frac{1}{x}+1）\ln(1+x) \\
&= \lim_{x \to 0}（\frac{1}{x}+1）x ····无穷小等价替换有 \ln(1 + x) \sim x（证实去百度）\\
&= \lim_{x \to 0}(1+x) \\
& \sim 1
\end{aligned}
$$

所以，

$$
\begin{aligned}
loadFactor & = \lim_{s \to \infty}\frac{\ln2}{s\ln\frac{s}{s-1}} \\
&\sim \ln2 \\
& \sim 0.693
\end{aligned}
$$

这也就是为什么 stackoverflow 上说靠近于 ln2 的起因了。而后再去思考 hashmap 一些内置的要求：

• 乘 16 能够最好一个整数。

那么在 0.5~1 之间找一个小数，满足这要求的只有 0.625（5/8），0.75（3/4），0.875（7/8）。这三个数让我选，从审美角度，还是从 中位数 角度，我都会挑 0.75。毕竟碰撞是个概率问题，这个 0.75 我感觉不错，我没方法预知使用者的数据到底什么样子的，0.75 是最为折中的一个抉择。

我的答案 2

当时申明，我否定了下面的一些答案，不代表我就很反对我总结的答案 1，很坦率的说，我目前的认识还是保留着这只是作者的一个心理掂量进去的一个值的猜测。只是下面的那个答案 1 目前还算能让我心里把本人说得过去的。

我猜测兴许从源头上，就是最原始的答复上咱们被误导了，总感觉这个 0.75 不是简简单单来了，就感觉这个数肯定是通过某种数理逻辑推演出来的。能够像下面那个答复一样能够用公式完满的一步步能够推算出来。然而，事实呢？咱们从设计者的角度复演一下过后设计者的思考：

如果要设值，这个值，在心理正当的范畴应该是 0.5~1 之间的某个数。起因很简略：

• 小于 0.5，空着一半就扩容了，这在心理上很多人都会感觉不合理吧，空间必定会很节约。
• 然而如果是 1 的话，只能说有超级大的概率，会产生碰撞，这不合乎咱们的初衷。

而后就为什么是 0.75 呢？我的猜测是这样：过后因为曾经设置了 hash table 的长度为 16。其实负载因子并不重要，重要的其实是那个阈值。负载因子也是为了计算那个阈值的。下面也提到了 0.5~1 之间找一个小数，乘 16 能够是一个整数时候 0.75 很适合。（这也正如 1.7 正文外面说的。所以兴许作者也没法和咱们精确交代 0.75 到底怎么来的，无妨换位思考下，如果这个 0.75 是你通过精细推演得进去的数字，正文必定会具体解释阐明，怎么可能 ” 一般而言 ” 就简略带过了呢？）

所以我还是保留这个答案 2，这个数字就是作者感觉差不多满足他想要的一些条件，感觉上也差不多的一个值，不会太节约空间，也不会高碰撞概率。并且这是一个调优参数，用户能够依据本人的数据去动静调整这些参数来实现最优。所以就设了个这么个值。

但还是要提一下：

C# 中的相似于 Java 的 HashMap 的类叫 HashTable，而它的负载因子是 0.72。这也是让我为什么始终要钻这个牛角尖的次要起因。取的数不同只是类似，这个数必定没那么简略。

总结

这个问题，困扰了我很久，其实每次回头看 hashmap 的时候，我都会想这个问题，也和四周的人探讨过，失去的答复根本是：” 不要转牛角尖 ”，” 面试问这个就太过分了 ”，”” 晓得有啥用，记住数字就行 ”。可是不明所以，就如鲠在喉，心愿这文章能够帮忙和我有同样的感觉的人，也心愿有什么异议能够通知我。

其实几个答复剖析下来，发现整个过程是：简略→简单→简略的过程。如果面试我间接答复最初一个的论断，我感觉面试官也听的很没劲。须要一步步趟过去，这种返璞归真才有意思。

当然，对这个问题，也的确可能没必要转这牛角尖。就和探讨 P 和 NP 问题一样，能够探讨，没理论多大意义。没准就如我所猜测，就是作者心理选了这么个数字呢？特地是网上看到的一些乌七八糟，逻辑都站不住脚的答复，我感觉就是有点强行了。好像世间所有的因果必是很强的逻辑性，没有因果就乱设因果，容易造成就是硬造也要造一个让本人称心的答案（这在学术圈不足为奇：很多从根上错的货色含糊其辞的说过来了，就开始持续往下推演）。

最初还是要提一句，如果你真的有紧密的推演逻辑，还请通知我。

援用

还是感激下，没有 2 篇文章，我可能很长时间都无从下手。

https://stackoverflow.com/que…

HashMap 的 loadFactor 为什么是 0.75)