rapidement (XOR-?) Combiner hachages SHA1 pour générer un nouveau hachage

Question

Avoir une (éventuellement grande) liste de unique lignes de texte (données JSON stringifiées) J'ai besoin de calculer un hachage unique pour l'ensemble du document texte. Souvent, de nouvelles lignes sont ajoutées au document et, parfois, certaines lignes en sont supprimées, ce qui entraîne la création d'un nouveau hachage pour le document.

Le but ultime est d'être capable d'identifier des documents identiques en utilisant simplement le hachage.

Bien sûr, le calcul du hachage SHA1 pour le document entier après chaque modification me donner le hash unique désiré, mais serait également informatiquement cher - en particulier dans une situation où seulement ~ 40 octets sont ajoutés à un 5 mégaoctet et toutes ces données devraient à nouveau passer par le calcul SHA1. Donc, je suis à la recherche d'une solution qui me permet de réduire le temps nécessaire pour calculer le nouveau hachage.

Un résumé des propriétés du problème/exigences:

• chaque ligne est garantie unique
• l'ordre des lignes ne pas nécessairement besoin de la matière (encore mieux si elle ne fonctionne pas)
• la longueur d'une seule ligne est généralement faible, mais tout le document pourrait être grand
• l'algorithme peut être optimisé pour en annexe données (delet les données pourraient même ing nécessitent un redémarrage à partir de zéro dans ce cas)

Mon idée actuelle est de calculer la SHA1 (ou autre) hachage pour chaque ligne unique individuellement, puis XOR les hash ensemble. Cela devrait satisfaire toutes les exigences. Pour les nouvelles lignes, je calcule juste le SHA1 de cette ligne et XOR avec la somme déjà connue.

Cependant, je suis dans le doute parce que ...

• Je ne suis pas sûr si le hachage XORé serait encore assez fort pour identifier exactement un document (ie. Est-il une probabilité significativement plus élevé de les collisions non désirées?)
• calcul beaucoup de hash SHA1 de courtes lignes pourraient être coûteuses de informatiquement son propre (au moins pendant l'initialisation)

Tout le monde peut faire la lumière sur ces questions?

Alternativement, est-il généralement possible avec SHA1 (ou un hachage similaire) de générer rapidement un nouveau hachage pour les données ajoutées (old hash + appended data = new hash)?

Answer 1

Vous pouvez effectuer des mises à jour incrémentielles pour vous-stream calcul:

var crypto = require('crypto'); 

var shasum = crypto.createHash('sha1'); 
shasum.update("Hello, "); 
shasum.update("World!"); 
console.log(shasum.digest('hex')); 

shasum = crypto.createHash('sha1'); 
shasum.update("Hello, World!") 
console.log(shasum.digest('hex')); 

Answer 2

Il y a des problèmes avec hachant chaque fichier individuellement.

Si deux lignes identiques sont ajoutées, les xor combinés ne changeront pas.

Vous feriez mieux de hacher tous les hachages individuels.

Peut-être utiliser un Merkle Tree.