Невозможно удалить значение из HashTable в C

Question

Я пытаюсь удалить значение из хеш-таблицы, код работает, когда я удаляю значение из массива, где размер связанного списка равен единице, а затем segfaults, если размер больше, чем 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.

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