Проблема реализации Hashmap в C с пустым указателем в качестве значения

Question

Здравствуйте, я пытаюсь реализовать действительно простой хэш-файл в обычном C со строкой в ​​качестве ключа и пустым указателем в качестве значения, так как я хочу использовать карту для нескольких типов данных.

Пока у меня есть это

struct node{
    void * value;
    char * key;
};

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

    while ((c = *string++))
    {   
        hash = ((hash << 5) + hash) + c;
    }   
    return hash;
}


map_t *map_create(int maxSize){

    map_t *map = malloc(sizeof(map_t));
    map->curSize = 0;
    map->maxSize = maxSize;
    map->nodes = calloc(map->maxSize, sizeof(node_t *));

    return map;
}


node_t *node_create(char *key, void *value){

    node_t *node = malloc(sizeof(node_t));
    node->key = key;
    node->value = value;
    return node;
}

void map_insert(map_t *map, char *key, void *value){

    node_t *node = node_create(key, value);

    int idx = strhash(key) % map->maxSize;
    if(map->nodes[idx] == NULL){
        map->nodes[idx] = node;
    }else{
        while(map->nodes[idx] != NULL){
            idx++%map->maxSize;
        }
        map->nodes[idx] = node;
    }   
    return;
}

void map_print(map_t *map){

    for(int i = 0; i < map->maxSize; i++){
        if(map->nodes[i] != NULL){
            printf("index: %d\t value: %d\n",i, *(int*)map->nodes[i]->value);
        }
    }
    return;
}

void map_destroy(map_t *map){
     for(int i = 0; i < map->maxSize; i++){
        if(map->nodes[i] != NULL){
            free(map->nodes[i]);
        }
    }
    free(map->nodes);
    free(map);
    return;
}



int main(){

    map_t *map = map_create(32);
    for(int i = 0; i < 30; i++){
        map_insert(map, (char*)&i, &i);
    }
    map_print(map);
    map_destroy(map);
    return 0;
}

Проблема в том, что вывод не такой, как я ожидаю, когда карта будет напечатана, все, что получено, это значение «30» по всем индексам, которое является последним числом, вставленным в карту. Если я изменю значение на тип int, карта будет работать, как и ожидалось, поэтому должно быть что-то важное, чего мне не хватает в отношении указателей.

Я не самый лучший в C, поэтому любой свет, который можно было бы пролить на это, был бы очень признателен.

Answer 1

Проблема в том, что вы используете один и тот же указатель каждый раз, когда звоните map_insert(). Он просто хранит указатель, но не копирует данные. Каждый раз в цикле вы меняете содержимое этой памяти, поэтому все элементы карты хеша указывают на одно и то же значение.

Есть два способа исправить это. Один из способов - всегда делать динамически распределяемую копию данных перед вызовом map_insert():

for (int i = 0; i < 30; i++) {
    int *i_copy = malloc(sizeof *i_copy);
    *i_copy = i;
    map_insert(map, (char *)i_copy, (char *)i_copy);
}

Другой вариант - добавить размер значения к аргументам map_insert() и node_create(). Затем node_create вызовите malloc() и memcpy(), чтобы скопировать значение в динамическую память.

Кстати, есть еще одна проблема. Ключ должен быть строкой с нулевым символом в конце (strhash() зависит от этого), но вы используете &i, который является указателем на целое число. Приведение указателя на целое число к char* не возвращает строку, оно просто возвращает указатель на то же местоположение с другим типом данных. Я не исправил это выше.

Answer 2

OP хранит ссылку на одно и то же значение, поэтому, конечно, все поиски выдают одно и то же значение (которое даже не является строкой, но каким бы ни было представлением в хранилище значения переменной i).

Я предпочитаю создавать цепочки записей хеш-карты и сохранять копию хеш-функции в записи:

struct entry {
    struct entry *next;
    size_t        hash;
    void         *data;
    size_t        data_size;
    int           data_type;
    unsigned char name[];
};

typedef struct {
    size_t         size;
    size_t         used;  /* Number of entries, total */
    struct entry **slot;  /* Array of entry pointers */
    size_t       (*hash)(const unsigned char *, size_t);
} hashmap;

int hashmap_new(hashmap *hmap, const size_t size,
                size_t (*hash)(const unsigned char *, size_t))
{
    if (!hmap)
        return -1; /* No hashmap specified */

    hmap->size = 0;
    hmap->used = 0;
    hmap->slot = NULL;
    hmap->hash = NULL;

    if (size < 1)
        return -1; /* Invalid size */
    if (!hash)
        return -1; /* No hash function specified. */

    hmap->slot = calloc(size, sizeof hmap->slot[0]);
    if (!hmap->slot)
        return -1; /* Not enough memory */

    hmap->size = size;
    hmap->hash = hash;

    return 0;
}

