哈希表是一種高效的數據結構，通過哈希函數將鍵映射到存儲位置。但由于哈希函數可能將不同鍵映射到相同位置（稱為哈希沖突），需要有效的方法來解決沖突。以下是常見的沖突解決策略，每種方法都有其原理、優缺點和適用場景。我將逐步解釋這些方法，確保內容清晰可靠。

1. 開放尋址法（Open Addressing）

• 原理：當沖突發生時，在哈希表中順序探測其他空槽位，直到找到可用位置。探測序列由特定公式定義。
• 常見變體：
  • 線性探測（Linear Probing）：探測位置計算為 $h(k, i) = (h'(k) + i) \mod m$，其中 $i$ 是探測步數（從0開始遞增），$h'(k)$ 是初始哈希函數，$m$ 是表大小。
  • 二次探測（Quadratic Probing）：位置公式為 $h(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod m$，其中 $c_1$ 和 $c_2$ 是常數，減少聚集現象。
  • 雙重哈希（Double Hashing）：使用第二個哈希函數，公式為 $h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$，其中 $h_2(k)$ 用于計算步長。
• 優點：節省空間，不需要額外數據結構。
• 缺點：可能導致聚集（clustering），降低性能；裝載因子高時效率下降。
• 適用場景：內存受限的環境，如嵌入式系統。

2. 鏈地址法（Chaining）

• 原理：每個哈希表槽位存儲一個鏈表（或其他動態結構），沖突的元素直接添加到鏈表中。哈希函數僅用