c - 无法从 C 中的 HashTable 中删除值

Question

我正在尝试从哈希表中删除一个值，当我从链表大小为 1 的数组中删除一个值时代码有效，如果大小大于 1 则出现段错误。

typedef struct hash {
    char *key;
    char *value;
    struct hash *next;
} hashTable;

// generate hash code
unsigned int hashCode(char *key) {
    int sum;
    int i;

    sum = 0;
    i = 0;
    while (key[i])
        sum += key[i++];
    return sum % MAX_HASH;
}

// get hash item size
int hash_size(hashTable *head) {
    int i;
    hashTable *list;

    i = 0;
    list = head;
    if (list) {
        while (list != NULL) {
            i++;
            list = list->next;
        }
    }
    return (i);
}

// free item
void free_hash(hashTable *item) {
    free(item->key);
    free(item->value);
    free(item);
}

// function for deleting item from hash table
void deleteItem(hashTable *table[], char *key) {
    hashTable *head = table[hashCode(key)];
    hashTable *tmp = head;
    hashTable *prev = NULL;

    if (!head)
        return;

    if (hash_size(tmp) == 1) {
        table[hashCode(key)] = 0;
        free_hash(tmp);
        return;
    }
    while (strcmp(tmp->key, key) != 0 && tmp->next != NULL) {
        prev = tmp;
        tmp = tmp->next;
    }

    if (strcmp(tmp->key, key) == 0) {
        if (prev)
            prev->next = tmp->next;
        else
            head = tmp->next;
        free_hash(tmp);
    }
}

// function for inserting item into the table
void insert(hashTable *table[], char *key, char *value) {
    hashTable *tmp;
    hashTable *item;
    unsigned int code;

    item = (hashTable *)malloc(sizeof(hashTable));
    if (!item)
        return;
    item->key = (char *)malloc(sizeof(char) * strlen(key) + 1);
    item->value = (char *)malloc(sizeof(char) * strlen(value) + 1);
    item->next = NULL;
    code = hashCode(key);
    strcpy(item->key, key);
    strcpy(item->value, value);
    if (!table[code])
        table[code] = item;
    else {
        tmp = table[code];
        item->next = tmp;
        table[code] = item;
    }
}

// displaying items
void display(hashTable *table[]) {
    int i = 0;
    hashTable *tmp;

    while (i < MAX_HASH) {
        if (table[i] != NULL) {
            tmp = table[i];
            if (hash_size(tmp) == 1)
                printf("%s=%s\n", tmp->key, tmp->value);
            else {
                while (tmp != NULL) {
                    printf("%s=%s\n", tmp->key, tmp->value);
                    tmp = tmp->next;
                }
            }
        }
        i++;
    }
}

int main(int argc, char const *argv[]) {
    hashTable *table[MAX_HASH];

    memset(table, 0, MAX_HASH * sizeof(hashTable *));
    insert(table, "Bart", "first");
    insert(table, "Lisa", "Second");
    insert(table, "Foo", "bar");
    deleteItem(table, "Lisa");
    display(table);
    return 0;
}

Answer 1

你的代码有很多问题:

• 包含标准头文件，并定义 HASH_MAX:

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  #define HASH_MAX  1027
  

• hashTable 类型令人困惑:它实际上是一个条目列表，哈希表本身就是数组。

• while 循环容易出错:使用更受欢迎的 for 循环，其中循环索引的初始化、测试和增量方便地位于同一位置行:

  for (int i = 0; i < HASH_MAX; i++) {
      // printf hashTable[i]
  }
  

  我知道 42 的本地样式约定明确排除了 for 循环，但您应该游说反对这个有问题的选择。

• display_table()

  中不需要特殊情况 hash_size(tmp) == 1

• 无需强制转换malloc() 的返回值。 sizeof(char) 根据定义为 1。您可以使用 strdup() 复制 C 字符串。

• 在 deleteItem() 中，如果条目是单独的，您总是会删除它:如果条目有不同的键，这是不正确的。此外，您不会将前一个节点或表槽链接到列表的下一个元素。

这是此函数的更正版本:

// function for deleting item from hash table
void deleteItem(hashTable *table[], const char *key) {
    hashTable **link = &table[hashCode(key)];

    while (*link) {
        hashTable *tmp = *link;
        if (strcmp(tmp->key, key) == 0) {
            *link = tmp->next;  // unlink the list node
            free_hash(tmp);
            break;  // remove this if you mean for deleteItem to remove all matching nodes
        } else {
            link = &(*link)->next;
        }
    }
}

这是整个程序的简化版本:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_HASH  1027

typedef struct HashItem {
    char *key;
    char *value;
    struct HashItem *next;
} HashItem;

// generate hash code
unsigned int hashCode(const char *key) {
    unsigned int sum = 0;

    for (int i = 0; key[i]; i++) {
        sum += (unsigned char)key[i] * (i + 1);
    }
    return sum % MAX_HASH;
}

// free item
void freeItem(HashItem *item) {
    free(item->key);
    free(item->value);
    free(item);
}

// function for deleting item from hash table
void deleteItem(HashItem *table[], const char *key) {
    HashItem **link = &table[hashCode(key)];

    while (*link) {
        HashItem *tmp = *link;
        if (strcmp(tmp->key, key) == 0) {
            *link = tmp->next;  // unlink the list node
            freeItem(tmp);
            break;
        } else {
            link = &(*link)->next;
        }
    }
}

// function for inserting item into the table
void insertItem(HashItem *table[], const char *key, const char *value) {
    unsigned int code = hashCode(key);
    HashItem *item = malloc(sizeof(*item));
    if (item != NULL) {
        item->key = strdup(key);
        item->value = strdup(value);
        item->next = table[code];
        table[code] = item;
    }
}

// displaying items
void displayHashTable(HashItem *table[]) {
    for (int i = 0; i < MAX_HASH; i++) {
        for (HashItem *tmp = table[i]; tmp; tmp = tmp->next) {
            printf("%s=%s\n", tmp->key, tmp->value);
        }
    }
}

int main(int argc, char const *argv[]) {
    HashItem *table[MAX_HASH] = { 0 };

    insertItem(table, "Bart", "first");
    insertItem(table, "Lisa", "Second");
    insertItem(table, "Foo", "bar");
    deleteItem(table, "Lisa");
    displayHashTable(table);
    return 0;
}