5、链地址法实现（下）：查找、删除、销毁与遍历打印

好，咱们接着上一讲继续。上一章我们把链地址法的插入和初始化搞定了，这次来聊聊剩下的几个关键操作：查找、删除、销毁，还有遍历打印。这几个操作在实际项目中用的频率非常高，尤其是查找和删除，几乎是每个哈希表都绕不开的核心功能。

我个人习惯把哈希表的操作分成两类：一类是“改结构”的（插入、删除），一类是“读结构”的（查找、遍历）。销毁比较特殊，它属于“彻底清理”。咱们一个一个来看。

5.1 查找操作实现

查找的逻辑其实很简单：先通过哈希函数算出 key 对应的桶索引，然后在这个桶的链表里挨个找。说白了就是“先定位，再遍历”。

我在项目中遇到过一个问题：有些同学写查找时，直接把 key 和哈希表里的 key 做比较，但忘了处理 key 为 NULL 的情况。嗯，这里要注意，空桶的链表头是 NULL，直接遍历会崩溃。

来看代码：

// 查找键为 key 的节点，返回节点指针，没找到返回 NULL
HashNode* hashTableSearch(HashTable* ht, int key) {
    if (ht == NULL) {
        return NULL;
    }

    int index = hashFunc(key, ht->size);
    HashNode* cur = ht->table[index];

    while (cur != NULL) {
        if (cur->key == key) {
            return cur;  // 找到了
        }
        cur = cur->next;
    }

    return NULL;  // 没找到
}

这里有个小细节：hashFunc 必须和插入时用的是同一个函数，否则你算出来的桶索引对不上，永远找不到。我曾经见过一个项目，插入时用的哈希函数和查找时用的不一样，结果查了半天查不到数据，最后发现是函数版本没同步。

5.2 删除操作实现

删除比查找稍微复杂一点，因为你要操作链表。删除一个节点，需要知道它的前驱节点，这样才能把链表接上。当然，你也可以用“双指针”技巧来避免单独处理头节点的情况。

我个人习惯用双指针法，代码更简洁，不容易漏掉边界情况。

// 删除键为 key 的节点，成功返回 1，失败返回 0
int hashTableDelete(HashTable* ht, int key) {
    if (ht == NULL) {
        return 0;
    }

    int index = hashFunc(key, ht->size);
    HashNode** cur = &(ht->table[index]);

    while (*cur != NULL) {
        if ((*cur)->key == key) {
            HashNode* toDelete = *cur;
            *cur = (*cur)->next;  // 前驱的 next 指向当前节点的下一个
            free(toDelete);
            ht->count--;
            return 1;
        }
        cur = &((*cur)->next);
    }

    return 0;  // 没找到要删除的节点
}

你看，这里用了二级指针 HashNode** cur，它指向的是链表里每个节点的 next 指针（或者头指针本身）。这样删除时不需要单独判断“是不是头节点”，代码统一了。

5.3 哈希表销毁

销毁操作，说白了就是把整个哈希表清理干净。包括每个桶里的链表节点，还有哈希表结构体本身。如果你只 free 了哈希表结构体，而忘了释放链表节点，那内存泄漏就等着你了。

我曾经在一个嵌入式项目里吃过这个亏：程序跑着跑着内存越来越少，最后定位到是哈希表销毁时没释放节点。从那以后，我写销毁函数都会格外小心。

// 销毁整个哈希表
void hashTableDestroy(HashTable* ht) {
    if (ht == NULL) {
        return;
    }

    for (int i = 0; i < ht->size; i++) {
        HashNode* cur = ht->table[i];
        while (cur != NULL) {
            HashNode* next = cur->next;
            free(cur);
            cur = next;
        }
        ht->table[i] = NULL;
    }

    free(ht->table);
    free(ht);
}

这里有个关键点：遍历链表时，一定要先保存 next 指针，再 free 当前节点。否则 free 之后你就找不到下一个节点了。这个顺序搞反了，程序直接崩溃。

5.4 遍历与打印

遍历和打印，主要是为了调试和验证。实际项目中，你可能需要遍历所有元素做某种统计，或者把哈希表的内容 dump 出来看看。

我一般会写一个 hashTablePrint 函数，把每个桶的链表都打印出来，方便肉眼检查。

// 打印哈希表所有元素
void hashTablePrint(HashTable* ht) {
    if (ht == NULL) {
        printf("哈希表为空\n");
        return;
    }

    printf("哈希表容量: %d, 当前元素数: %d\n", ht->size, ht->count);
    for (int i = 0; i < ht->size; i++) {
        printf("桶[%d]: ", i);
        HashNode* cur = ht->table[i];
        if (cur == NULL) {
            printf("NULL");
        } else {
            while (cur != NULL) {
                printf("(%d) ", cur->key);
                cur = cur->next;
            }
        }
        printf("\n");
    }
}

这个函数会输出每个桶的链表内容。如果某个桶是空的，就打印 NULL。这样你一眼就能看出数据分布是否均匀。

5.5 整体流程示意图

下面我用一张 SVG 图来展示链地址法哈希表的完整操作流程，包括查找、删除、销毁和遍历的关系。

从这张图可以看得很清楚：哈希表的核心是桶数组，每个桶指向一个链表。查找和删除都需要先定位桶，再操作链表。销毁则是把所有的桶和节点全部释放。遍历就是挨个桶把链表内容打印出来。

5.6 避坑指南

最后，我把自己这些年踩过的坑总结一下，希望能帮你少走弯路：

• 查找时一定要判空：哈希表指针、桶指针、节点指针，任何一个为 NULL 都要提前返回。
• 删除时别忘了释放内存：C 语言没有垃圾回收，free 必须成对出现。
• 销毁时先释放节点，再释放桶数组，最后释放哈希表结构体：顺序搞反了，你就再也找不到那些节点了。
• 遍历时不要修改结构：如果一定要在遍历时删除，建议先记录要删除的节点，遍历完再统一处理。
• 哈希函数要一致：插入、查找、删除用的哈希函数必须是同一个，否则定位会出错。

好了，链地址法的核心操作就这些。代码看起来不多，但每个细节都值得仔细推敲。你写的时候可以自己多跑几个测试用例，尤其是边界情况：空表、只有一个元素、所有元素都冲突到同一个桶……把这些情况都覆盖到，代码的健壮性就上来了。

---