深入理解雜湊表中的二次探測再散列技術

什麼是二次探測再散列？

在資料庫系統設計中，雜湊表是常用的資料結構。當發生雜湊衝突（不同鍵值映射到同一索引）時，二次探測是一種開放定址法的衝突解決策略。它通過平方步長（1², 2², 3²...）尋找下一個可用槽位，而非線性探測的固定步長。

為什麼不會返回錯誤結果？

許多開發者誤以為二次探測會導致查找失敗或返回錯誤數據。實際上，演算法會在發現衝突後，按照二次方程式計算新位置繼續搜尋，直到找到目標鍵值或遇到空槽位（表示鍵值不存在）。正確的實作會確保：

• 探測序列能覆蓋整個表（需表大小為質數且載入因子＜0.5）
• 插入時若表已滿則擴容重雜湊
• 查找時區分「空槽位」與「已刪除標記」

核心實作要點

int quadraticProbe(int key, int i, int tableSize) {
    return (key + i*i) % tableSize; // 典型二次探測函數
}

實際系統中常結合雙重雜湊或布谷鳥雜湊提升性能。理解其數學特性（如模質數的二次剩餘分佈）是避免「錯誤結果」的關鍵。