Implémentation d'un HashMap
Comment créer un Hashmap en C à partir de zéro ? Quels seraient les paramètres pris en compte et comment testeriez - vous le hashmap quant à sa qualité ? Comme dans ce qui serait des cas de test de référence que vous devez exécuter avant de dire que votre carte de hachage est terminée.
4 réponses
Eh bien, si vous connaissez les bases derrière eux, il 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 retournera un entier. Vous prenez ensuite le module du résultat et c'est l'emplacement de votre index de tableau ou "seau". Ensuite vous vérifiez la clé non hachée avec la clé stockée, et si cela correspond, alors vous avez trouvé le bon endroit.
Sinon, vous avez eu une "collision" et devez explorer la liste liée et comparer les clés jusqu'à ce que vous correspondez. (notez que certaines implémentations utilisent un arbre binaire au lieu d'une liste liée pour les collisions).
Découvrez cette implémentation rapide de la table de hachage:
La meilleure approche dépend de la distribution et du nombre de clés attendus de collisions. Si relativement peu de collisions sont attendues, c'est vraiment n'importe la méthode utilisée. Si beaucoup de collisions sont attendu, alors lequel utiliser dépend du coût de ressasser ou sondage vs manipulation de la structure de données de seau extensible.
Mais voici un exemple de code source de une implémentation Hashmap en C
L'objectif principal d'un hashmap est de stocker un ensemble de données et de fournir des recherches en temps quasi constant à l'aide d'une clé unique. Il existe deux styles communs d'implémentation de hashmap:
- chaînage séparé: un avec un tableau de compartiments (listes liées)
- adressage ouvert: un seul tableau alloué avec un espace supplémentaire afin que les collisions d'index puissent être résolues en plaçant l'entrée dans un emplacement adjacent.
Un chaînage séparé est préférable si le hashmap peut avoir un hachage médiocre fonction, 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. Évidemment, il y a de la mémoire supplémentaire requise dans chaque entrée pour stocker les pointeurs de liste liés.
HashMaps utilisant l'adressage ouvert ont des avantages potentiels de performance lorsque le facteur de charge est maintenu en dessous d'un certain seuil (généralement environ 0,7) et un raisonnablement bon fonction de hachage est utilisée. En effet, ils évitent les échecs potentiels de cache et de nombreuses petites allocations de mémoire associées à une liste liée, et effectuent toutes les opérations dans un tableau pré-alloué contigu. Itération à travers tous les éléments est également moins cher. Les hashmaps utilisant l'adressage ouvert doivent être réalloués à une taille plus grande et hachés pour maintenir 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 incluraient:
- Facteur de charge maximal
- Nombre moyen de collisions lors de l'insertion
- Distribution des collisions: distribution inégale (clustering) pourrait indiquer une mauvaise fonction de hachage.
- temps relatif pour diverses opérations: put, get, remove des entrées existantes et non existantes.
Voici une implémentation HashMap flexible que j'ai faite. J'ai utilisé l'adressage ouvert et linéaire sondage pour la résolution des collisions.
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, par exemple, gaspille beaucoup de mémoire.
Le mécanisme à utiliser dépend entre autres de si vous pouvez choisir la fonction de hachage et en choisir plusieurs (pour implémenter par exemple le double hachage pour gérer les collisions); si vous prévoyez d'ajouter 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 mettre en œuvre ceci est d'abord pensez à tous ces paramètres et ensuite ne pas le coder vous-même mais pour choisir une implémentation existante mature. Google a quelques bonnes implémentations -- par exemple, http://code.google.com/p/google-sparsehash/