负载因子（Load Factor）
负载因子衡量哈希表的装满程度，是决定哈希冲突概率和扩容时机的关键指标。
定义
负载因子（Load Factor）是哈希表中已存储元素数量与数组容量的比值：
负载因子 = 已存储元素数量 / 数组容量
λ = n / m
其中：
n= 已存储的元素数量m= 数组的容量（桶的数量）
核心特性
| 特性 | 说明 |
|---|---|
| 取值范围 | λ ≥ 0，通常在实际使用中 λ ≤ 1（开放寻址法）或 λ 可 > 1（拉链法） |
| 冲突概率 | 负载因子越大，哈希冲突概率越高 |
| 空间效率 | 负载因子越小，空间浪费越多 |
| 时间效率 | 负载因子过大导致冲突增多，查找/插入效率下降 |
负载因子与冲突关系
| 负载因子 λ | 冲突概率 | 平均查找长度（拉链法） | 说明 |
|---|---|---|---|
| 0.5 | 较低 | ≈ 1 + λ/2 = 1.25 | 空间浪费较多 |
| 0.75 | 适中 | ≈ 1 + λ/2 = 1.375 | Java HashMap 默认值 |
| 1.0 | 较高 | ≈ 1 + λ/2 = 1.5 | 数组刚好装满 |
| > 1.0 | 很高 | 快速增长 | 拉链法可以支持，开放寻址法不行 |
扩容机制
当负载因子超过阈值时，触发哈希表扩容（rehash）：
Java HashMap 的扩容策略
| 参数 | 值 | 说明 |
|---|---|---|
| 默认初始容量 | 16 | 必须是 2 的幂 |
| 默认负载因子阈值 | 0.75 | 平衡时间和空间效率 |
| 扩容倍数 | 2 倍 | newCap = oldCap << 1 |
| 树化阈值 | 链表长度 > 8 | 转为红黑树 |
扩容流程：
- 创建一个新数组，容量为原来的 2 倍
- 遍历原数组所有元素
- 重新计算每个元素的哈希值对应的新索引
- 将元素复制到新数组（rehash）
时间复杂度：单次扩容 O(n)，但均摊后仍为 O(1)
不同冲突解决方法的负载因子
| 冲突解决方法 | 支持的负载因子 | 说明 |
|---|---|---|
| 拉链法 | λ 可以 > 1 | 链表可以无限增长（虽然性能会下降） |
| 开放寻址法 | λ 必须 < 1 | 需要空位才能插入新元素 |
| 线性探查法 | λ < 0.7 较好 | 负载因子过高会导致聚集现象 |
负载因子的选择
| 场景 | 推荐负载因子 | 原因 |
|---|---|---|
| 内存敏感 | 较高（0.75 ~ 1.0） | 减少数组空间浪费 |
| 时间敏感 | 较低（0.5 ~ 0.75） | 减少冲突，提高查找效率 |
| 开放寻址法 | < 0.7 | 避免聚集现象 |
| 拉链法 | 0.75 ~ 1.0 | 可以容忍较高负载因子 |
与类似概念对比
| 维度 | 负载因子 | 扩容阈值 | 填充因子 |
|---|---|---|---|
| 定义 | n/m（元素数/容量） | 触发扩容的负载因子值 | 同负载因子 |
| 作用 | 衡量装满程度 | 决定何时扩容 | 同负载因子 |
| 典型值 | 动态变化 | 固定值（如 0.75） | 同负载因子 |
注意事项
- 不是越大越好：负载因子过大导致冲突激增，性能急剧下降
- 不是越小越好：负载因子过小浪费大量数组空间
- Java HashMap 的选择：0.75 是时间和空间效率的平衡点
- 扩容代价：虽然单次扩容 O(n)，但均摊分析后仍为 O(1)
应用场景
- 哈希表性能调优：根据应用场景调整负载因子阈值
- 自定义哈希表：设计扩容策略时参考负载因子
- 性能分析：诊断哈希表性能问题时检查负载因子