c语言 - 这个迷你哈希图有什么问题？

Question

我正在尝试实现一个简单的HashMap，只有newget和insert功能。 有一个非常简单的测试函数，目前没有通过。

输出：

test: Assertion `el == -10' failed.

调试测试时，我得到：

key: hhh value: 300
key: aba value: 300

当它淅行时：

key: hhh value: 10
key: aba value: -10

代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define N (1000)
#define MULTIPLIER (37)
typedef struct Node {
char* key;
int value;
struct Node* next;
} Node;
typedef struct HashMap {
Node* data[N];
} HashMap;
void test();
unsigned long hash(const char* key);
HashMap* new_hash_map();
void insert_element(char* key, int value, HashMap* hm);
int get_element(char* key, HashMap* hm, int* el);
unsigned long hash (const char* s)
{
unsigned long h;
unsigned const char* us;
us = (unsigned const char*) s;
h = 0;
while (*us != ''){
h = h * MULTIPLIER + *us;
us++;
}
return h % N;
}
HashMap* new_hash_map()
{
HashMap* hm = malloc(sizeof(HashMap));
for (int i = 0; i < N; i++){
hm->data[i] = NULL;
}
return hm;
}
void insert_element(char* key, int value, HashMap* hm)
{
unsigned long hk = hash(key);
Node* ll = hm->data[hk];
if (ll == NULL) {
ll = malloc(sizeof(Node));
ll->key = key;
ll->value = value;
ll->next = NULL;
return;
}
for (; ll != NULL; ll = ll->next){
if (strcmp(ll->key, key) == 0){
// already exists
ll->value = value;
return;
}
}
// new element, same hash key
ll->key = key;
ll->value = value;
ll->next = NULL;
}
int get_element(char* key, HashMap* hm, int* el)
{
unsigned long hk = hash(key);
Node* ll = hm->data[hk];
if (ll == NULL) {
return -1;
}
for (; ll != NULL; ll = ll->next){
if (strcmp(ll->key, key) == 0){
// already exists
*el = ll->value;
return 1;
}
}
return -1;
}
void test()
{
HashMap* hm = new_hash_map();
int el;
insert_element("aba", 10, hm);
insert_element("hhhh", -10, hm);
get_element("hhhh", hm, &el);
assert(el == -10);
get_element("aba", hm, &el);
assert(el == 10);
}
int main () {
test();
return 0;
}

Answer 1

好吧，主要问题是你从来没有插入任何东西，你准备好了，分配然后分配给适当的成员，然后你只是从函数中返回。

将分配的内存分配给hashmap的data。(hm->data[hk] = ll)。还要检查malloc的返回值。

此外，第二个循环在这方面具有很大的误导性 - 您最终会在ll中得到NULL，然后取消引用它。你应该分配并做与以前相同的事情。

for (; ll != NULL; ll = ll->next){
if (strcmp(ll->key, key) == 0){
// already exists
ll->value = value;
return;
}
}
// if the ll is NULL (in case it doesn't match) 
// the you wil dereference NULL leading to UB.
// new element, same hash key
ll->key = key;
ll->value = value;
ll->next = NULL;

取消引用NULL值是未定义的行为。这里可能的解决方案是为这个新节点分配内存，然后将其分配给哈希映射中的插槽。

从标准 6.5.3.2p4

一元 * 运算符表示间接寻址。如果操作数指向 函数，结果是一个函数指示符;如果它指向 对象，结果是指定对象的左值。如果操作数 具有类型"指向类型的指针"，结果具有类型"类型"。如果 已将无效值分配给指针，该指针的行为 一元 * 运算符未定义。

在脚注上

在

用于取消引用指针的无效值中，一元*运算符为空指针，地址未正确对齐 指向的对象类型，以及 其生命周期结束。