void hashmap_free(hashmap *hmap)
{
    if (hmap) {
        size_t  i = hmap->size;
        while (i-->0) {
            struct entry *next = hmap->slot[i];
            struct entry *curr;

            while (next) {
                curr = next;
                next = next->next;

                free(curr->data);

                /* Poison the entry, to help detect use-after-free bugs. */
                curr->next = NULL;
                curr->data = NULL;
                curr->hash = 0;
                curr->data_size = 0;
                curr->data_type = 0;
                curr->name[0] = '\0';

                free(curr);
            }
        }
    }

    free(hmap->slot);
    hmap->size = 0;
    hmap->used = 0;
    hmap->slot = NULL;
    hmap->hash = NULL;
}

Чтобы вставить пару ключ-значение, функция либо использует данные, указанные как есть, и в этом случае вызывающая сторона несет ответственность за обеспечение того, чтобы каждый ключ имел свои уникальные данные, не перезаписанные позже; или мы копируем данные пользователя. В приведенной выше функции hashmap_free() вы увидите free(curr->data);; он предполагает, что мы распределили память динамически и скопировали туда данные пользователя. Итак:

int hashmap_add(hashmap *hmap, const unsigned char *name,
                const void *data, const size_t data_size,
                const int data_type)
{
    const size_t  namelen = (name) ? strlen(name) : 0;
    struct entry *curr;
    size_t        i;

    if (!hmap)
        return -1; /* No hashmap specified. */

    if (name_len < 1)
        return -1; /* NULL or empty name. */

    /* Allocate memory for the hashmap entry,
       including enough room for the name, and end of string '\0'. */
    curr = malloc(sizeof (struct entry) + namelen + 1;
    if (!curr)
        return -1; /* Out of memory. */

    /* Copy data, if any. */
    if (data_size > 0) {
        curr->data = malloc(data_size);
        if (!curr->data) {
            free(curr);
            return -1; /* Out of memory. */
        }
        memcpy(curr->data, data, data_size);
    } else {
        curr->data      = NULL;
        curr->data_size = 0;
    }

    curr->data_type = data_type;

    /* Calculate the hash of the name. */
    curr->hash = hmap->hash(name, namelen);

    /* Copy name, including the trailing '\0'. */
    memcpy(curr->name, name, namelen + 1);

    /* Slot to prepend to. */
    i = curr->hash % hmap->size;

    curr->next = hmap->slot[i];
    hmap->slot[i] = curr;

    /* An additional node added. */
    hmap->used++;

    return 0;
}

Значение data_type полностью зависит от пользователя кода. Поиск может быть сделан на основе хеша и типа данных:

/* Returns 0 if found. */
int hashmap_find(hashmap *hmap, const unsigned char *name,
                 const int data_type,
                 void **dataptr_to, size_t *size_to)
{
    struct entry  *curr;
    size_t         hash;

    if (size_to)
        *size_to = 0;
    if (dataptr_to)
        *dataptr_to = NULL;

    if (!hmap)
        return -1; /* No hashmap specified. */
    if (!name || !*name)
        return -1; /* NULL or empty name. */

    hash = hmap->hash(name, strlen(name));
    curr = hmap->slot[hash % hmap->size];

    for (curr = hmap->slot[hash % hmap->size]; curr != NULL; curr = curr->next) {
        if (curr->data_type == data_type && curr->hash == hash &&
            !strcmp(curr->name, name)) {
            /* Data type an name matches. Save size if requested. */
            if (size_to)
                *size_to = curr->data_size;
            if (dataptr_to)
                *dataptr_to = curr->data;
            return 0; /* Found. */
        }
    }

    return -1; /* Not found. */
}

Приведенный выше поиск возвращает 0, если найдено, и ненулевое значение, если ошибка или не найдена. (Таким образом, даже нулевые данные NULL могут быть сохранены в хэш-карте.)

Если число поддерживаемых типов данных невелико, скажем, 32, то с помощью unsigned int с каждым битом (1U<<0 == 1, 1U<<1 == 2, 1U<<2 == 4 и т. Д.), Зарезервированным для определенного типа, вы можете выполнить поиск, используя маску, разрешающую только указанные типы. Точно так же data_type может быть маской, описывающей, к каким типам может быть интерпретировано значение (почти всегда будет установлен только один бит).

Эта схема также позволяет динамически изменять размер хэш-карты, выделяя новый массив slot указателей и перемещая каждую старую запись в новую. Ключи не нужно перефразировать, потому что оригинальный хеш хранится в каждой записи. Для эффективности поиска цепи (свисающие с каждой щели) должны быть как можно короче. Общее "правило большого пальца" состоит в том, что hashmap->size должно быть между hashmap->used и 2 * hashmap->used.

Answer 3

Когда вы вызываете map_insert(map, (char*)&i, &i);, значение, вставленное в hasmap, является указателем на переменную i, то есть его адрес в памяти, а не значением i. Поэтому при изменении значения i внутри цикла for возникает побочный эффект для всех записей в хэш-карте, и в конце цикла вы видите только последнее назначенное значение.