如何在連接2個字符串後快速生成新的字符串散列

如果我的數學正確，如果我已經爲每個字符串都有單獨的散列值，則可以快速生成兩個字符串串聯的新散列值。但是，只有當哈希函數的形式爲：如何在連接2個字符串後快速生成新的字符串散列

hash(n) = k * hash(n-1) + c(n), and h(0) = 0.

在這種情況下，

hash(concat(s1,s2)) = k**length(s2) * hash(s1) + hash(s2)

如。

h1 = makeHash32_SDBM("abcdef",   6); 
h2 = makeHash32_SDBM("ghijklmn",  8); 
h12 = makeHash32_SDBM("abcdefghijklmn", 14); 
hx = mod32_powI(65599, 8) * h1 + h2; 

h1 = 2534611139 
h2 = 2107082500 
h12 = 1695963591 
hx = 1695963591 

Note that h12 = hx so this demonstrates the idea.

現在，對於SDBM hashk=65599。而DJB hash有（或者可能是31？）和h(0) = 5381，所以爲了使它起作用，您可以改爲設置h(0) = 0。

但是對DJB hash的修改使用xor而不是+來添加每個字符。

http://www.cse.yorku.ca/~oz/hash.html

是否有另一種技術來快速計算級聯字符串的哈希值，如果哈希函數使用xor代替+？

來源

2010-04-04 philcolbourn

如果你的第二個散列是散列初始狀態的函數，那將是真的。對於某些類型的散列函數，可以很容易地根據新的初始狀態（如xor'e單詞或它們的總和等等）來移動它們。但是在一般情況下這幾乎是不可能的（在其他情況下，在密碼匹配中使用hash +「salt」將更容易中斷）。

但通常你可以使用第一個字符串的散列結果，而不是繼續從第二個字符串提供數據。

更新：
我想有沒有辦法找到f(x,y)爲：

h_abc = hashOf(h0, "abc") 
h_def = hashOf(h0, "def") 
(h_abcdef = f(h_abc, h_def)) == hashOf(h0, "abcdef")

但是你能夠：

h_abc = hashOf(h1, "abc") 
(h_abcdef = hashOf(h_abc, "def")) == hashOf(h0, "abcdef")

的爲什麼你不能做到這一點的原因之一是「33」不是「2」的力量。如果它將使用「32」（2 ** 5），那麼：

h_abcdef == (h_abc << (5*len(abc))) xor h_def

來源

2010-04-04 10:53:15 ony

我認爲你的意思是一般的情況是從第一個字符串的散列開始，並將其視爲h（0）然後輸入第二個字符串的每個字符以創建新的散列。 – philcolbourn 2010-04-04 11:54:54

@philcolbourn，只是不要放棄爲第一個字符串計算散列的中間對象，並且您將能夠繼續更新該對象以獲取這兩個字符串的散列。大多數我看到的散列函數的接口能夠在生成_hash result_之後進一步繼續處理已經過載的數據。 – ony 2010-04-04 21:21:25

在這些情況下，我的中間對象是散列值，但是對於使用'xor'的乘法散列有一個神奇的公式嗎？ – philcolbourn 2010-04-05 01:01:29

如何在連接2個字符串後快速生成新的字符串散列

回答

相關問題