負載因子（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）是在空間利用率和時間效率之間做出的平衡。