嗨,我正试图在常规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_create
和malloc()
将值复制到动态内存。顺便说一下,还有一个问题。键应该是以空结尾的字符串(
memcpy()
取决于此),但您使用的是指向整数的指针strhash()
。将一个指向&i
的整数的指针强制转换不返回字符串,它只返回一个指向具有不同数据类型的同一位置的指针。我还没把这个修好。关于c - 以void指针为值的C中的Hashmap实现问题,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/53217476/