How to quickly generate a new string hash after concatenating 2 strings
- by philcolbourn
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 +?
