J'écris un module de noyau Linux et j'ai besoin de proposer une fonction de hachage qui prend deux entiers pour la saisie. Parce que le code circule dans l'espace du noyau, aucune des bibliothèques standard n'est disponible pour moi.
Fondamentalement, j'ai besoin d'une fonction de hachage où: où des entrées acceptables pour un et B sont des entiers non signés 32 bits. La fonction de hachage doit renvoyer un entier non signé 64 bits. Collision (c'est-à-dire HASH (A, B) = C et HASH (D, F) = C aussi) n'est pas souhaitable car ces valeurs seront utilisées dans un arbre de recherche binaire. Le résultat de la recherche est une liste liée des résultats possibles qui sont ensuite itératés sur l'endroit où A et B sont en réalité comparés. Donc, une certaine collision est acceptable, mais moins les collisions, moins les itérations requises, et plus elle sera exécutée. performance est également d'une importance extrême, cette recherche sera utilisée pour chaque paquet reçu dans un système comme J'écris une application de pare-feu (les entiers sont en réalité des adresses de source et de destination de paquets). Cette fonction est utilisée pour rechercher des sessions de réseau existantes. Merci pour votre temps.
5 Réponses :
((a | b) << 32) + (a & b) is commutative and should lead to a minimum number of collisions. I have to think more about it though ...
Besoin de parenthèses? ((a | b) << 32) + (A & B)
Cela semble bien fonctionner, mais est légèrement plus lent que la solution de solution postée après le test.
pseudocode de la façon dont vous pouvez le faire:
uint64_t myhash(uint32_t a, uint32_t b)
{
uint64 a64 = (uint64_t) a;
uint64 b64 = (uint64_t) b;
return (a > b) ? ((a64 << 32) | b64) : ((b64 << 32) | a64);
}
On dirait que nous aimons tous celui-ci!
Après avoir analysé et tester toutes les réponses fournies, celle-ci semble être à la fois la plus simple et la plus rapide. Merci!
Aussi ... Toute façon de se débarrasser de "Avertissement: Nombre de quart de vitesse de gauche> = largeur de type [activé par défaut]"?
Hein, je viens de décider de jeter la main gauche à __U64 et l'avertissement est parti.
@Claudix - Merci pour la modification. Mon C est rouillé après de nombreuses années en utilisant d'autres langues (c'est pourquoi j'ai utilisé pseudocode). L'opérateur ternaire que vous avez ajouté dans votre édition est également un bon ajout.
#define MYHASH(a,b) ( (((UINT64) max(a,b)) << 32) | ((UINT64) min(a,b)) )
Cela ressemble à une bonne solution! L'utilisation de cette macro, cependant, causera «A» et «B» d'être évaluée en silence deux fois (ou plus, en fonction des définitions de «max» et «min»), ce qui pourrait causer des comportements inattendus. De plus, sur le débordement de la pile, nous découragons généralement les réponses du code - seules telles que ceci: voir meta.stackexchange.com/a/95473 . Je (et probablement beaucoup d'autres lecteurs) peut voir et comprendre comment et pourquoi cela fonctionne, mais les lecteurs OP et d'autres pourraient bénéficier d'une petite explication sur les raisons et comment cela fonctionne.
Merci pour votre commentaire ;-)
Comment sur ((uint64_t) max (A, B) << uint64_c (32)) | (uint64_t) min (A, B)) ? Cela éviterait entièrement les collisions, car il n'y a pas de chevauchement possible entre les intrants. Je ne peux pas parler de la distribution cependant, comme cela dépend de vos valeurs d'entrée.
Une première affiche vous a battue à cette solution par 3 minutes: Stackoverflow.com/a/11786819 bien qu'ils n'aient pas eu beaucoup d'informations de fond ...
Oui, j'ai vu cela immédiatement après que j'ai posté. Je ne sais pas quel protocole est dans ce cas ...
Malheureusement, je n'ai pas d'uint64_t, max, uint64_c ou des types / fonctions mineures à la disposition de moi. J'utilise __s64 et __U32 dans le linux / types.h en-tête.
Je suis sûr que vous pouvez comprendre les équivalents à utiliser. Comme pour max / min , ils ne font pas partie de la bibliothèque standard C, mais ils sont très faciles à mettre en œuvre.
(A ^ b) | ((A ^ ~ b) << 32);
@wildplasser - Ce n'est pas un non-sens complet, c'est un code sans succursale qui est une bonne chose dans de nombreuses situations. Cela prend plus d'opérations arithmétiques que d'autres solutions qui ne font que comparer et décaler, mais celles-ci sont toujours vraiment rapides. Tout ce que cela doit compiler correctement est uint64_t hachage = au début, et tout ce dont elle doit être une excellente réponse est une explication du moment où cela produira une meilleure distribution que ces méthodes.
Fonctionne bien, mais est légèrement plus lent que la hache de solution postée.
C'est complètement des ordures, car il gaspille 32 bits, car les 32 bits supérieurs et les 32 bits inférieurs sont complémentaires, gaspillant 32/64 bits. BTW: C'est une bonne raison de tester les fonctions de hachage pour propagation , pas de performance
@wildplasser - Non, ils ne sont pas complémentaires: comme l'inversion est appliquée uniquement sur B dans les 32 bits supérieurs, ils sont différents selon la commande d'A et B.
..., mais vous pouvez prédire la valeur du bit x, étant donné la valeur du bit x + - 32. Mais il est toujours est symétrique ... (Je vais me pleurer pour dormir, lire Knuth 4a ...)
Peut-être que je suis mal compris ce que vous voulez, mais pourquoi ne pas faire un bitwise ou de la plus petite des deux valeurs avec le décalage de gauche 32 de la valeur plus grande. Ensuite, vous utilisez l'espace complet des 64 bits (que vous ne recevez pas simplement en ajoutant).