С программированием на вопрос о реализации хеш-таблицы

Question

У меня есть вопрос по программированию на C для реализации хеш-таблицы. Я реализовал хеш-таблицу для хранения некоторых строк. У меня проблема при работе с хэш-коллизиями. Я следую цепочному подходу связанного списка, чтобы преодолеть проблему, но, так или иначе, мой код ведет себя по-другому. Я не могу отладить его. Может ли кто-нибудь помочь?

Вот с чем я сталкиваюсь: Скажем в первый раз, я вставляю строку под названием гаур. Моя хэш-карта вычисляет индекс как 0 и успешно вставляет строку. Однако, когда другая строка, чей хэш также при вычислении оказывается равной 0, мое предыдущее значение перезаписывается, т.е. гаур будет заменен новой строкой.

Это мой код:

struct list
{ 
 char *string;
 struct list *next; 
};

struct hash_table
{
 int size;     /* the size of the table */
 struct list **table; /* the table elements */
}; 

struct hash_table *create_hash_table(int size)
{
    struct hash_table *new_table;
    int i;

    if (size<1) return NULL; /* invalid size for table */

    /* Attempt to allocate memory for the table structure */
    if ((new_table = malloc(sizeof(struct hash_table))) == NULL) {
        return NULL;
    }

    /* Attempt to allocate memory for the table itself */
    if ((new_table->table = malloc(sizeof(struct list *) * size)) == NULL) {
        return NULL;
    }

    /* Initialize the elements of the table */
    for(i=0; i<size; i++) 
     new_table->table[i] = '\0';

    /* Set the table's size */
    new_table->size = size;

    return new_table;
}


unsigned int hash(struct hash_table *hashtable, char *str)
{
    unsigned int hashval = 0;
    int i = 0;

    for(; *str != '\0'; str++)
    {
     hashval += str[i];
     i++;
    }

    return (hashval % hashtable->size);
}

struct list *lookup_string(struct hash_table *hashtable, char *str)
{
    printf("\n enters in lookup_string \n");

    struct list * new_list;
    unsigned int hashval = hash(hashtable, str);

    /* Go to the correct list based on the hash value and see if str is
     * in the list.  If it is, return return a pointer to the list element.
     * If it isn't, the item isn't in the table, so return NULL.
    */


    for(new_list = hashtable->table[hashval]; new_list != NULL;new_list = new_list->next)
    {
        if (strcmp(str, new_list->string) == 0)
          return new_list;
    }
    printf("\n returns NULL in lookup_string \n");
    return NULL;
}


int add_string(struct hash_table *hashtable, char *str)
{
    printf("\n enters in add_string \n");

    struct list *new_list;
    struct list *current_list;
    unsigned int hashval = hash(hashtable, str);
    printf("\n hashval = %d", hashval);

    /* Attempt to allocate memory for list */
    if ((new_list = malloc(sizeof(struct list))) == NULL)
    {
     printf("\n enters here \n");
     return 1;
    }

    /* Does item already exist? */
    current_list = lookup_string(hashtable, str);

    if (current_list == NULL)
    {
     printf("\n DEBUG Purpose \n");
     printf("\n NULL \n");
    }

    /* item already exists, don't insert it again. */
    if (current_list != NULL)
    {
     printf("\n Item already present...\n");
     return 2;
    }

    /* Insert into list */
    printf("\n Inserting...\n");

    new_list->string = strdup(str);
    new_list->next = NULL;
    //new_list->next = hashtable->table[hashval];
    if(hashtable->table[hashval] == NULL)
    {
      hashtable->table[hashval] = new_list;
    }
    else
    {
      struct list * temp_list = hashtable->table[hashval];
      while(temp_list->next!=NULL)
       temp_list = temp_list->next;

      temp_list->next = new_list;
      hashtable->table[hashval] = new_list;
    }

    return 0;
}

Answer 1

Я не проверял, чтобы подтвердить, но эта строка выглядит неправильно:

hashtable->table[hashval] = new_list;

Это в самом конце последнего случая add_string. У вас есть:

• правильно создал новый struct list для хранения добавляемого значения
• правильно нашел заголовок связанного списка для этого хэш-значения и прошел до конца
• правильно поместил новый struct list в конец связанного списка

НО тогда, со строкой, которую я цитирую выше, вы говорите хэш-таблице поместить новый struct list в заголовок связанного списка для этого хэш-значения! Таким образом выбрасывая весь связанный список, который был там прежде.

Я думаю, вы должны опустить строку, которую я цитирую выше, и посмотреть, как вы продвигаетесь. Предыдущие строки правильно добавляют его в конец существующего списка.

Answer 2

Заявление hashtable->table[hashval] = new_list; является виновником. Вы ввели new_list (я думаю, что лучшее имя было бы new_node) в конце связанного списка. Но затем вы перезаписываете этот связанный список с new_list, который является просто одним узлом. Просто удалите это утверждение.

Answer 3

Как уже отмечали другие, вы идете в конец списка с помощью temp_list, добавляя к нему new_list и выбрасывая существующий список.

Поскольку одно и то же значение NULL используется для обозначения пустого сегмента и конца списка, гораздо проще поместить новый элемент в начало списка.

Вам также следует выполнить любой тест, который приведет к тому, что новый элемент не будет добавлен до его создания, иначе вы потеряете память.

У меня также была бы внутренняя функция поиска, которая принимает значение хеша, в противном случае вам придется вычислять его дважды

int add_string(struct hash_table *hashtable, char *str)
{
    unsigned int hashval = hash(hashtable, str);

    /* item already exists, don't insert it again. */
    if (lookup_hashed_string(hashtable, hashval, str))
        return 2;

    /* Attempt to allocate memory for list */
    struct list *new_list = malloc(sizeof(struct list));

    if (new_list == NULL)
        return 1;

    /* Insert into list */
    new_list->string = strdup(str);
    new_list->next = hashtable->table[hashval];

    hashtable->table[hashval] = new_list;

    return 0;
}

Answer 4

Хеш-функция должна быть функцией, которая принимает ваши данные при вводе и возвращает идентификатор с разделителями (например, целое число от 0 до HASH_MAX)

Затем вы должны поместить свой элемент в список в индексе Hash(data) массива hash_table. если данные имеют тот же хэш, они будут храниться в том же списке, что и предыдущие данные.

struct your_type_list {
  yourtype data;
  yourtype *next_data;
};

struct your_type_list hash_table[HASH_MAX];