uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
size_t i = 0;
uint32_t hash = 0;
while (i != length) {
hash = key[i ];
hash = hash << 10;
hash ^= hash >> 6;
}
hash = hash << 3;
hash ^= hash >> 11;
hash = hash << 15;
return hash;
}
來源：https ://en.wikipedia.org/wiki/Jenkins_hash_function
添加hash<<10到hash時，如果字串長度很大，它可能會溢位。當使用多項式散列函式對字串進行散列時，我們在每次迭代中mod p取值（p是 范圍內的一個大素數），并回傳。但是在這個演算法中，我們為什么不采取防止溢位呢？我們如何確保回傳值保持在哈希表長度內？uint32_thash % hash_table_lengthhash = (hash (hash<<10)) % phash
uj5u.com熱心網友回復：
一次一個哈希被設計為將一串位元組作為輸入，然后輸出一個（大致）均勻分布的 32 位值。重要的是，這意味著如果您想使用散列函式將鍵分配到散串列中，則需要執行一些輔助數學運算以將 32 位散列轉換為表索引，因為散列函式本身不是設計的將其輸出限制為較少數量的插槽。因此，例如，如果您想使用它來分配密鑰，您可以通過表槽數修改結果。
上一段中的推理本質上歸結為“正如最初所寫的那樣，散列函式不會嘗試適應少量的插槽。” 但這里還有一個更深層次的問題：為什么散列函式沒有為處理整數溢位做出任何規定，為什么它不在每一步都用一個素數修改其內部值？這與指導哈希函式的設計原則有關。一次一個哈希在一篇關于使用可逆變換構建具有某些理想屬性的哈希函式族的文章中進行了描述. 這個想法是通過增量應用將現有哈希值和新位元組組合在一起的可逆變換來構建長位元組流的哈希。這樣做有一個有用的屬性，如果你已經對位元組流 X 和 Y 進行了哈希處理并且沒有發生沖突，那么如果你將相同的位元組序列附加到 X 和 Y 上，那么就沒有發生沖突的機會。具體操作在散列中使用的確實是可逆的，但是關于為什么是微妙的理由并且依賴于添加移位并允許計算溢位對應于乘以模2 32的可逆值的事實。從這個意義上說，這里故意沒有 mods，因為由溢位計算的隱式模執行“正確”模以使所有步驟都可逆。
這與多項式散列以一些素數為模形成對比。你是對的，在使用多項式散列策略時，你需要注意整數溢位，因為你特別不希望這些隱式 mods 啟動 - 畢竟，你是用不同的數字進行 modding！但這對于特定的散列策略來說是特別的。有很多不同的方法來構建散列函式，每種方法都使用不同的方法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417250.html
標籤：
上一篇：單源最短路徑問題的演算法
下一篇：如何使用原型撰寫快速排序函式