HashMap默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？

#### 1. **加载因子的定义** - 加载因子（load factor）是用来衡量 `HashMap` 的数据填充程度的一个参数： \[ \text{加载因子} = \frac{\text{填入哈希表中的数据个数}}{\text{哈希表的长度}} \] - 默认情况下，`HashMap` 的初始容量为 16，默认加载因子为 0.75。这意味着当哈希表填充了 16 × 0.75 = 12 个元素时，会触发扩容。 #### 2. **加载因子的作用** - **加载因子过小**：意味着哈希表中填入的元素较少，减少了哈希冲突的概率，但会浪费大量空间，并频繁触发扩容。 - **加载因子过大**：意味着哈希表中填入的元素较多，空间利用率高，但哈希冲突的概率会增加，导致查找效率下降。 #### 3. **为什么选择 0.75？** - **空间与时间的平衡**：0.75 的加载因子在空间和时间效率上取得了较好的折中。它既保证了较高的空间利用率，又有效地减少了哈希冲突。 - **泊松分布**：根据泊松分布理论，链表中的节点长度一般不会太长。在 `HashMap` 的文档中提到，理想情况下，随机分布的哈希码下，加载因子为 0.75 时，桶中节点的分布符合参数为 0.5 的泊松分布。根据泊松分布公式，链表长度为 8 的概率极低（不到千万分之一），因此选择 0.75 能有效控制链表长度，减少冲突。 - **CPU 缓存优化**：当加载因子超过 0.8 时，`HashMap` 查找过程中，CPU 缓存不命中的情况会增加，导致查找性能下降。加载因子 0.75 限制在合理范围内，避免了这一问题。 #### 4. **数学推导** - 基于二项分布的推导可以证明，0.75 是一个理想的加载因子值。它保证了较低的哈希冲突概率，同时与 `HashMap` 扩容时的容量倍数相匹配： \[ 16 \times 0.75 = 12 \] \[ 32 \times 0.75 = 24 \] - 这些计算结果都是整数，方便在扩容时整齐划一地处理数据。 #### 5. **其他可能的选择** - 0.75 不是唯一的加载因子。0.5 到 1 之间的其他加载因子也可以使用，如 0.625 或 0.875，但 0.75 由于平衡了查找性能、空间利用率和 CPU 缓存命中率，因此被认为是最理想的选择。 ### 总结： `HashMap` 选择默认加载因子为 0.75 是基于多种考虑的结果，包括空间利用率、查找性能、哈希冲突概率、CPU 缓存优化等。0.75 提供了一个良好的平衡点，在现实应用中表现出色。