链表实现哈希表插入时所有节点值被覆盖的问题求助

问题重现 #

基于链表实现的哈希表，在插入多个节点后，所有已插入节点的值会被最近插入的节点覆盖。例如插入"b"(4)、"a"(1)、"c"(2)后，查询"b"的weight返回2而非4。相关代码如下：

数据结构定义 #

//linked list node  
struct node{
    char* symbol;
    int weight;
    struct node* succ;
};
typedef struct node node;

//linked list 
struct linkedList{
    node* head;
};
typedef struct linkedList linkedList;

//hashtable  
struct hashTable{
    linkedList* cells;
    int capacity;
};
typedef struct hashTable hashTable;

插入函数实现 #

//linked list insertion
void insertion_linkedList(linkedList* l, node n){
    node** p = &l->head; 
    if (*p == NULL){
        *p = &n;
    }
    else{
        while ((*p)->succ != NULL){
            *p = (*p)->succ;
        }
    }
    (*p)->succ = &n;
    return;
}

//hashtable insertion 
void insertion_hashTable(hashTable h, char* s, int n){
    node ins = {.symbol = s, .weight = n, .succ = NULL};
    insertion_linkedList(&h.cells[hashFunction(s, h.capacity)], ins);
}

测试代码 #

int main(){
    int cap = 100;
    hashTable h = creation_hashTable(cap);

    insertion_hashTable(h,"b",4);
    insertion_hashTable(h,"a",1);
    insertion_hashTable(h, "c", 2);

    printf("%i\n", h.cells[hashFunction("b",h.capacity)].head->weight);
    // 返回2而非预期的4

    exit(0);
}

核心原因分析 #

1. 栈局部变量地址复用：insertion_hashTable中定义的node ins是栈上的局部变量，函数执行完毕后该内存空间会被回收。每次调用insertion_hashTable时，ins都会分配在栈上的同一位置，导致所有链表节点的指针都指向这块重复使用的内存区域。后续插入操作会覆盖该区域的数据，最终所有节点都显示最后一次插入的值。

2. 链表插入逻辑错误：

   • 当链表为空时，代码先将头指针指向&n，随后又执行(*p)->succ = &n，导致头节点的succ指向自身，形成循环链表。
   • 无论链表是否为空，最终都强制将当前节点的succ指向&n，破坏原有链表结构的同时，重复绑定到同一个局部变量地址。

3. 哈希表参数值传递问题：insertion_hashTable的参数是hashTable h（值传递），函数内对h的修改只会作用于副本，不会影响原哈希表。这是潜在问题，虽不是当前值覆盖的直接诱因，但必须修复。

修复方案 #

1. 动态分配节点内存 #

使用malloc在堆上为每个节点分配内存，避免栈内存的复用和回收问题。

2. 修正链表插入逻辑 #

确保新节点正确添加到链表末尾，避免循环引用。

3. 哈希表参数改为指针传递 #

确保函数内的修改能作用于原哈希表。

修复后的代码 #

// 链表插入：接收动态分配的节点指针
void insertion_linkedList(linkedList* l, node* new_node){
    node** p = &l->head; 
    // 找到链表末尾的空指针位置
    while (*p != NULL){
        p = &(*p)->succ;
    }
    *p = new_node;
    new_node->succ = NULL; // 确保新节点的后继为空
}

// 哈希表插入：传哈希表指针，动态分配节点
void insertion_hashTable(hashTable* h, char* s, int n){
    // 动态分配节点内存
    node* ins = (node*)malloc(sizeof(node));
    if (ins == NULL){
        // 内存分配失败处理
        perror("malloc failed");
        return;
    }
    ins->symbol = s;
    ins->weight = n;
    ins->succ = NULL;

    int idx = hashFunction(s, h->capacity);
    insertion_linkedList(&h->cells[idx], ins);
}

测试代码修正 #

int main(){
    int cap = 100;
    hashTable h = creation_hashTable(cap);

    // 传哈希表指针
    insertion_hashTable(&h,"b",4);
    insertion_hashTable(&h,"a",1);
    insertion_hashTable(&h, "c", 2);

    int idx = hashFunction("b", h.capacity);
    printf("%i\n", h.cells[idx].head->weight);
    // 现在返回预期的4

    // 注意：需要添加内存释放逻辑，避免内存泄漏
    // 此处省略释放代码，需遍历哈希表每个链表，逐个free节点

    exit(0);
}

额外注意事项 #

• 务必为动态分配的节点添加内存释放逻辑，避免内存泄漏。
• hashFunction需保证返回值在[0, capacity-1]范围内，避免数组越界访问。
• 如果symbol是动态分配的字符串，插入时需考虑深拷贝，避免原字符串被修改影响哈希表数据。

内容的提问来源于stack exchange，提问作者M K