J'écris un programme en ce moment qui produit quatre entiers 32 bits non signés comme sortie d'une certaine fonction. Je veux que je sache ces quatre entiers, je peux donc comparer la sortie de cette fonction aux sorties futures.
J'ai du mal à écrire une fonction de hachage décente cependant. Lorsque j'ai écrit à l'origine ce code, j'ai lancé un simple ajout de chacun des quatre entiers, que je savais ne suffirait pas. J'ai essayé plusieurs autres techniques, telles que le changement et l'ajout, en vain. Je reçois un hasch, mais c'est de mauvaise qualité, et la fonction génère une tonne de collisions.
La sortie de hachage peut être un entier 32 bits ou 64 bits. La fonction en question génère de nombreuses milliards de hashes. Les collisions sont donc un véritable problème ici, et je suis disposé à utiliser une variable plus grande pour vous assurer qu'il y a aussi peu de collisions que possible.
Quelqu'un peut-il m'aider à comprendre comment écrire une fonction de hachage de qualité?
7 Réponses :
Pourquoi ne stockez-vous pas les quatre entiers dans une structure de données appropriée et les comparez-les? L'avantage de les hacher dans ce cas semble douteux pour moi, sauf si le stockage est un problème.
Si le stockage est le problème, vous pouvez utiliser l'une des fonctions de hachage analysées ici .
Parce que le hachage peut générer des collisions, vous devez garder les clés en mémoire de toute façon afin de découvrir ces collisions. Hashmaps et autres données de données standard font cela dans leur comptabilité interne.
Comme la clé est si petite, utilisez simplement la clé directement plutôt que la hachage. Cela sera plus rapide et ne garantira aucune collision.
Pourquoi un hash? Il semble qu'un STD :: Set ou STD :: Multi Set serait mieux adapté pour stocker ce type de sortie. Tout ce que vous devriez faire est d'envelopper les quatre entiers dans une structure et d'écrire une simple fonction comparer.
Essayez d'utiliser CRC ou FNV . FNV est agréable car il est rapide et a une méthode définie de bits de pliage pour obtenir des valeurs de hachage "plus petites" (c'est-à-dire 12 bits / 24 bits / etc.).
L'avantage de générer un hachage de 64 bits d'un numéro de 128 bits (4 x 32 bits) est un peu discutable car, car d'autres personnes ont suggéré, vous pouvez simplement utiliser la valeur d'origine comme une clé dans un ensemble . Vous voulez vraiment que le nombre de bits dans le hachage représente le nombre de valeurs que vous avez à l'origine. Par exemple, si votre ensemble de données comporte 100 000 valeurs 4x32-bits, vous voulez probablement une valeur de hachage de 17 bits ou 18 bits, pas un hachage de 64 bits.
Peut-être un peu surkill, mais considérez Boost.Hash . Génère un code très simple et de bonnes valeurs.
Je suis tout à fait d'accord avec Vinko - il suffit de les comparer à tous. Si vous voulez toujours une bonne fonction de hachage, vous devez analyser la distribution de vos 4 entiers non décisés. Ensuite, vous devez créer votre fonction de hachage de manière à ce que le résultat soit même réparti sur toute la plage de la valeur de hachage 32 bits.
Un exemple simple - supposons simplement que la plupart du temps, le résultat de chaque fonction est compris entre 0 et 255. Vous pourriez facilement mélanger les 8 bits inférieurs de chaque fonction dans votre hachage. La plupart du temps, vous trouverez le résultat directement, juste parfois (quand une fonction renvoie un résultat plus large), vous auriez une collision.
Pour résumer - sans information comment les résultats des 4 fonctions sont distribués, nous ne pouvons pas vous aider avec une bonne fonction de hachage.
Voici une fonction de hachage assez raisonnable de 4 entiers à 1 entier: avec une entrée de manière uniformément distribuée, il offre une sortie de manière uniformément distribuée. Tous les bits de l'entrée participent à la sortie et chaque valeur d'entrée (bien que toutes les bit d'entrée) puissent affecter chaque bit de sortie. Les chances sont qu'il est plus rapide que la fonction qui produit la sortie, auquel cas aucun problème de performance. Il y a d'autres hachages avec d'autres caractéristiques, mais accumulez-la multiplication-Multiplication-by-prime est un bon départ jusqu'à preuve autrement. Vous pouvez essayer d'accumuler avec Xor au lieu d'addition si vous le souhaitez. De toute façon, il est facile de générer des collisions (par exemple {1, 0, A, B} collision avec {0, 37, A, B} pour tous A, B), vous voudrez peut-être choisir un premier que vous pensez avoir Rien à voir avec un bogue de mise en œuvre plausible dans votre fonction. Donc, si votre fonction a beaucoup d'arithmétique modulo-37, utilisez peut-être 1000003 à la place.
"Je veux hacher ces quatre entiers, afin que je puisse comparer la sortie de cette fonction aux sorties futures." Ne suit pas nécessairement. Si vous testez une fonction que les chaînes de sortie, vous n'auriez pas à hacher à 32 ou 64 bits afin de faire des tests de régression. Dans votre cas, vous vous donnez un mal de tête afin d'économiser 50% de stockage (supposer que vous utilisez 64 bits au lieu de 128). Est-ce que ça vaut le coup? Avez-vous essayé d'utiliser GZIP à la place?
Avez-vous envisagé d'utiliser une ou plusieurs des fonctions de hachage à usage général suivantes: /hashfonctions/index.html