实现哈希表解决LeetCode217时遇'misaligned address'错误求助

问题背景 #

刚学习哈希表概念，手动实现哈希表来解决LeetCode 217. 存在重复元素问题（判断数组是否存在重复元素），运行代码时出现内存对齐错误，请求排查原因。

代码实现 #

typedef struct node{
    int n;
    struct node *next;
}
node;

int hash(int i) {
    return abs((i*2654435761)%1024);
}

void unloadBucket(node *at) {
    if(at->next != NULL) {
        unloadBucket(at->next);
    }
    free(at);
}

bool containsDuplicate(int* nums, int numsSize){
    node *table[1024];

    // Load buckets of hash table
    for(int i = 0; i < 1024; i++) {
        table[i] = malloc(sizeof(node));
        table[i]->n = 0;
        table[i]->next = NULL;
    }

    for(int i = 0; i < numsSize; i++) {
        int key = hash(nums[i]);
        node *at = table[key];

        while(at->next != NULL) {
            if(at->n == nums[i])
                return true;
            else
                at = at->next;
        }

        at->n = nums[i];
        at->next = malloc(sizeof(node));
    }

    // Unload buckets
    for(int i = 0; i < 1024; i++) {
        unloadBucket(table[i]);
    }
    return false;
}

错误信息 #

Line 12: Char 10: runtime error: member access within misaligned address 0xbebebebebebebebe for type 'struct node', which requires 8 byte alignment [solution.c]
0xbebebebebebebebe: note: pointer points here
<memory cannot be printed>

错误原因分析 #

出现0xbebebebebebebebe地址访问错误，说明代码访问了已被释放或未初始化的野指针，具体问题如下：

1. 新节点未初始化next指针
   在插入元素的循环中，每次执行at->next = malloc(sizeof(node));后，没有为新分配的节点初始化next成员。这会导致新节点的next是随机的垃圾值，后续遍历链表或释放内存时，会访问到非法地址。

2. 内存释放函数的递归逻辑缺陷
   unloadBucket函数中，先检查at->next != NULL再递归，但未处理at本身为NULL的情况。当递归到带有野指针的节点时，访问at->next会触发非法内存访问，进而触发内存对齐错误。

3. 哈希函数的潜在溢出问题
   当输入i为INT_MIN时，abs(i)会产生整数溢出（C语言中属于未定义行为），虽然这不是当前错误的直接原因，但会导致哈希值计算错误。

修复方案 #

1. 初始化新分配的节点 #

在插入元素时，为新分配的节点初始化next指针为NULL：

at->next = malloc(sizeof(node));
if (at->next != NULL) { // 增加malloc失败判断，避免空指针
    at->next->next = NULL;
    at->next->n = 0; // 可选，初始化数据域
}

2. 修正内存释放函数的递归逻辑 #

修改unloadBucket，先判断当前节点是否为NULL，避免访问空指针：

void unloadBucket(node *at) {
    if (at == NULL) {
        return;
    }
    unloadBucket(at->next);
    free(at);
}

3. 优化哈希函数避免溢出 #

针对INT_MIN的情况，调整哈希函数的实现：

int hash(int i) {
    // 用无符号整数处理避免溢出
    unsigned int ui = (unsigned int)i;
    return (ui * 2654435761u) % 1024;
}

4. 优化链表插入逻辑（可选） #

原代码中头节点存储数据的设计容易引发误判（比如初始值0与输入元素0的冲突），可以改为头节点作为哨兵（不存储数据），或者直接将桶初始化为NULL：

// 初始化桶为NULL
for(int i = 0; i < 1024; i++) {
    table[i] = NULL;
}

// 插入元素时的逻辑调整
for(int i = 0; i < numsSize; i++) {
    int key = hash(nums[i]);
    node *at = table[key];
    // 遍历整个链表检查重复
    while(at != NULL) {
        if(at->n == nums[i])
            return true;
        at = at->next;
    }
    // 新建节点并插入链表头部
    node *new_node = malloc(sizeof(node));
    new_node->n = nums[i];
    new_node->next = table[key];
    table[key] = new_node;
}

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