如何在连接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 哈希 具有 k=33（或者可能 31？）和 h(0) = 5381 所以要使其正常工作，您可以设置 h(0) = 0 。

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

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

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

Answer 1

如果您的第二个哈希值是哈希值初始状态的函数，那么情况就是如此。对于某些类型的哈希函数，很容易根据新的初始状态（例如异或词或其总和等）来移动它们。但在一般情况下，这几乎是不可能的（在其他情况下，在密码匹配中使用哈希+“盐”会更容易被破解）。

但通常您可以使用第一个字符串的哈希结果，然后继续从第二个字符串提供数据。

更新：
我想没有办法找到 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