嗨,我正试图在常规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不是最伟大的,所以任何能在这方面有所帮助的人都会非常感激。

最佳答案

问题是每次调用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_createmalloc()将值复制到动态内存。
顺便说一下,还有一个问题。键应该是以空结尾的字符串(memcpy()取决于此),但您使用的是指向整数的指针strhash()。将一个指向&i的整数的指针强制转换不返回字符串,它只返回一个指向具有不同数据类型的同一位置的指针。我还没把这个修好。

关于c - 以void指针为值的C中的Hashmap实现问题,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/53217476/

10-11 22:21
查看更多