double hash 是啥

雙重哈希是開放尋址哈希表中的衝突解決技術。雙重哈希的思想是在發生衝突時對鍵做第二個哈希函數。

雙重哈希可以處理 :

(hash1(key) + i * hash2(key)) % TABLE_SIZE

這裏 hash1() 、 hash2() 是hash 函數， TABLE_SIZE 是hash表大小

(如果發生衝突，i遞增然後重複運算)

通俗的二次Hash函數：hash2(key) = PRIME – (key % PRIME)

PRIME一般選擇小於 TABLE_SIZE 的質數

優質的二次Hash函數應該具備這些條件：

二次Hash函數結果不能為0

第二個哈希函數要可以覆蓋表的每一個單元