如何在连接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个字符串后快速生成新的字符串散列

回答

相关问题