3

如果我的数学是正确的，如果我已经拥有每个字符串的单独哈希值，我可以快速为两个字符串的连接生成一个新的哈希值。但仅当哈希函数具有以下形式时：

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 hash k=65599. 而DJB hashhas k=33（或者可能31？）等h(0) = 5381要使其工作，您可以h(0) = 0改为设置。

但是对DJB hash用途进行了修改，xor而不是+添加每个字符。

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

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

4

1 回答 1

0

如果您的第二个哈希将是哈希初始状态的函数，那将是正确的。对于某些类型的散列函数，很容易根据新的初始状态（如异或词或它们的总和等）来转移它们。但在一般情况下，这几乎是不可能的（在其他情况下，在密码匹配中使用 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-04T10:53:15.603 回答