时间戳

首页 > 解决方案 > C中以void指针为值的Hashmap实现问题

c - C中以void指针为值的Hashmap实现问题

问题描述

嗨，我正在尝试在常规 C 中实现一个非常简单的哈希映射，其中一个字符串作为键，一个 void 指针作为值，因为我希望将映射用于多种数据类型。

到目前为止我有这个

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 方面不是最伟大的，所以任何可以阐明这一点的光都将不胜感激。

标签： cpointershashmapvoid-pointers

解决方案

问题是每次调用时都使用相同的指针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()andnode_create()参数。然后node_create调用malloc()andmemcpy()将值复制到动态内存。

BTW，还有一个问题。键应该是一个以 null 结尾的字符串（strhash()取决于此），但您正在使用&i，它是一个指向整数的指针。将指向整数的指针转换为char*不返回字符串，它只是返回指向具有不同数据类型的相同位置的指针。我没有在上面解决这个问题。

推荐阅读