Реализация вставки хеш-таблицы с использованием строкового ключа

Question

У меня есть проблема, которую я пытаюсь решить уже несколько дней.Я пытаюсь создать Hashtable из трех структур, первый из которых содержит наборы указателей на массив пар с ключом и парой значений.Ключ должен быть строкой (char * arr).Я не совсем понимаю, как создать для него работающую функцию вставки, и то, что я собираюсь сделать в своем коде, - это попытаться увидеть, есть ли в корзине h ключ или нет.Я чувствую, что что-то не так с моей логикой и синтаксисом.Если бы кто-то мог помочь мне в этом, это было бы очень признательно.

Я посмотрел теорию хэш-таблиц в Википедии и видео на YouTube, но никто из них не использует три структуры и строковые ключи.вот где я застреваю, я чувствую.

#include<stdio.h>
#include"hashtable.h"

struct hash_table
{
    Bucket *bucket;
    int hash_size;
};

struct bucket
{
    Pair *list;
    int capacity;
    int size;
};

struct pair
{
    char *key;
    int value;
};

Pair copy_key(char *key, int value)
{
    Pair copy = malloc(sizeof(Pair));
    copy->key = key;
    copy->value = value;
    return copy;
}

unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)          
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

void hash_insert (HashTable *tab, const char *key, int value)
{
    unsigned long h = hash(key) % tab->hash_size;
    int i = 0;

    while(tab->bucket[h]->list[i]->key != NULL && (i < tab->bucket->size))
    {
        Pair pair = copy_key(key,value);
        if (tab->bucket[h]->list[i]->key == pair->key)
        {
            tab->bucket[h]->list[i]->value == pair->value;
            return;
        }
    }
}

Работающая функция вставки для хэш-таблицы с тремя структурами со строковыми ключами.

Answer 1

В вашей функции вставки довольно много проблем:

void hash_insert (HashTable *tab, const char *key, int value)
{
    unsigned long h = hash(key) % tab->hash_size;
    int i = 0;

    // depending on how you initialise your hash table, the list might yet
    // be NULL(!) - so you possibly yet need a check for!

    // you need FIRST to check if the index is yet valid, THEN check
    // if there is a key!
    //while(tab->bucket[h]->list[i]->key != NULL && (i < tab->bucket->size))
    while(i < tab->bucket[h].size && tab->bucket[h].list[i].key != NULL)
    // additionally: you have a pointer, index operator [] dereferences
    // -> you have a struct directly -> need to access via .
    {
        //Pair pair = copy_key(key,value);
        // BAD idea: you malloc a struct, but never free it -> memory leak!

        if (tab->bucket[h].list[i].key == /*pair->*/key)
        // compare directly!

        // however: == compares the pointers only - most likely, though,
        // you have created a new string somewhere else just with same
        // CONTENT - in this case you need to compare via strcmp:
        if (strcmp(tab->bucket[h].list[i].key, key) == 0)

        {
            //tab->bucket[h]->list[i]->value == pair->value;
            // comparison? assuming you wanted to assign:
            tab->bucket[h].list[i].value = value;

            return;
        }
    }

    // end of while reached, the key was not yet found!
    // -> you need to insert it here:

    if(i == tab->bucket[h].size)
    {
        // no space in buckets left!
        // -> need to realloc (leaving this to you)

        // BUT: you might want to consider overall fill grade or maximum fill
        // grade for buckets and do a complete re-hash of all contents...
    }

    // assuming we insert in THIS bucket:
    tab->bucket[h].list[i].key = ???;
    tab->bucket[h].list[i].value = value;
}

??? - ну, зависит.Я в значительной степени предполагаю, что вы хотите, чтобы хэш-карта имела ключевые строки, которые она содержит.Тогда вы защищены от того, что ключ - это локальный массив, выходящий из области видимости, или динамически размещаемая строка, которая впоследствии удаляется!Итак:

tab->bucket[h].list[i].key = strdup(key);

Если вы хотите избежать ненужных копий, поскольку вы уже выделили строку, вы можете добавить еще один параметр: int isTakeOwnwership (или bool, но вам нужно #include <stdbool.h> для):

tab->bucket[h].list[i].key = isTakeOwnership ? key : strdup(key);

В обоих примерах я не проверял, что результат strdup равен NULL - вам нужно сделать это и обработать случай, когда выделение памяти завершилось неудачно (возможно, добавьте возвращаемое значение в функцию вставки, указывающее на успех илиошибка?).

Не забудьте free строки на карте при удалении элемента !!!Помните, что ваша карта стала владельцем.