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