2012-04-12 60 views
2

將不同對象的兩個哈希合併的一種可接受方式是使用XOR。這是有道理的,但正如下面的帖子中Thomas Pornin的第二個評論中所提到的,XOR是可交換的,這意味着如果你將每個元素散列到一個集合中並將它們與XOR合併,那麼你所做的任何順序總是會導致相同的散列:爲有序集合組合散列

Why is XOR the default way to combine hashes?

什麼是要依賴於順序散列結合的好辦法?如果它是特定的大小,32位和64位的一些已知技術是什麼?

+0

注意,在特定情況下,我有一個從0到元素數量的迭代變量'i'。有沒有一種好的方法來使用'我'來做出依賴訂單的哈希? – Trevor 2012-04-12 16:49:07

+0

如果要強制執行順序,可以在將它們存入集合之前旋轉(*不轉移)部分哈希。這如果當然可以導致碰撞(如H(ABCD)== H(DABC)),但這是遊戲的一部分... – wildplasser 2012-04-12 17:59:15

+0

現在我在做一些愚蠢的事情,我乘以一個巨大的素數'我' ,以及用每個元素的散列表示異或。它確實強加了秩序,但我絕對不是專家,我不知道這是否會導致任何重大沖突。 – Trevor 2012-04-12 18:54:38

回答

1

爲了使得到的散列順序相關,算法中必須有一些順序的(即非靜態的)方面。最常見的技術可能是Cyclic Redundancy Checks(CRC)。

CRC可以硬件實現爲具有異或反饋的移位寄存器。這種移位寄存器用作確定性隨機數發生器。如果初始狀態相同,它將始終經歷相同的狀態序列。這些狀態在CRC簽名計算中用於以可重複的方式對數據進行XOR。

要組合兩個散列值,您需要將它們與來自CRC算法的第三個值異或。這可能是計算或者從查找採取table.-

熱門CRC碼:

09 bits (CRC-8) 
17 bits (CRC-16) 
33 bits (CRC-32) 
65 bits (CRC-64) 

Classless.Hasher提供更多的細節。

C#實現可以在HashLib中找到。