Comment générer rapidement un nouveau hachage de chaîne après la concaténation de 2 chaînes

Question

Si mes calculs sont corrects, je peux rapidement générer une nouvelle valeur de hachage pour la concaténation de deux chaînes si j'ai déjà les valeurs de hachage individuelles pour chaque chaîne. Mais seulement si la fonction de hachage est de la forme:

hash(n) = k * hash(n-1) + c(n), and h(0) = 0. 

Dans ce cas,

hash(concat(s1,s2)) = k**length(s2) * hash(s1) + hash(s2) 

par exemple.

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. 

Maintenant, pour la SDBM hashk=65599. Alors que le DJB hash a (ou peut-être 31?) Et h(0) = 5381 afin de le faire fonctionner, vous pouvez définir h(0) = 0 à la place.

Mais une modification sur le DJB hash utilise xor au lieu de + pour ajouter chaque caractère.

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

Y at-il une autre technique pour calculer rapidement la valeur de hachage des chaînes concaténées si la fonction de hachage utilise xor au lieu de +?

Answer 1

Cela serait vrai si votre second hachage est fonction de l'état initial de hachage. Pour certains types de fonction de hachage, il est facile de les décaler en fonction du nouvel état initial (comme les mots xor'e, ou leur somme, etc.). Mais dans le cas général c'est presque impossible (dans d'autres cas, l'utilisation de hash + "salt" dans le mot de passe sera plus facile à casser).

Mais généralement, vous pouvez utiliser le résultat du hachage de la première chaîne et continuer à alimenter les données de la deuxième chaîne.

Mise à jour:
Je suppose qu'il n'y a aucun moyen de trouver f(x,y) pour:

h_abc = hashOf(h0, "abc") 
h_def = hashOf(h0, "def") 
(h_abcdef = f(h_abc, h_def)) == hashOf(h0, "abcdef") 

Mais vous capable de:

h_abc = hashOf(h1, "abc") 
(h_abcdef = hashOf(h_abc, "def")) == hashOf(h0, "abcdef") 

l'une des raisons pour lesquelles vous ne pouvez pas faire est que "33" n'est pas la puissance de "2". Si elle utilisera "32" (2 ** 5), alors:

h_abcdef == (h_abc << (5*len(abc))) xor h_def