16. HashMap为什么默认负载因子是0.75？如何选择合适的负载因子？

16.HashMap 为什么默认负载因子是 0.75？如何选择合适的负载因子？

HashMap 的默认负载因子 0.75 是时间和空间的折中选择，它保证了哈希桶的填充程度不会太高（避免过多哈希冲突），同时也不会太低（避免浪费内存）。选择合适的负载因子需要权衡查找效率、空间占用和扩容成本，通常：

HashMap 采用数组 + 链表（JDK 1.8 以后可能是红黑树）存储数据，负载因子（Load Factor）控制着何时触发扩容，计算方式如下：

if (size >= capacity * loadFactor) {
    resize();
}

1
2
3

默认负载因子 0.75 代表数组填充 75% 时触发扩容。选择 0.75 主要基于哈希碰撞概率与空间利用率的平衡：

哈希冲突概率分析
- 负载因子越高，桶存储的元素越多，哈希冲突概率上升，导致链表变长或红黑树存储更多元素，get() 和 put() 操作性能下降。
- 负载因子越低，哈希桶填充率下降，减少冲突，但会浪费更多内存。
- 研究表明，0.75 能较好地控制链表长度在 1~2 之间，查找时间复杂度趋近 O(1)。
时间 vs. 空间权衡
- 0.75 确保平均查找成本较低，同时避免频繁扩容导致的内存和计算开销。
- 过小的负载因子（如 0.5）会导致更频繁的扩容，而扩容涉及数据重新哈希（Rehashing），开销较大。
扩容机制的影响
- HashMap 每次扩容时，容量翻倍（capacity = capacity * 2），通过 capacity & (newCap - 1) 计算新索引，减少了 rehashing 成本。
- 0.75 作为负载因子确保扩容不会过于频繁，同时保证 HashMap 的 get() 仍接近 O(1)。

为什么不是 0.5？
0.5 会让 HashMap 更快扩容，导致更高的 rehashing 开销，影响 put() 性能。
为什么不是 1.0？
1.0 代表 HashMap 填充满了才扩容，哈希冲突极高，退化成链表或红黑树，get() 和 put() 可能变为 O(n) 或 O(log n)。
能否修改负载因子？
可以通过 new HashMap<>(initialCapacity, loadFactor) 设置，但通常不推荐调整，除非对查询性能或空间有特殊要求。