很多知识点在第一次学习时往往容易被忽略，笔者也是在重新梳理 HashMap 原理的时候，才发现其中有不少值得深入研究的问题，而这些问题追根溯源，最终常常会回到数学层面。比如：HashMap 的加载因子为什么是 0.75？
本文主要围绕以下几个问题展开：
- 为什么 HashMap 需要加载因子？
- Hash 冲突有哪些常见解决方法？
- 为什么加载因子通常选择 0.75，而不是 0.8 或 0.6？
为什么HashMap需要加载因子？
HashMap 的底层本质上是哈希表（散列表），它是一种用于存储键值对的数据结构。数据在哈希表中的存储位置，需要通过一定的哈希计算来确定：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// AbstractMap
public int hashCode() {
int h = 0;
Iterator> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
} 常见的数据结构通常很难同时兼顾查询效率和插入效率，不是查询快，就是插入快。HashMap 可以看作是一种查询效率较高、但底层维护成本并不低的数据结构。
不过，这类结构也很容易面临两类典型问题：① 如果空间利用率过高，那么经过哈希算法计算存储位置时，会发现很多位置已经被占用，从而产生哈希冲突；② 如果为了尽量减少哈希冲突而持续增大数组容量，又会造成空间利用率偏低，带来内存浪费。
而加载因子，正是用来衡量 Hash 表中元素填充程度的重要参数。
加载因子 = 填入表中的元素个数 / 散列表的长度
加载因子越大，表示表中填入的元素越多，空间利用率越高，但同时发生哈希冲突的概率也会更高；
加载因子越小，表示元素更稀疏，冲突概率会降低，但空间浪费会更明显，而且还可能增加扩容与 rehash 的次数。
冲突概率越高，就意味着查找目标数据时更可能需要经过额外路径，例如遍历链表或树结构，这会直接提高查询成本。因此，在“冲突概率”和“空间利用率”之间，必须找到一个合理的平衡点。
所以我们也可以总结出，影响哈希表查找效率的因素主要包括以下几类：
- 哈希函数是否能够将数据尽可能均匀地分布到哈希表中？
- 发生哈希冲突后采用什么方式处理？
- 哈希表的加载因子应该如何选择？
本文重点介绍后两个问题。
解决冲突有什么方法？
1. 开放定址法
Hi = (H(key) + di) MOD m，其中i=1,2,…,k(k<=m-1)H(key)为哈希函数，m为哈希表表长，di为增量序列，i为已发生冲突的次数。其中，开放定址法根据步长不同可以分为3种：
1.1 线性探查法（Linear Probing）：di = 1,2,3,…,m-1简单来说，就是从当前发生冲突的位置开始，以步长为 1 向后循环查找，直到找到一个空槽位。如果整张表都探查完仍然没有空位，就说明容器已经满了。打个比方，就像你在饭点出门找餐馆吃饭，沿着街道一家一家询问是否还有空位。
1.2 平方探测法（Quadratic Probing）：di = ±12, ±22，±32，…，±k2（k≤m/2）与线性探查法相比，平方探测法的步长按 di = i2 变化，通过平方增长的方式继续寻找空位置。继续沿用上面的例子，这就不是一家一家去看了，而是先算出第 i2 家店，再去询问有没有位置。
1.3 伪随机探测法：di = 伪随机数序列这种方式则是用伪随机数作为探查步长。还是以找餐馆为例，这次你不再按顺序或固定规律寻找，而是比较随机地挑一家店询问是否有座位。
不过，开放定址法也存在一些明显缺点：
当冲突较多时，元素容易出现聚集现象，不利于后续查找操作。而且在删除节点时，不能直接把该位置清空，否则会破坏之后元素的探查路径，导致查找失败。因此，删除时通常只能打“删除标记”，而不能真正移除节点。另外，如果哈希表空间已经装满，还需要额外建立溢出表来存储后续元素。
2. 再哈希法
Hi = RHi(key), 其中i=1,2,…,kRHi()函数是不同于H()的哈希函数，用于同义词发生地址冲突时，计算出另一个哈希函数地址，直到不发生冲突位置。这种方法不容易产生堆集，但是会增加计算时间。
因此，再哈希法最大的缺点就是：会增加额外的计算开销。
3. 建立一个公共溢出区
假设哈希函数的值域为[0, m-1]，设向量HashTable[0,…,m-1]为基本表，每个分量存放一个记录，另外还设置了向量OverTable[0,…,v]为溢出表。基本表中存储的是关键字的记录，一旦发生冲突，不管他们哈希函数得到的哈希地址是什么，都填入溢出表。
这种方法的缺点也很明显：在查找发生冲突的数据时，往往需要额外遍历溢出表，查找效率会受到影响。
4. 链地址法（拉链法）
将冲突位置的元素组织成链表。在插入数据时，如果哈希地址与哈希表中已有元素发生冲突，就将新元素挂到该位置对应的链表上。
拉链法的优点：
处理冲突的方式比较直接，而且不会出现明显的堆集现象，非同义词之间通常不会发生地址冲突，因此平均查找长度相对较短；同时，由于拉链法中各链表节点的空间是动态申请的，所以更适合在建表前无法准确确定表长的场景；此外，删除节点也较容易实现，只需删除链表中的对应节点即可。拉链法的缺点是：需要额外的存储空间。
从 HashMap 的底层结构可以看出，HashMap 采用的是数组 + 链表 / 红黑树的组合结构，也就是通过哈希桶配合链地址法来处理冲突。
为什么HashMap加载因子一定是0.75？而不是0.8，0.6？
从上文可知，HashMap 的底层本质上也是哈希表，而它处理冲突的主要方式是链地址法。HashMap 的默认初始容量是 16。为了降低冲突概率，当 HashMap 的数组长度达到某个临界值时，就会触发扩容，并将所有元素重新进行 rehash 后放入新的更大容器中，而这个过程是比较耗时的。
这个临界值由加载因子和当前容量共同决定：
临界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR
也就是说，在默认情况下，当容量为 16、加载因子为 0.75 时，阈值就是 16 x 0.75 = 12，达到 12 个元素后就会触发扩容。
那么，为什么 HashMap 默认选择 0.75 作为加载因子？这与统计学中一个非常重要的原理——泊松分布有关。
泊松分布是统计学和概率论中常见的一种离散概率分布，适合描述单位时间内随机事件发生次数的概率情况。有兴趣的读者可以参考维基百科，或者阮一峰老师的文章《泊松分布和指数分布：10分钟教程》[1]
等号左侧中，P 表示概率，N 表示某种函数关系，t 表示时间，n 表示数量；等号右侧中，λ 表示事件发生的频率。
在 HashMap 源码中，有这样一段注释：
* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (https://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on a verage 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这段注释的意思是：在理想情况下，如果哈希码分布足够随机，那么在默认扩容阈值（加载因子）为 0.75 时，哈希桶中节点数量的分布大致符合参数平均值为 0.5 的泊松分布。忽略方差的情况下，即 X = λt，P(λt = k)，其中 λt = 0.5，按照公式：
计算结果正如上面列出的概率值所示。当某个 bin 中链表长度达到 8 个元素时，其概率仅为 0.00000006，几乎可以看作极小概率事件。
因此可以看出，常数 0.5 是作为参数带入泊松分布进行计算的，而加载因子 0.75 则是一个重要前提条件：当 HashMap 的使用程度达到扩容阈值时，在这种设定下，冲突后的链表长度及其概率分布如下：
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那么为什么不可以是0.8或者0.6呢？
在 HashMap 中，除了哈希算法本身之外，还有两个关键参数会直接影响性能：初始容量和加载因子。初始容量表示哈希表创建时的桶数量，加载因子则表示哈希表在自动扩容之前，允许装载到多满的程度。
维基百科中对加载因子的描述大致是这样的：
对于开放定址法来说，加载因子是非常关键的参数，通常需要严格控制在 0.7 - 0.8 以下。一旦超过 0.8，查表时 CPU 缓存未命中（cache missing）的情况可能会明显上升。也正因为如此，像 Java 系统库中一些采用哈希思想的数据结构，会把加载因子限制在 0.75 左右，一旦超过该阈值，就触发 resize 扩容操作。
在设置初始容量时，应该结合预估的元素数量以及加载因子综合考虑，这样才能尽量减少扩容和 rehash 的次数。因此，在实际开发中，通常建议在使用 HashMap 时根据业务预估值设置合适的初始容量，以减少不必要的扩容成本。
归根结底，选择 0.75 作为 HashMap 默认加载因子，本质上是在时间成本和空间成本之间做出的一种经验性折中，也是性能与内存占用之间较为合理的平衡选择。
