假設您有兩個哈希H(A)，H(B)并且想要將它們組合在一起。我已經讀到，將兩個散列組合在一起的一種好方法是使用XOR它們，例如XOR( H(A), H(B) )。這些哈希函數準則在此簡要地介紹了我找到的最佳解釋：對兩個具有大致隨機分布的數字進行異或運算會導致另一個仍具有大致隨機分布*的數字，但現在取決于這兩個值。 ... *在要組合的兩個數字的每一位，如果兩位相等，則輸出0，否則為1。換句話說，在50％的組合中，將輸出1。因此，如果兩個輸入位各自有大約50-50的可能性為0或1，那么輸出位也是如此。您能解釋為什么XOR應該是用于組合哈希函數（而不是OR或AND等）的默認操作的直覺和/或數學方法嗎？
3 回答
慕慕森
TA貢獻1856條經驗 獲得超17個贊
xor是在散列時使用的危險默認函數。它比and和更好or，但這并不多。
xor是對稱的，因此元素的順序丟失了。因此，"bad"哈希組合與相同"dab"。
xor 將成對的相同值映射為零，并且應避免將“公共”值映射為零：
因此，(a,a)被映射為0，(b,b)也被映射為0。由于這樣的對幾乎總是比隨機性所暗示的更為普遍，因此最終在零處產生的碰撞要多得多。
遇到這兩個問題，xor最終是一個哈希組合器，看起來表面上還算不錯，但經過進一步檢查后才發現。
在現代硬件上，添加速度通常與添加速度差不多xor（公認的，它可能會使用更多功能來實現此目的）。加法運算的真值表與所xor討論的位類似，但是當兩個值均為1時，它還會向下一位發送一個位。這意味著它將刪除較少的信息。
因此，與if相比，結果hash(a) + hash(b)要好于0。hash(a) xor hash(b)a==bhash(a)<<1
這仍然是對稱的。所以"bad"并"dab"得到同樣的結果仍然是一個問題。我們可以以適度的成本打破這種對稱性：
hash(a)<<1 + hash(a) + hash(b)
又名hash(a)*3 + hash(b)。（hash(a)如果使用班次解決方案，建議一次計算并存儲）。而不是任何奇數常量，3將雙射地將一個“ k-bit”無符號整數映射到自身，因為無符號整數的映射對2^k某些對象而言是數學模k，并且任何奇數常量都相對于2^k。
對于更高級的版本，我們可以檢查boost::hash_combine，這實際上是：
size_t hash_combine( size_t lhs, size_t rhs ) {
lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
return lhs;
}
在這里，我們將一些seed帶有常數的移位版本加在一起（基本上是隨機的0s和1s，特別是32位固定點分數的黃金分割率的倒數），加上一些加法和一個xor。這打破對稱，并介紹了一些“噪聲”，如果傳入的散列值是差（即，每一個部件散列想象到0 -上述處理得很好，產生的涂抹1和0。之后的每個結合我的幼稚3*hash(a)+hash(b)簡單地一個輸出0中這種情況）。
（對于不熟悉C / C ++的人，a size_t是一個無符號整數值，該值足以描述內存中任何對象的大小。在64位系統上，它通常是64位無符號整數。在32位系統上，一個32位無符號整數。）
侃侃爾雅
TA貢獻1801條經驗 獲得超16個贊
Xor可能是組合哈希的“默認”方式，但是Greg Hewgill的答案也表明了它有陷阱的原因：兩個相同哈希值的Xor為零。在現實生活中，存在相同的散列比人們預期的更常見。然后，您可能會發現在這些（不是那么少見的）極端情況下，所得到的組合哈希值始終相同（零）。哈希沖突比您預期的要頻繁得多。
在一個人為的示例中，您可能正在組合來自您管理的不同網站的用戶的哈希密碼。不幸的是，大量用戶重復使用了他們的密碼，并且產生的哈希值中令人驚訝的比例為零！
添加回答
舉報
0/150
提交
取消