C语言 使用字符串键问题的哈希表插入实现

Question

我有一个问题，我已经尝试解决好几天了。我尝试从三个结构创建一个哈希表，第一个结构带有指向具有键值对的指针桶。键应该是一个字符串（char * arr）。我不完全掌握如何为它创建一个有效的插入函数，我的目标是在我的代码中做的是尝试查看存储桶 h 中是否存在键。我觉得我的逻辑和语法有问题。如果有人能在路上帮助我，将不胜感激。

我在维基百科和YouTube视频上查看了哈希表理论，但没有一个使用三个结构和字符串键。 这就是我感到卡住的地方。

#include<stdio.h>
#include"hashtable.h"
struct hash_table
{
    Bucket *bucket;
    int hash_size;
};
struct bucket
{
    Pair *list;
    int capacity;
    int size;
};
struct pair
{
    char *key;
    int value;
};
Pair copy_key(char *key, int value)
{
    Pair copy = malloc(sizeof(Pair));
    copy->key = key;
    copy->value = value;
    return copy;
}
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;
    while (c = *str++)          
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash;
}
void hash_insert (HashTable *tab, const char *key, int value)
{
    unsigned long h = hash(key) % tab->hash_size;
    int i = 0;
    while(tab->bucket[h]->list[i]->key != NULL && (i < tab->bucket->size))
    {
        Pair pair = copy_key(key,value);
        if (tab->bucket[h]->list[i]->key == pair->key)
        {
            tab->bucket[h]->list[i]->value == pair->value;
            return;
        }
    }
}

具有字符串键的三结构层哈希表的工作插入函数。

Answer 1

您的插入函数中存在很多问题：

void hash_insert (HashTable *tab, const char *key, int value)
{
    unsigned long h = hash(key) % tab->hash_size;
    int i = 0;
    // depending on how you initialise your hash table, the list might yet
    // be NULL(!) - so you possibly yet need a check for!
    // you need FIRST to check if the index is yet valid, THEN check
    // if there is a key!
    //while(tab->bucket[h]->list[i]->key != NULL && (i < tab->bucket->size))
    while(i < tab->bucket[h].size && tab->bucket[h].list[i].key != NULL)
    // additionally: you have a pointer, index operator [] dereferences
    // -> you have a struct directly -> need to access via .
    {
        //Pair pair = copy_key(key,value);
        // BAD idea: you malloc a struct, but never free it -> memory leak!
        if (tab->bucket[h].list[i].key == /*pair->*/key)
        // compare directly!
        // however: == compares the pointers only - most likely, though,
        // you have created a new string somewhere else just with same
        // CONTENT - in this case you need to compare via strcmp:
        if (strcmp(tab->bucket[h].list[i].key, key) == 0)
        {
            //tab->bucket[h]->list[i]->value == pair->value;
            // comparison? assuming you wanted to assign:
            tab->bucket[h].list[i].value = value;
            return;
        }
    }
    // end of while reached, the key was not yet found!
    // -> you need to insert it here:
    if(i == tab->bucket[h].size)
    {
        // no space in buckets left!
        // -> need to realloc (leaving this to you)
        // BUT: you might want to consider overall fill grade or maximum fill
        // grade for buckets and do a complete re-hash of all contents...
    }
    // assuming we insert in THIS bucket:
    tab->bucket[h].list[i].key = ???;
    tab->bucket[h].list[i].value = value;
}

??? - 嗯，取决于。我几乎假设您希望哈希映射拥有它包含的键字符串。这样，您就不会将密钥作为超出范围的本地数组或之后删除动态分配的字符串！所以：

tab->bucket[h].list[i].key = strdup(key);

如果要避免不必要的复制，因为已经分配了字符串，则可以添加另一个参数：int isTakeOwnwership（或bool，但您需要#include <stdbool.h>）：

tab->bucket[h].list[i].key = isTakeOwnership ? key : strdup(key);

在这两个示例中，我没有检查 strdup 为 NULL 的结果 - 您需要这样做并处理内存分配失败的情况（也许在您的插入函数中添加一个返回值指示成功或失败？

不要忘记在元素删除时free映射中的字符串!!请记住，您的地图拥有所有权。