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