Implémenter une HashMap

Comment créer une Hashmap en C à partir de zéro? Quels seraient les parameters pris en compte et comment testeriez-vous le hashmap quant à sa qualité? Comme dans les cas de test de performances que vous devez exécuter avant de dire que votre carte de hachage est complète.

Eh bien, si vous connaissez les bases derrière eux, cela ne devrait pas être trop difficile.

Généralement, vous créez un tableau appelé “buckets” qui contient la clé et la valeur, avec un pointeur facultatif pour créer une liste liée.

Lorsque vous accédez à la table de hachage avec une clé, vous traitez la clé avec une fonction de hachage personnalisée qui renverra un entier. Vous prenez alors le module du résultat et c’est l’emplacement de votre index de tableau ou “bucket”. Ensuite, vous vérifiez la clé non assortie avec la clé stockée, et si elle correspond, vous avez trouvé le bon endroit.

Sinon, vous avez eu une “collision” et devez parcourir la liste chaînée et comparer les clés jusqu’à ce que vous obteniez une correspondance. (notez que certaines implémentations utilisent un arbre binary au lieu d’une liste liée pour les collisions).

Découvrez cette implémentation rapide de la table de hachage:

http://attractivechaos.awardspace.com/khash.h.html

La meilleure approche dépend de la dissortingbution des clés attendue et du nombre de collisions. Si relativement peu de collisions sont attendues, peu importe la méthode utilisée. Si un grand nombre de collisions sont attendues, alors l’utilisation dépend des coûts de réarchivage ou de vérification, ou de la manipulation de la structure de données du compartiment extensible.

Mais voici l’exemple de code source d’ une implémentation d’Hashmap en C

Le but principal d’un hashmap est de stocker un dataset et de fournir des recherches en temps quasi-constant à l’aide d’une clé unique. Il y a deux styles communs d’implémentation de hashmap:

  • Chaînage séparé: un avec un tableau de compartiments (listes liées)
  • Adressage ouvert: un tableau unique alloué avec un espace supplémentaire afin que les collisions d’index puissent être résolues en plaçant l’entrée dans un logement adjacent.

Le chaînage séparé est préférable si le hashmap peut avoir une mauvaise fonction de hachage, il n’est pas souhaitable de pré-allouer le stockage pour les emplacements potentiellement inutilisés, ou les entrées peuvent avoir une taille variable. Ce type de hashmap peut continuer à fonctionner de manière relativement efficace même lorsque le facteur de charge dépasse 1,0. De toute évidence, il faut de la mémoire supplémentaire dans chaque entrée pour stocker les pointeurs de liste liés.

Les hachages utilisant l’adressage ouvert présentent des avantages potentiels en termes de performances lorsque le facteur de charge rest inférieur à un certain seuil (généralement environ 0,7) et qu’une fonction de hachage raisonnablement bonne est utilisée. Cela est dû au fait qu’ils évitent les ratés potentiels du cache et de nombreuses petites allocations de mémoire associées à une liste chaînée, et effectuent toutes les opérations dans un tableau contigu, pré-alloué. L’itération à travers tous les éléments est également moins chère. Les hashmaps utilisant l’adressage ouvert doivent être réalloués pour conserver un facteur de charge idéal, ou ils font face à une pénalité de performance significative. Il est impossible que leur facteur de charge dépasse 1,0.

Certaines mesures de performance clés à évaluer lors de la création d’un hashmap incluent:

  • Facteur de charge maximum
  • Nombre moyen de collisions à l’insertion
  • Répartition des collisions: une dissortingbution inégale (clustering) pourrait indiquer une mauvaise fonction de hachage.
  • Temps relatif pour diverses opérations: mettre, obtenir, supprimer des entrées existantes et non existantes.

Voici une implémentation de hashmap flexible que j’ai faite. J’ai utilisé l’adressage ouvert et le sondage linéaire pour la résolution de collision.

https://github.com/DavidLeeds/hashmap

Il existe d’autres mécanismes pour gérer le débordement que la simple liste liée d’entrées de débordement, qui gaspille par exemple beaucoup de mémoire.

Le mécanisme à utiliser dépend, entre autres, de la possibilité de choisir la fonction de hachage et de choisir plusieurs options (pour implémenter par exemple un double hachage pour gérer les collisions); si vous prévoyez d’append souvent des éléments ou si la carte est statique une fois remplie; si vous avez l’intention de supprimer des éléments ou non; …

La meilleure façon de l’implémenter est de penser d’abord à tous ces parameters, puis de ne pas les coder vous-même, mais de choisir une implémentation existante mature. Google a quelques bonnes implémentations, par exemple http://code.google.com/p/google-sparsehash/