我有一个关于哈希表实现的 C 编程问题。我已经实现了用于存储一些字符串的哈希表。 我在处理哈希冲突时遇到问题。我正在遵循链接链表方法来解决这个问题,但不知何故,我的代码的行为有所不同。我无法调试它。有人可以帮忙吗?
这就是我面临的情况: 说第一次,我插入一个名为 gaur 的字符串。我的 HashMap 计算索引为0并成功插入字符串。然而,当另一个字符串在计算时其哈希值也为 0 时,我之前的值就会被覆盖,即 gaur 将被新字符串替换。
这是我的代码:
struct list
{
char *string;
struct list *next;
};
struct hash_table
{
int size; /* the size of the table */
struct list **table; /* the table elements */
};
struct hash_table *create_hash_table(int size)
{
struct hash_table *new_table;
int i;
if (size<1) return NULL; /* invalid size for table */
/* Attempt to allocate memory for the table structure */
if ((new_table = malloc(sizeof(struct hash_table))) == NULL) {
return NULL;
}
/* Attempt to allocate memory for the table itself */
if ((new_table->table = malloc(sizeof(struct list *) * size)) == NULL) {
return NULL;
}
/* Initialize the elements of the table */
for(i=0; i<size; i++)
new_table->table[i] = '\0';
/* Set the table's size */
new_table->size = size;
return new_table;
}
unsigned int hash(struct hash_table *hashtable, char *str)
{
unsigned int hashval = 0;
int i = 0;
for(; *str != '\0'; str++)
{
hashval += str[i];
i++;
}
return (hashval % hashtable->size);
}
struct list *lookup_string(struct hash_table *hashtable, char *str)
{
printf("\n enters in lookup_string \n");
struct list * new_list;
unsigned int hashval = hash(hashtable, str);
/* Go to the correct list based on the hash value and see if str is
* in the list. If it is, return return a pointer to the list element.
* If it isn't, the item isn't in the table, so return NULL.
*/
for(new_list = hashtable->table[hashval]; new_list != NULL;new_list = new_list->next)
{
if (strcmp(str, new_list->string) == 0)
return new_list;
}
printf("\n returns NULL in lookup_string \n");
return NULL;
}
int add_string(struct hash_table *hashtable, char *str)
{
printf("\n enters in add_string \n");
struct list *new_list;
struct list *current_list;
unsigned int hashval = hash(hashtable, str);
printf("\n hashval = %d", hashval);
/* Attempt to allocate memory for list */
if ((new_list = malloc(sizeof(struct list))) == NULL)
{
printf("\n enters here \n");
return 1;
}
/* Does item already exist? */
current_list = lookup_string(hashtable, str);
if (current_list == NULL)
{
printf("\n DEBUG Purpose \n");
printf("\n NULL \n");
}
/* item already exists, don't insert it again. */
if (current_list != NULL)
{
printf("\n Item already present...\n");
return 2;
}
/* Insert into list */
printf("\n Inserting...\n");
new_list->string = strdup(str);
new_list->next = NULL;
//new_list->next = hashtable->table[hashval];
if(hashtable->table[hashval] == NULL)
{
hashtable->table[hashval] = new_list;
}
else
{
struct list * temp_list = hashtable->table[hashval];
while(temp_list->next!=NULL)
temp_list = temp_list->next;
temp_list->next = new_list;
hashtable->table[hashval] = new_list;
}
return 0;
}
最佳答案
我还没有检查确认,但这行看起来错误:
hashtable->table[hashval] = new_list;
这位于add_string
最后一个例子的末尾。你有:
- 正确创建了新的
结构列表
来保存正在添加的值 - 正确找到该哈希值的链表头,并一直找到它的末尾
- 正确地将新的
结构列表
放在链表的末尾
但是,通过我上面引用的行,您告诉哈希表将 new struct list
放在 head这个哈希值的链表!从而丢弃之前存在的整个链表。
我认为你应该忽略我上面引用的那句话,看看你进展如何。前面的行正确地将其附加到现有列表的末尾。
关于关于哈希表实现的C编程问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2847287/