哈希表（分离链接解决冲突）删除后Get函数无限循环问题

嘿，我帮你捋捋这个分离链接哈希表的问题——删除特定图像后调用get()会触发无限循环，旧ID还没被清除，这大概率是删除操作的指针处理不到位，或者get()函数的循环逻辑有漏洞，咱们一步步拆解排查：

1. 删除节点时的指针遗漏 #

分离链接法最容易踩的坑就是删除节点时没处理好链表的链接关系：

• 如果删除的是链表头节点，但没更新hashtable[i]的指向，那hashtable[i]会一直指向已删除的节点（野指针），后续get()拿到这个野指针后，遍历链表时就会因为野指针的next指向混乱，要么读到旧ID，要么进入无限循环。
• 如果删除的是中间/尾节点，但没更新前驱节点的next指针，会导致链表出现断链或者残留无效节点，遍历的时候也可能卡死。

2. get()函数的循环逻辑错误 #

如果你的get()函数循环条件写得有问题，比如：

• 用了while(temp->next)而不是while(temp != NULL)，会漏检头节点，或者在链表末尾继续访问野指针；
• 找到匹配节点后没及时break，或者循环里的指针更新出错，也可能导致无限循环。

3. 野指针与未释放内存 #

删除节点后如果没正确free内存，或者释放后还有其他指针指向这块内存，就会出现野指针，此时读取旧ID或者触发循环都是不可控的。

假设你的代码基础结构，给出修正后的关键片段：

正确的get()函数实现 #

int get(image img) {
    int i = hashCode(img);
    Node* temp = hashtable[i];
    
    // 遍历链表，直到找到匹配或到链表末尾
    while(temp != NULL) {
        // 假设你有一个图像比较函数，判断两个image是否一致
        if(isSameImage(temp->img, img)) { 
            return temp->id; // 找到就返回ID，及时退出循环
        }
        temp = temp->next; // 指针正常向后移动
    }
    return -1; // 没找到返回无效标识
}

正确的删除函数实现 #

要覆盖头节点、中间节点、尾节点三种场景：

void delete(image img) {
    int i = hashCode(img);
    Node* curr = hashtable[i];
    Node* prev = NULL;

    // 先找到要删除的节点
    while(curr != NULL && !isSameImage(curr->img, img)) {
        prev = curr;
        curr = curr->next;
    }

    if(curr == NULL) {
        return; // 没找到要删除的节点，直接退出
    }

    // 处理链表链接更新
    if(prev == NULL) {
        // 删除的是头节点，必须更新哈希表的指针
        hashtable[i] = curr->next;
    } else {
        // 让前驱节点跳过当前要删除的节点
        prev->next = curr->next;
    }

    // 释放节点内存，避免野指针
    free(curr);
}

• 一定要更新哈希表头指针：删除头节点时，hashtable[i]必须指向curr->next，否则哈希表会一直残留无效的头指针。
• 循环条件必须判断temp != NULL：这是遍历链表的标准写法，能避免访问野指针和无限循环。
• 避免循环引用：删除时绝对不能让任何节点的next指向已删除的节点或者自身，确保链表始终是单向无环的。
• 及时释放内存：删除节点后用free()释放，避免内存泄漏和野指针问题。

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