Quelques questions sur Coucou Hashing

Question

J'ai besoin de construire une table de recherche rapide avec des clés entiers de 8 octets. La construction de la table est faite pendant l'initialisation et les données ne sont pas mises à jour après cela. Le nombre d'éléments de données est inférieur à 100K, donc je peux me permettre d'utiliser un espace supplémentaire pour rendre la table de hachage éparse. Cependant, la recherche de données doit être aussi efficace que possible. D'après ce que je comprends, Cuckoo Hashing semble être un bon choix pour ce genre de scénario. Cependant, je ne suis pas très clair sur un certain nombre de choses:

1. Quelle famille de fonctions de hachage doit être utilisé dans ce cas? Certains articles suggèrent que la famille de fonctions standard ((a * x + b) mod p) mod m "n'est pas un bon choix. De plus, p doit être un primitif> UInt64.MaxValue, ce qui rend difficile le calcul de la fonction. La famille de multiplication-décalage "(a * x) >> (w - log (m))" n'est pas non plus considérée comme un bon choix. Je n'ai pas trouvé de réponse définitive sur la fonction à utiliser.

2. L'opération "insertion" peut déclencher le ressassement. Donc, en théorie, le temps d'insertion est illimité dans le pire des cas (vous continuez à choisir une "mauvaise" fonction qui se traduit par un ressassement). Je comprends, que la probabilité de ceci est proche de zéro, mais j'ai du mal à ignorer simplement ce problème dans la production.

3. Existe-t-il de meilleures structures de données pour le problème décrit? Le original Cuckoo Hash paper suggère qu'un simple hachage de sondage linéaire peut être plus efficace lorsque vous avez suffisamment d'espace supplémentaire (deux à trois fois le nombre d'éléments). De plus, pendant la phase de construction, je peux vérifier s'il y a plus de deux clés qui entrent en collision et choisissent une fonction de hachage différente (je peux me permettre de le faire quelques fois et choisir le meilleur).

Merci beaucoup pour vos réponses.

Answer 1

1. presque toutes les fonctions de hachage fera, puisque vous n'avez 100K clés assurez-vous qu'il est au moins 2 sages indépendants (voir http://www.eecs.harvard.edu/~michaelm/postscripts/soda2008b.pdf) ou tout simplement utiliser quelque chose de rapide.

2. La procédure d'insertion fonctionnera en temps O (1) amorti/attendu si vous faites une recherche exhaustive, puisque vous faites cela au début, tout ira bien. Si vous avez moins de 50% d'utilisation (c'est-à-dire, nombre de slots> 2x nombre de clés), la probabilité qu'un insert déclenche un rehash est faible. Vous pouvez rendre encore plus petit en utilisant une cachette (http://www.eecs.harvard.edu/~michaelm/postscripts/esa2008full.pdf) et la recherche est encore petite. Dans tous les cas, réessayez jusqu'à ce que tout fonctionne, car vous ne faites cela qu'à l'initialisation.

3. Couper deux fois, mesurer une fois.