If my math is right, I can quickly generate a new hash value for the concatenation of two strings if I already have the individual hash values for each string. But only if the hash function is of the form:
hash(n) = k * hash(n-1) + c(n), and h(0) = 0.
In this case,
hash( concat(s1,s2) ) = k**length(s2) * hash(s1) + hash(s2)
eg.
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.
Now, for the SDBM hash
k=65599
. Whereas the DJB hash
has k=33
(or perhaps 31
?) and h(0) = 5381
so to make it work you can set h(0) = 0
instead.
But a modification on the DJB hash
uses xor
instead of +
to add each character.
http://www.cse.yorku.ca/~oz/hash.html
Is there another technique to quickly calculate the hash value of concatenated strings if the hash function uses xor
instead of +
?