C语言哈希表实现中的内存分配与数据获取异常问题

核心问题排查 #

1. 哈希表插入未完成赋值操作 #

这是导致table_get始终返回NULL和内存泄漏的根本原因：在table_insert函数中，创建entry后，没有将其赋值给table->entries[index]。代码只执行了entry = entry_init(misspelling, correct_word);，但从未把这个entry存入哈希表的数组中，导致哈希表的entries数组对应位置始终为NULL，后续查询找不到数据，销毁时也无法释放这些孤立的entry内存。

修复代码：

if (!entry) {
    entry = entry_init(misspelling, correct_word);
    table->entries[index] = entry; // 新增这行，将entry存入哈希表
    table->used_entries++;
    return index;
}

2. 字符串内存管理不匹配 #

• entry_init直接存储传入的字符串指针（来自strtok的返回值，指向getline分配的缓冲区），但entry_delete却尝试free这些指针。strtok返回的指针并非malloc分配，直接free会触发未定义行为，同时也会导致原缓冲区被free后出现野指针。
• 正确做法是在entry_init中复制字符串，存储堆上的副本：

修复后的entry_init和entry_delete：

static entry_t *
entry_init(const char *const misspelling, const char *const correct_word)
{
    entry_t *entry = malloc(sizeof(entry_t));
    if (!entry) return NULL; // 新增malloc失败检查
    entry->misspelling = strdup(misspelling);
    entry->correct_word = strdup(correct_word);
    // 可添加strdup失败的回滚逻辑
    return entry;
}

static void
entry_delete(entry_t *entry)
{
    free((void*)entry->misspelling); // 强制转换去掉const，适配strdup的可释放指针
    free((void*)entry->correct_word);
    free(entry);
}

3. get_prime函数逻辑错误 #

当前函数生成的是偶数而非质数：while (number % 2 != 0) { number++; }意味着最终返回的number一定是偶数，不可能是质数，这会破坏哈希函数的分布性。

修复示例（简单质数生成逻辑）：

#include <stdbool.h>

static bool is_prime(size_t n) {
    if (n <= 1) return false;
    if (n <=3) return true;
    if (n%2 ==0 || n%3 ==0) return false;
    for (size_t i=5; i*i <=n; i+=6) {
        if (n%i ==0 || n%(i+2)==0) return false;
    }
    return true;
}

size_t
get_prime(void)
{
    static bool seeded = false;
    if (!seeded) {
        srand((unsigned int)time(NULL));
        seeded = true;
    }
    size_t number;
    do {
        number = (unsigned int)rand();
        if (number <2) number =2;
    } while (!is_prime(number));
    return number;
}

注：随机种子只需初始化一次，避免每次调用get_prime都重置。

4. 哈希表entries数组未初始化 #

table_init中malloc的entries数组是未初始化的，内存中是随机垃圾值，不是NULL。插入时会误判某些位置已被占用，导致插入失败或位置错误。

修复：用calloc代替malloc，或者手动初始化数组为NULL：

table_t *
table_init(const size_t size)
{
    table_t *table = malloc(sizeof(table_t));
    if (!table) return NULL;
    // 用calloc直接初始化所有元素为NULL
    table->entries = calloc(size, sizeof(entry_t *));
    if (!table->entries) { free(table); return NULL; }
    table->seed = get_prime();
    table->size = size;
    table->used_entries = 0U;
    return table;
}

其他优化建议 #

• 错误处理：所有malloc/calloc/strdup/fopen都要检查返回值，避免空指针解引用。
• 哈希函数优化：当前的线性探测公式position = position + it * (position * 2 + 1)易导致聚类问题，可改用标准线性探测position = (hash + it) % table_size，或二次探测减少聚类。
• 负载因子控制：当used_entries / size超过0.7左右的阈值时，触发哈希表扩容，避免过多探测操作。
• 文件读取健壮性：strtok会修改原字符串，若行格式不符合->分隔，correct_word会为NULL，插入时需判断两个指针是否有效。
• const修饰合理性：entry_t中的字符串指针若存储堆上副本，可去掉const，或在entry_delete中用强制转换适配。

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