无法从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循环，但你应该游说这个可疑的选择。

• 没有必要特殊情况hash_size(tmp) == 1在display_table()

• 没有必要投的malloc()返回值。根据定义，sizeof(char)是1。您可以使用strdup()复制C字符串。

• in 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; 
}