负载因子（Load Factor） 是哈希表（Hash Table）中的一个关键性能指标，用于衡量哈希表的空间利用率和发生哈希冲突的可能性。

一：定义

负载因子（通常用希腊字母 λ 表示）的计算公式为：

负载因子 (λ) = 哈希表中已存储的键值对数量 (n) / 哈希表的总容量（槽位数，桶数）(m)

即：λ = n / m

• n：当前哈希表中实际存储的元素个数。
• m：哈希表底层数组的长度，也就是“桶”（bucket）或“槽”（slot）的总数。

---

二：作用和意义

负载因子是评估哈希表性能和决定何时进行扩容（Resizing） 的核心依据。

1. 衡量空间利用效率：

   • 负载因子越接近 1，说明哈希表的空间被利用得越充分。
   • 负载因子越小，说明哈希表中空闲的槽位越多，空间利用率较低。

2. 预测冲突概率和性能：

   • 负载因子越高，意味着更多的元素被映射到有限的槽位中，发生哈希冲突的概率就越大。
   • 冲突越多，查找、插入、删除操作的平均时间复杂度就越差（例如，链地址法中链表会变长，查找需要遍历更多节点）。
   • 因此，高负载因子通常意味着更差的性能。

3. 触发扩容机制：

   • 为了避免性能急剧下降，哈希表实现中通常会设定一个阈值负载因子（Threshold Load Factor）。
   • 当当前负载因子 超过这个阈值 时，哈希表就会自动进行扩容（通常是将容量扩大一倍，如从 m 扩到 2m），然后将所有已有的元素重新哈希（rehash）到新的、更大的数组中。
   • 扩容后，负载因子会下降，冲突概率降低，性能得以恢复。

---

三：举个例子

假设有一个哈希表：

• 当前容量 m = 10
• 已存储元素数量 n = 7

那么，负载因子 λ = 7 / 10 = 0.7

如果该哈希表设定的阈值负载因子为 0.75，那么当前负载因子 0.7 < 0.75，不需要扩容。

如果再插入3个元素，n 变为 10，此时 λ = 10 / 10 = 1.0，超过了 0.75，哈希表就会触发扩容，比如将容量扩大到 20。扩容并 rehash 后，λ = 10 / 20 = 0.5，性能得到改善。

---

四：常见默认值

不同编程语言和库的实现中，阈值负载因子的默认值可能不同，但通常在 0.7 到 0.75 之间。例如：

• Java 的 HashMap：默认初始容量为 16，默认负载因子为 0.75。当元素数量超过 容量 × 0.75 时，就会触发扩容。
• Python 的 dict：其扩容策略更复杂，但本质上也是基于类似负载因子的概念来控制。

---

五：归纳

• 负载因子 = 元素数量 / 表容量。
• 它是哈希表性能的晴雨表：值越高，冲突越多，性能越差。
• 它是扩容的触发器：当超过预设阈值时，哈希表会自动扩容以维持性能。
• 合理设置负载因子（如 0.75）是在空间利用率和时间效率之间做出的平衡。