C - Création d'une table de hachage de chaînage distincte - Problème
J'ai passé du temps à faire cela, en faisant des efforts pour mettre des variables compréhensibles et des trucs. J'ai essayé de le rendre propre et rangé. Pour que je puisse facilement le déboguer. Mais je n'arrive pas à trouver mon problème ... Le terminal ne produit rien. Aidez-moi à identifier mon erreur!
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct list_node *node_ptr;
struct list_node
{
node_ptr next;
char *key;
char *value;
};
typedef node_ptr LIST;
typedef node_ptr position;
struct hash_table
{
LIST *list_ptr_arr;
unsigned int table_size;
};
typedef struct hash_table *HASHTABLE;
unsigned long long int
hash(const char *key, unsigned int hash_size)
{
unsigned long long int hash;
for(int i = 0; key[i]; i++)
{
hash = (hash<<32)+key[i];
}
return (hash%hash_size);
}
unsigned int
next_prime(int number)
{
int j;
for(int i = number; ; i++)
{
for(j = 2; j<i; j++)
{
if(i%j == 0){break;}
}
if(i==j){return j;}
}
}
HASHTABLE
initialize(unsigned int table_size)
{
HASHTABLE H;
H = (HASHTABLE) malloc(sizeof(struct hash_table));
if(H==NULL){printf("Out of Space!"); return 0;}
H->table_size = next_prime(table_size);
H->list_ptr_arr = (position*) malloc(sizeof(LIST)*table_size);
if(H->list_ptr_arr==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr = (LIST*) malloc(sizeof(struct list_node)*table_size);
for(unsigned int i = 0; i<table_size; i++)
{
if(H->list_ptr_arr[i]==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr[i]=NULL;
}
return H;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
node_ptr prev;
while(entry!=NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
prev = entry;
entry = prev->next;
}
entry = (position) malloc(sizeof(struct list_node));
entry->value = malloc(strlen(value)+1);
entry->key = malloc(strlen(key)+1);
strncpy(entry->key,key,strlen(key));
strncpy(entry->value,value,strlen(value));
entry->next = NULL;
prev->next = entry;
}
void
dump(HASHTABLE H)
{
for(unsigned int i = 0; i<H->table_size; i++)
{
position entry = H->list_ptr_arr[i];
if(H->list_ptr_arr[i]==NULL){continue;}
printf("slot[%d]: ", i);
for(;;)
{
printf("%s|%s -> ", entry->key, entry->value);
if(entry->next == NULL)
{
printf("NULL");
break;
}
entry = entry->next;
}
printf("\n");
}
}
int main()
{
HASHTABLE H = initialize(10);
insert("name1", "David", H);
insert("name2", "Lara", H);
insert("name3", "Slavka", H);
insert("name4", "Ivo", H);
insert("name5", "Radka", H);
insert("name6", "Kvetka", H);
dump(H);
return 0;
}
J'ai essayé de le modifier et de changer un peu certaines choses, mais rien n'a aidé ...
Merci d'avance les gars!
Réponses
Il y a quelques problèmes de beauté et au moins deux erreurs qui cassent le code. Je n'entrerai pas dans les choses mineures, c'est surtout stylistique, mais vos fonctions initialize()et insert()ne fonctionnent pas.
Dans initialize()vous allouez de la mémoire pour H->list_ptr_arraydeux fois. Cela fuit la mémoire de la première allocation sans raison valable, mais bien sûr, cela ne plantera pas votre code, mais une fuite. Dans la deuxième allocation, vous allouez la mauvaise taille, vous utilisez sizeof(struct list_node) * tale_size, mais vous voulez un tableau de pointeurs et non les structures (qui, puisque les structures contiennent des pointeurs, seront plus grandes). Cela, encore une fois, ne fait que gaspiller de la mémoire et ne la plante pas. Pourtant, vous seriez mieux avec la bonne mémoire, que vous pouvez utiliser
H->list_ptr_arr = malloc(table_size * sizeof *H->list_ptr_arr);
Vous n'avez pas besoin de convertir le résultat de malloc(), c'est un void *et vous n'avez pas besoin de le convertir en types de pointeur, mais c'est un problème de style. La partie importante de cette ligne est que nous pouvons obtenir la taille des données sous-jacentes à partir de la variable à laquelle nous assignons, ce qui garantira toujours que nous obtenons la bonne taille, même si nous changeons le type à un moment donné. J'ai aussi tendance à utiliser sizeof(type)de temps en temps, mais sizeof *ptrc'est le meilleur modèle, et cela vaut la peine de s'y habituer.
Quoi qu'il en soit, bien que vous allouiez la mauvaise quantité de mémoire, vous allouez suffisamment de sorte que votre programme ne plante pas à cause de cela. Mais lorsque vous parcourez ensuite les bacs alloués dans la table, vous revenez avec une erreur s'ils le sont NULL. Ils ne sont pas du tout initialisés, donc s'ils le sont NULL(et ils pourraient l'être), c'est par pure chance. Ou, si vous considérez cela comme un signe d'erreur, malheur. Mais si vous considérez ici NULLun signal d'erreur d'allocation, pourquoi initialisez-vous alors chaque bac NULLjuste après avoir conclu que ce n'est pas le cas?
Dans l'état actuel des choses, votre initialisation s'interrompra si vous obtenez un NULLpointeur dans le tableau, et comme vous ne vérifiez pas les erreurs d'allocation dans main()(ce qui convient pour un test), cela pourrait être la raison pour laquelle votre programme plante. Ce n'est pas le problème principal, et cela n'arrive que si, par hasard, vous en avez NULLdans l'un de vos bacs, mais cela peut arriver. Ne faites pas la vérification NULLlorsque vous parcourez les bacs. Les bacs ne sont pas initialisés. Réglez simplement chacun sur NULL.
C'est dans insert()le problème principal réside. Votre prevvariable n'est pas initialisée avant le while-loop, et si vous n'entrez pas dans la boucle, elle ne le sera pas non plus. Définir prev->next = entryquand prevest non initialisé provoque des problèmes et est un candidat probable pour une erreur de plantage. Surtout en considérant que la première fois que vous insérez quelque chose dans une poubelle, le entrysera NULL, donc vous déclencherez l'erreur la toute première fois. Ce qui se passe lorsque vous déréférencer un pointeur non initialisé n'est pas défini, mais cela signifie rarement quelque chose de bon. Un crash est le meilleur des cas.
Je comprends la logique ici. Vous voulez vous déplacer le prevlong de la liste pour pouvoir insérer le nouveau entryà la fin, et vous n'avez pas de dernier élément avant de parcourir les entrées du bac. Mais cela ne signifie pas que vous ne pouvez pas avoir de pointeur initialisé vers l'endroit où vous souhaitez insérer une nouvelle entrée. Si vous utilisez un pointeur vers un pointeur, vous pouvez commencer par l'entrée dans le tableau de la table. Ce n'est pas un list_node, donc un list_node *ne fera pas pour prev, mais un list_node **fonctionnera très bien. Vous pouvez faire quelque chose comme ceci:
node_ptr new_entry(const char *key, const char *value)
{
node_ptr entry = malloc(sizeof *entry);
if (!entry) abort(); // Add error checking
entry->value = malloc(strlen(value) + 1);
entry->key = malloc(strlen(key) + 1);
strncpy(entry->key, key, strlen(key));
strncpy(entry->value, value, strlen(value));
entry->next = NULL;
return entry;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
// Make sure that we always have a prev, by pointing it
// to the location where we want to insert a new entry,
// which we want at the bin if nothing else
node_ptr *loc = &H->list_ptr_arr[slot];
while(entry != NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
// make loc the entry's next
loc = &entry->next;
// and move entry forward (we don't need prev->next now)
entry = entry->next;
}
// now loc will hold the address we should put
// the entry in
*loc = new_entry(key, value);
}
Bien sûr, étant donné que les listes dans les bacs ne sont pas triées ou conservées dans un ordre particulier (sauf s'il y a des contraintes que vous n'avez pas mentionnées), vous n'avez pas besoin d'ajouter de nouvelles entrées. Vous pouvez également les ajouter. Ensuite, vous n'avez pas besoin de faire glisser un tel loclong pour une autre recherche linéaire. Vous pouvez faire quelque chose comme:
node_ptr find_in_bin(const char *key, node_ptr bin)
{
for (node_ptr entry = bin; entry; entry = entry->next) {
if(strcmp(entry->key, key)==0)
return entry;
}
return 0;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr *bin = &H->list_ptr_arr[slot];
node_ptr entry = find_in_bin(key, *bin);
if (entry) {
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
} else {
*bin = new_entry(key, value, *bin);
}
}
Si vous corrigez l'initialisation et l'insertion de cette façon, je pense que le code devrait fonctionner. C'est le cas pour les quelques tests que je lui ai soumis, mais j'ai peut-être raté quelque chose.
Pas une erreur en tant que telle, mais quelque chose que je vais quand même commenter rapidement. La next_prime()fonction ressemble à une version lente du tamis d'Eratosthène. C'est bien, il calcule un premier (sauf si j'ai manqué quelque chose), mais ce n'est pas quelque chose dont vous avez besoin. Si vous recherchez cela sur Google, vous trouverez des tableaux des premiers K premiers, pour des K. assez grands. Vous pouvez facilement les intégrer dans votre code. Autrement dit, si vous voulez absolument que vos tables aient des tailles de premier ordre. Vous n'en avez pas besoin, cependant. Il n'y a rien de mal à avoir des tables d'autres tailles.
Il y a quelques avantages à modulo premiers pour le hachage, mais la table de hachage n'a pas besoin d'avoir la taille du premier pour que cela fonctionne. Si vous avez un grand P premier et une table de hachage de taille M, vous pouvez faire ((i% P)% M) et obtenir les avantages de faire modulo P et la commodité d'avoir une taille de table M. Lorsque vous redimensionnez les tables et tel, il est plus facile si M est une puissance de deux, et alors la dernière opération modulo peut être un masquage de bits très rapide:
#define mask_k(n,k) (n & ((1 << k) - 1))
et puis plus tard ...
int index = mask_k(i % P, k); // where table size is 1 << k
Le i % Ppeut - être pas nécessaire non plus , cela dépend de la qualité de votre fonction de hachage est. Si vous avez une fonction de hachage qui vous donne des nombres aléatoires proches, alors les bits isont aléatoires, puis les kbits les moins significatifs le sont également et % Pne fait rien pour l'améliorer. Mais si vous voulez faire modulo a prime, vous pouvez le faire pour un grand prime et le masquer à une taille de table plus petite, vous n'avez donc pas à utiliser une taille de table qui est un prime. Et si vous voulez avoir une taille de table qui est de toute façon un nombre premier, utilisez une table de nombres premiers. Il est lent de devoir calculer de nouveaux nombres premiers à chaque fois que vous redimensionnez le tableau.