Coucou en C

Question

Quelqu'un a-t-il implémenté le hachage de coucou en C? S'il existait une version Open Source non GPL, ce serait parfait!

Depuis qu'Adam l'a mentionné dans son commentaire, tout le monde sait pourquoi il n'est pas tellement utilisé? Est-ce juste une question de mise en œuvre ou les bonnes propriétés théoriques ne se matérialisent pas dans la pratique?

Answer 1

http://www.mpi-inf.mpg.de/ ~ ponceuses / programmes / coucou /

HTH

Answer 2

Comme d'autres réponses l'ont souligné, il est vrai que la table de hachage de coucou la plus simple nécessite que la table soit à moitié vide. Cependant, le concept a été généralisé au d -ary hack du coucou, dans lequel chaque clé a d des emplacements possibles pour imbriquer, par opposition à 2 emplacements dans la version simple.

Le facteur de charge acceptable augmente rapidement avec d . Pour seulement d = 3, vous pouvez déjà utiliser environ une table complète à 75%. L'inconvénient est que vous avez besoin de d fonctions de hachage indépendantes. Je suis fan des fonctions de hachage de Bob Jenkins à cette fin (voir http://burtleburtle.net /bob/c/lookup3.c ), qui pourrait vous être utile dans une implémentation de hachage de coucous.

Answer 3

Le hachage de coucous est relativement peu utilisé en dehors du monde universitaire (mis à part les caches de matériel, qui empruntent parfois des idées, mais ne les implémentent pas pleinement). Il faut une table de hachage très clairsemée pour passer du bon temps sur les insertions - vous devez vraiment avoir 51% de votre table vide pour obtenir de bonnes performances. Donc, il est rapide et prend beaucoup de place, ou lent et utilise efficacement l’espace - jamais les deux. D'autres algorithmes sont efficaces dans le temps et dans l'espace, bien qu'ils soient pires que le coucou lorsque seul le temps ou l'espace est pris en compte.

Voici un générateur de code pour les tables de hachage de coucous . Vérifiez la licence du générateur pour vérifier que la sortie est non GPL. Cela devrait être le cas, mais vérifiez quand même.

-Adam

Answer 4

Même s’il s’agit d’une question ancienne, une personne pourrait être intéressée:)

Ce document décrit la mise en œuvre d'un hachage de coucou d-ary parallèle sur les GPU (CUDA / OpenCL). Il est très bien décrit et sa mise en œuvre basée sur la description est assez facile. Généralement intéressant à lire, si vous êtes intéressé par ce sujet. (Vous aurez cependant besoin d’un identifiant ACM.)

Answer 5

Le langage IO en a un, en PHash.c. Vous pouvez trouver le code pour IO sur Github. IO est sous licence BSD.

Answer 6

Je vois le problème de l’utilisation, mais c’est ce que j’ai fait pour essayer ce schéma de hachage particulier. Merci de me prévenir si quelque chose me manque.

À ma connaissance, les alternatives possibles aux tables de hachage pour créer un dictionnaire dynamique sont les arbres binaires et les skiplistes (équilibrés). Juste pour la discussion, abstenons-nous des types de clé et de valeur et supposons que nous accéderons aux valeurs par le biais d'un void * .

Pour un arbre binaire, j'aurais:

struct node {
  void *key;
  void *value;
  struct node *left;
  struct node *right;
}

Donc, en supposant que les pointeurs aient tous la même taille s , pour stocker les n éléments, vous aurez besoin de 4 s octets.

Les disciplines sont presque les mêmes que le nombre moyen de pointeurs dans un nœud est égal à 2.

Dans une table de hachage, j'aurais:

struct slot {
  void *key;
  void *value;
}

Ainsi, chaque élément ne nécessite que 2 s octets à stocker. Si le facteur de charge est de 50%, pour stocker n éléments, il me faudra les mêmes 4 s octets que les arbres.

Cela ne me semble pas trop grave: la table de hachage à coucou occupera plus ou moins la même quantité de mémoire qu'un arbre binaire, mais me donnera un temps d'accès O (1) plutôt que O (log n).

