hash - 连接2个字符串后如何快速生成新的字符串哈希

Question

如果我的数学是正确的，如果我已经有了每个字符串的单独哈希值，我可以快速生成一个新的哈希值来连接两个字符串。但前提是散列函数的形式为:

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 哈希 k=65599。而 DJB hash 有 k=33(或者 31？)和 h(0) = 5381 所以要使其正常工作，您可以改为设置 h(0) = 0。

但是对 DJB hash 的修改使用 xor 而不是 + 来添加每个字符。

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

如果散列函数使用xor而不是+，是否有另一种技术可以快速计算连接字符串的散列值？

Answer 1

如果您的第二个散列将是散列初始状态的函数，那将是正确的。对于某些类型的哈希函数，很容易根据新的初始状态(如 xor'e 字或它们的总和等)移动它们。但在一般情况下，这几乎是不可能的(在其他情况下，在密码匹配中使用 hash+"salt"将更容易破解)。

但通常您可以使用第一个字符串的散列结果，而不是继续从第二个字符串输入数据。

更新:
我想没有办法找到 f(x,y) for:

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