Le hachage coucou rend la recherche en temps constant en expulsant une clé comme un œuf de coucou

Les tables de hachage à adressage ouvert standard se dégradent lorsque les entrées s'agglutinent et que les chaînes de sondage s'allongent. Rasmus Pagh et Flemming Friche Rodler se sont demandé ce qui se passerait si chaque clé avait exactement deux emplacements possibles au lieu d'un.

Leur dictionnaire, présenté en 2001 au BRICS à Aarhus, utilise deux fonctions de hachage et deux tables. En cas de collision, la clé arrivante expulse l'occupant, qui est déplacé vers son autre foyer. La recherche est garantie en au plus deux sondages.

Comme les tables ne doivent être remplies qu'à environ la moitié en moyenne, la structure reste économe en mémoire tout en offrant une recherche en temps constant dans le pire des cas.

Donner à chaque clé deux places et déplacer le perdant

Deux positions possibles limitent une recherche à deux sondages, quel que soit l'ensemble de clés.

L'expulsion résout les collisions sans longue chaîne de sondage ni liste chaînée.

Elle maintient un taux d'occupation élevé, ce qui permet une bonne utilisation de la mémoire tout en restant favorable au cache.

Choisir une structure de données rapide dans le pire des cas, et pas seulement en moyenne. L'expulsion à deux choix transforme une collision rare et coûteuse en une recherche bornée à deux sondages.

Le hachage coucou est devenu un résultat de référence dans la théorie et la pratique des dictionnaires. Sa garantie de temps constant et sa localité de cache l'ont rendu attractif pour le matériel et le routage à haute performance, et l'idée d'expulsion a influencé des schémas ultérieurs de hachage et d'esquisse.