Combinaison de fonctions de hachage - Y a-t-il une diminution significative du risque de collision?

Question

Est-ce que quelqu'un sait s'il y a un réel avantage à réduire la probabilité de collision en combinant des fonctions de hachage? J'ai particulièrement besoin de savoir ceci concernant le hachage 32 bits, à savoir la combinaison d'Adler32 et de CRC32. Fondamentalement, adler32 (crc32 (données)) donnera-t-il une probabilité de collision plus petite que crc32 (données)? Le dernier commentaire here donne quelques résultats de test en faveur de la combinaison, mais aucune source n'est mentionnée. Pour mon but, la collision n'est pas critique (c'est-à-dire que la tâche n'implique pas de sécurité), mais je préfère de toute façon minimiser la probabilité, si possible. PS: Je commence juste dans le monde merveilleux du hachage, en faisant beaucoup de lecture à ce sujet. Désolé si j'ai posé une question idiote, je n'ai même pas encore acquis le bon "dialecte de hachage", probablement mes recherches de Google concernant ceci ont été également mal formées. Merci.

Answer 1

Cela n'a aucun sens de les combiner en série comme ça. Vous êtes en train de hacher un espace de 32 bits vers un autre espace de 32 bits.

Dans le cas d'une collision crc32 dans la première étape, le résultat final est toujours une collision. Ensuite, vous ajoutez des collisions potentielles dans l'étape adler32. Donc, ça ne peut pas aller mieux, et ça ne peut qu'être le même ou pire.

Pour réduire les collisions, vous pouvez essayer quelque chose comme en utilisant les deux hash indépendamment pour créer un espace de sortie 64 bits:

adler32 (données) < < 32 | crc32 (données)

S'il y a un avantage important à le faire, je ne suis pas sûr.

Notez que le commentaire original dont vous avez parlé stockait les hash indépendamment:

Quel que soit l'algorithme que vous utilisez, il est va être une chance de faux positifs . Cependant, vous pouvez réduire ces chances d'une marge considérable en utilisant deux algorithmes de hachage différents . Si vous deviez calculer et stocker à la fois le CRC32 et le Alder32 pour chaque URL, les probabilités d'une collision simultanée pour les deux hachages pour une paire donnée d'URL sont largement réduites.

Bien sûr, cela signifie stocker deux fois plus d'informations que votre problème d'origine. Cependant, il est un moyen de stocker les deux ensembles de données hachage telle qu'elle nécessite un minimum de mémoire (10kb ou presque) tout en donnant presque les mêmes performances de recherche (15 microsecs/recherche par rapport à 5 microsecs) que les hash de Perl .