Sans compter la complexité liée au maintien de l'arborescence équilibrée et les informations supplémentaires pouvant être nécessaires pour stocker les informations d'équilibrage dans le noeud.

D'autres systèmes de hachage pourraient atteindre un meilleur facteur de charge (par exemple 75% ou 80%) sans garantie sur le temps d'accès dans le pire des cas (pouvant même être O (n)).

Au fait, D-ary Cuckoo Hashing hachage de coucous avec une cachette " semble pouvoir augmenter le facteur de charge tout en maintenant un temps d'accès constant.

Le pépin de coucou me semble une technique précieuse et je pensais que cela avait déjà été exploré; c'est la raison de ma question.

Answer 7

Je ne peux pas parler pour un logiciel, mais le hachage du coucou est certainement utilisé dans le matériel et devient très populaire. Les principaux fournisseurs d’équipement de réseau se sont penchés sur le hachage de coucous et certains l’utilisent déjà. L’attrait pour le hachage de coucous vient bien sûr du temps de recherche constant, mais aussi du temps d’insertion presque constant.

Bien que l’insertion puisse théoriquement être illimitée, elle peut en pratique être liée à O (log n) du nombre de lignes de la ou des table (s) et, lorsqu’elle est mesurée, le temps d’insertion est d’environ 1,1 * d accès mémoire en moyenne. C'est juste 10% de plus que le minimum absolu! L’accès à la mémoire est souvent le facteur limitant des équipements de réseau.

Les fonctions de hachage indépendantes sont indispensables et il est difficile de les sélectionner correctement. Bonne chance.

Answer 8

À la suite d'un commentaire de "onebyone", j'ai implémenté et testé plusieurs versions du hachage Cuckoo afin de déterminer les besoins réels en mémoire.

Après quelques expériences, l'affirmation qu'il n'est pas nécessaire de regrouper les tâches tant que le tableau n'est pas rempli à 50% semble être vraie, en particulier si le " stash " astuce est mis en œuvre.

Le problème est lorsque vous agrandissez la table. L’approche habituelle consiste à doubler sa taille, mais la nouvelle table n’est utilisée qu’à 25%!

En fait, supposons que la table de hachage ait 16 emplacements, lorsque j'insère le 8ème numéro d’élément, je vais manquer de bons emplacements et je devrai rassembler les éléments. Je vais doubler et maintenant la table est composée de 32 places avec seulement 8 places occupées, ce qui représente 75% de perte!

C’est le prix à payer pour avoir une "constante". temps de récupération (en termes de limite supérieure pour le nombre d'accès / comparaison).

J'ai toutefois conçu un schéma différent: à partir d'une puissance de 2 supérieure à 1, si la table a n emplacements et n est une puissance de deux, ajoutez n / 2 emplacements sinon ajoutez-y n / 3 emplacements:

+--+--+
|  |  |                             2 slots
+--+--+

+--+--+--+
|  |  |  |                          3 slots
+--+--+--+ 

+--+--+--+--+
|  |  |  |  |                       4 slots
+--+--+--+--+

+--+--+--+--+--+--+
|  |  |  |  |  |  |                 6 slots
+--+--+--+--+--+--+

+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |           8 slots
+--+--+--+--+--+--+--+--+

etc.

Avec l’hypothèse selon laquelle le regroupement ne se produira que lorsque la table est remplie à 50%, cela signifie que la table ne sera que 66% vide (1/3) plutôt que 75% vide (1/4) après un reash (c'est à dire le pire des cas).

J'ai également découvert (mais je dois toujours vérifier le calcul) que chaque agrandissement de sqrt (n) à chaque fois, l'espace perdu représente asymptotiquement 50%.

Bien entendu, le prix à payer pour une consommation de mémoire inférieure est l’augmentation du nombre de campagnes qui sera nécessaire à la fin. Hélas, rien ne vient gratuitement.

Je vais aller plus loin si quelqu'un est intéressé.