哈希表添加-C

Question

在以下算法中出现段错误以将元素添加到哈希中的正确存储桶table。

我的结构很基础：

struct kv {
    char* key;
    unsigned val;
    struct kv* next;
};

struct hashtable {
    struct kv** table;
    unsigned size;
};

还有我的越野车功能：

    struct kv* ht_find_or_put(char* word, unsigned value,
                                  struct hashtablet* hashtable,
                                  unsigned (*hash)(char*))
    {
        unsigned index = hash(word) % hashtable->size;
        struct kv* ke = malloc(sizeof (struct kv));

        for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
        {
            if (strcmp(ke->key, word) == 0)
                return ke;
        }

        if (ke == NULL)
        {
            ke->key = word;
            ke->val = value;
            ke->next = hashtable->table[index];
            hashtable->table[index] = ke;
        }
   return ke;
}

我知道我还没有添加所有测试（如果 malloc 失败等）只是试图调试这个特定问题...

我正在这样分配我的 table：

struct hashtable* hashtable_malloc(unsigned size)
{
    struct hashtable *new_ht = malloc(sizeof(struct hashtable));
    new_ht->size = size;
    new_ht->table = malloc(sizeof(struct kv) * size);

    for(unsigned i = 0; i < size; i++)
        new_ht->table[i] = NULL;

    return new_ht;
}

我们将不胜感激任何形式的帮助。我才刚刚开始学习。

Answer 1

第一个问题是内存泄漏，例如- 您使用 malloc 分配内存，但在覆盖指针时丢失了对它的引用：

// allocate memory
struct kv* ke = malloc(sizeof (struct kv));
//   lose the reference
//   VVVVVVVVVVV
for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)

可能导致段错误的第二个问题是您尝试取消引用空指针：

if (ke == NULL)
{
    // ke is NULL, you can't de-reference it
    ke->key = word;
    ke->val = value;
    ke->next = hashtable->table[index];
    hashtable->table[index] = ke;
}

解决方案是，恕我直言，只有在找不到新元素时才分配和放置新元素：

struct kv* ht_find_or_put(char* word, unsigned value, struct hashtablet* hashtable, unsigned (*hash)(char*))
{
    unsigned index = hash(word) % hashtable->size;
    struct kv* ke;

    // first we try to find the node
    for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
    {
        if (strcmp(ke->key, word) == 0)
            return ke;
    }

    // didn't find it - lets create and put a new one.    
    if (ke == NULL)
    {
        ke = malloc(sizeof (struct kv));
        // later add a check if the allocation succeded...
        ke->key = word;
        ke->val = value;
        ke->next = hashtable->table[index];
        hashtable->table[index] = ke;
    }
    return ke;
}

由于我不想引入全新的代码，那样只会让您感到困惑，所以我对原始代码进行了最少的更改。

哈希表添加-C

Hashtable Add - C

c

hashtable