Mise en œuvre d'une HashMap
Comment aller sur la création d'une table de hachage en C à partir de zéro ?
Quels seraient les paramètres pris en considération et comment voulez-vous tester la table de hachage comment il est bon ? Comme dans ce qui serait l'indice de référence des cas de test à laquelle vous avez besoin de courir avant de vous dire que votre hash carte est complète.
Vous devez vous connecter pour publier un commentaire.
Bien si vous connaissez les principes de base derrière eux, il ne devrait pas être trop dur.
En général, vous créez un tableau appelé "seaux" qui contiennent la clé et la valeur, en option avec un pointeur pour créer une liste liée.
Lorsque vous accédez à la table de hachage avec une clé, la clé avec un custom fonction de hachage qui renvoie un entier. Vous prenez alors le module de la suite et c'est l'emplacement de votre index de tableau ou de "seau". Ensuite, vous vérifiez la unhashed clé avec la clé stockée, et si elle correspond, alors vous avez trouvé le bon endroit.
Sinon, vous avez eu une "collision" et doit ramper à travers la liste, et de comparer les touches jusqu'à ce que vous correspondre. (notez que certaines implémentations utiliser un arbre binaire au lieu de lié liste pour les collisions).
Check out rapide, cette table de hachage de mise en œuvre:
http://attractivechaos.awardspace.com/khash.h.html
La meilleure approche repose sur la clé de répartition et le nombre
de collisions. Si relativement peu de collisions sont attendus, il est vraiment
n'importe la méthode utilisée. Si beaucoup de collisions sont
attendu, ensuite, pour l'utiliser dépend du coût de ressasser ou
sondage contre la manipulation de l'extensible seau structure de données.
Mais ici, c'est le code source de l'exemple de Une table de hachage de la mise en Œuvre en C
Le but primaire d'une table de hachage est de stocker un ensemble de données et de fournir près de la constante de temps des recherches sur elle à l'aide d'une clé unique. Il existe deux styles de hashmap mise en œuvre:
Séparer le chaînage est préférable si la table de hachage peut avoir une mauvaise fonction de hachage, il n'est pas souhaitable de pré-allouer du stockage pour potentiellement les emplacements non utilisés, ou les entrées peuvent avoir une taille variable. Ce type de table de hachage peut continuer à fonctionner de façon relativement efficace, même lorsque le facteur de charge est supérieure à 1,0. Évidemment, il y a la mémoire supplémentaire requise dans chaque entrée pour stocker des liste de pointeurs.
Hashmaps l'aide en abordant ont un potentiel de rendement avantages lorsque le facteur de charge est maintenu en dessous d'un certain seuil (généralement d'environ 0,7) et une bonne fonction de hachage est utilisée. C'est parce qu'ils éviter d'éventuels défauts de cache et de nombreuses petites allocations de mémoire associé à une liste chaînée, et effectuer toutes les opérations dans une zone contiguë, pré-alloués tableau. Itération à travers tous les éléments est aussi moins cher. Le hic, c'est hashmaps ouvrez à l'aide de l'adressage doit être réaffecté à une plus grande taille et de rabâchage de maintenir un idéal du facteur de charge, ou ils font face à une diminution importante de la performance. Il est impossible de leur facteur de charge de supérieur à 1,0.
Certains des principaux indicateurs de performance pour évaluer lors de la création d'une table de hachage seraient les suivantes:
Voici un flexible hashmap mise en œuvre que j'ai faite. J'ai utilisé en abordant et linéaire de sondage pour la résolution de collision.
https://github.com/DavidLeeds/hashmap
Il existe d'autres mécanismes pour gérer le dépassement de la simple d'esprit lié liste de dépassement des entrées qui, par exemple, les déchets de beaucoup de mémoire.
Mécanisme à utiliser dépend, entre autres choses, si vous pouvez choisir la fonction de hachage et possible de sélectionner plus d'un (à mettre en œuvre par exemple, le double hachage pour gérer les collisions); si vous vous attendez à souvent ajouter des éléments ou si la carte est statique, une fois rempli; si vous avez l'intention de supprimer des éléments ou non; ...
La meilleure façon de mettre en œuvre c'est d'abord penser à tous ces paramètres et donc pas de code vous-même, mais de choisir une mature de mise en œuvre existantes. Google a quelques bonnes implémentations -- par exemple, http://code.google.com/p/google-sparsehash/