Implémentation de Map <string, string> dans C

Question

Pour une raison quelconque, je dois l'implémenter moi-même, et je ne peux pas utiliser libs. Pour mapper rapidement, d'abord, je mappe la clé à un entier, et utilise cet entier comme une clé interne. Ensuite, j'applique la carte, qui me donne la fonction de cartographie. Cependant, lorsque j'utilise la clé de chaîne pour calculer la clé entière interne, il m'arrive d'obtenir le même nombre entier à partir d'une chaîne différente. Comment puis-je résoudre le problème?

Answer 1

Vous ne pouvez pas éviter cela. Il y a plus de chaînes possibles que d'entiers, donc les collisions de hachage sont imminentes. Lisez les hashmaps - c'est une structure de données qui prend explicitement en compte les collisions et qui les contourne.

Answer 2

Ceci est ce que l'on appelle des collisions, mais le plus simple consiste à faire de chaque compartiment de votre Hashmap une liste d'éléments ayant le même hachage. Ensuite, sur un obtenez tout ce que vous avez à faire est parcourir la liste jusqu'à ce que vous trouviez l'élément que vous recherchez.

Answer 3

Une structure de données cartographiques et une "collision" ne peuvent pas être séparées. la façon dont vous avez commencé votre implémentation semble bien, voici comment vous devez gérer les collisions:

Ajout d'une nouvelle entrée dans la carte

1. calculate hashcode pour key
2. Compute index de hashcode (plus ou moins index = hashcode value% size of keyset)
3. si keyset[index] est non nulle
   1. si keyset [index]! = Touche (c.-à-d. pour les chaînes, l'utilisation strcmp) incrémenter index module size of keyset, puis goto 3
4. mis value en entryset[index]

Obtenir une valeur de la carte

1. calculate hashcode pour key
2. calculer index à partir de h ashcode (plus ou moins index = hashcode value% size of keyset)
3. si keyset[index] est non nul
   1. si keyset [index]! = clé (ie.pour les chaînes, l'utilisation strcmp) incrémenter index module size of keyset, puis goto 3
4. si keyset[index] est null return null
5. retour entryset[index]

Suppression d'une entrée de la carte

1. calculer hashcode pour key
2. Compute index de hashcode (plus ou moins index = hashcode value% size of keyset)
3. si keyset[index] est non nul
   1. si keyset [index]! = Clé (ie. pour les chaînes, l'utilisation strcmp) incrémenter index module size of keyset, puis goto 3
4. mis keyset[index] et entryset[index] null

Comme vous pouvez le voir, vous pouvez mettre l'étape 1 à 3 en fonction int findIndexFromKey(Map *map, char *key); et plus du travail est fait

** EDIT **

Bien sûr, vous devez également vérifier si votre m ap n'est pas complet avant (ou pendant) l'ajout d'une nouvelle entrée, sinon vous ne bouclerez pas indéfiniment.