哈希表插入异常：取模哈希函数下数据被覆盖问题排查

问题概述 #

我实现了一个哈希表，要求用i % n作为哈希函数（i为键，n为表项数，由命令行传入），但insert函数存在问题：插入多组键值对时新数据会覆盖旧数据，最终仅留存一项。测试用例预期输出3个不同键值对，但实际只显示一个，需要排查问题原因。

相关代码 #

结构体定义 #

//Hash table entry structure
typedef struct entry_s {
    int key;
    int value;
    struct entry *next;
}entry_t;

//Hash table structure
typedef struct hash_table_s
{
    entry_t **entries;
    int size;
    int locks;
}hash_table_t;

核心函数 #

//Hash function
int hash(int i, int n){
    return i % n;
}

//New table entry
entry_t *new_entry(int key, int value){
    entry_t *entry = (entry_t *) malloc(sizeof(entry_t));
    entry->key = key;
    entry->value = value;
    entry->next = NULL;
    return entry;
}

//Create new hash table
hash_table_t *new_table(int n, int k){
    hash_table_t *table = (hash_table_t *) malloc(sizeof(hash_table_t));
    table->entries = (entry_t **) calloc(n, sizeof(entry_t *));
    table->size = n;
    table->locks = k;
    return table;
}

//Insert key value pair into hash table
void insert(hash_table_t *table, int key, int value){
    printf("table size %d\n", table->size);
    printf("key %d\n", key);
    int index = hash(key, table->size);
    printf("hash %d\n", index);
    entry_t *entry = table->entries[index];
    if (entry == NULL)
    {
        table->entries[index] = new_entry(key, value);
        table->size++;
        printf("null table\n");
    }
    else {
        while (1){
            //Update value for multiples
            if (entry->value == value){
                entry->key += key;
                printf("1\n");
                break;
            }
            //End of chain, add new entry
            else if (entry->next == NULL){
                //entry->next = (new_entry(key, value))->next;
                table->entries[index] = new_entry(key, value);
                printf("2\n");
                break;
            }
            //traverse the chain
            else{
                printf("3\n");
                //entry = entry->next;
            }
        }
    }
    //unlock???
}

主函数 #

int main(int argc, char *argv[])
{
    printf("\n");

    int n = atoi(argv[1]);
    int k = atoi(argv[2]);

    hash_table_t *pt = new_table(n,k);

    insert(pt, 1, 111);
    insert(pt, 1, 111);
    insert(pt, 1, 222);
    insert(pt, 1, 333);

    print_table(pt);

    free_memory(pt);

    return 0;
}

执行信息 #

执行命令 #

dpb@ThinkPad:~/Documents/CSE_420/P3$ ./par_hash_table 10 2

执行输出 #

table size 10
key 1
hash 1
null table
table size 11
key 1
hash 1
1
table size 11
key 1
hash 1
2
table size 11
key 1
hash 1
2

Hash Table
-------------------
Index:1, Key:1, Value:333
-------------------

问题排查与修复方向 #

1. 哈希计算逻辑错误 #

当前insert函数使用table->size计算哈希值，但table->size在插入第一个元素后被table->size++修改了——这里混淆了哈希桶的数量和哈希表中元素的数量。初始化时table->size被设为命令行传入的表项数（哈希桶数量），但插入元素后递增它，导致后续哈希计算的基数错误，同时也破坏了哈希函数的预期规则。

修复：

• 重新命名哈希表结构体的成员：将size改为bucket_count（表示哈希桶数量，初始化后不再修改），新增element_count用于记录元素总数（如果需要统计）。
• 哈希计算时使用table->bucket_count代替table->size。

2. 链表插入逻辑错误 #

在处理链表末尾的分支中，代码执行table->entries[index] = new_entry(key, value);，这直接覆盖了当前哈希桶的链表头节点，导致之前存在的整个链表被丢弃，只剩新插入的节点，这是数据丢失的核心原因。

修复：

• 改为将新节点挂到当前节点的next指针上：entry->next = new_entry(key, value);

3. 链表遍历逻辑停滞 #

在遍历链表的分支中，entry = entry->next;被注释掉了，导致循环永远停留在链表的第一个节点，无法遍历后续节点，后续的插入或判断逻辑都会失效。

修复：

• 取消entry = entry->next;的注释，让循环能够遍历整个链表。

4. 键值对匹配逻辑不符合需求 #

当前代码判断entry->value == value时累加key，这与“插入不同键值对”的需求不符——测试用例中key相同但value不同，应该判断key是否重复（比如key重复时更新value，否则插入新节点），而不是根据value判断。

修复：

• 将判断条件改为entry->key == key，如果匹配则更新value（或根据需求处理），否则继续遍历。

内容的提问来源于stack exchange，提问作者Devin Bowen