C Academy · 课时

冲突处理

Q: 「冲突处理」这节课中我会学到什么？

链式法与探测法 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

链式法与探测法

冲突处理 是 CoddyKit 上的免费 C Academy 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

冲突问题

当两个不同的键哈希到同一个桶时，就会发生冲突。由于冲突无法避免，每个哈希表都需要一种策略，以便在同一个槽中存储多个键。

两大主要方案是链式法和开放寻址法。

分离链接法

使用分离链接法时，每个桶都存放一个条目链表。发生冲突时，只需将条目追加到（或插入到）该桶的链表中即可。

桶存储链表头指针
查找只需遍历一个较短的链表

链接节点结构

每个节点存储一个键、一个值以及一个指向下一个节点的指针。哈希表是一个节点指针数组。

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *buckets[8] = {0};
    printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
    return 0;
}

使用链接法插入

将节点插入桶链表的头部只需 O(1) 时间。这里我们手动构建一个很小的链，并将其打印出来。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *next; } Node;

Node *prepend(Node *head, int key) {
    Node *n = malloc(sizeof *n);
    n->key = key; n->next = head;
    return n;
}

int main(void) {
    Node *bucket = NULL;
    bucket = prepend(bucket, 10);
    bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
    for (Node *p = bucket; p; p = p->next)
        printf("%d ", p->key);
    printf("\n");
    return 0;
}

开放寻址法

使用开放寻址法时，每个条目都直接存放在桶数组中。发生冲突时，会按照固定的序列探测其他空槽位。

无需分配额外节点，因此对缓存友好。

线性探测

线性探测会检查下一个槽位，再检查下一个槽位，并在到达末尾后绕回开头：(h + i) % capacity。

这种方法简单且对缓存友好，但会受到聚集问题的影响。

#include <stdio.h>

int main(void) {
    int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
    unsigned h = 2, cap = 8;
    for (unsigned i = 0; i < cap; i++) {
        unsigned idx = (h + i) % cap;
        if (!slots[idx]) { printf("insert at %u\n", idx); break; }
    }
    return 0;
}

二次探测

二次探测使用 (h + i*i) % capacity 来分散探测位置，减少主要聚集。

#include <stdio.h>

int main(void) {
    unsigned h = 3, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
    return 0;
}

双重哈希

双重哈希使用第二个哈希值确定步长：(h1 + i*h2) % capacity。这样每个键都有自己的探测序列，并且在这三种方法中分布最均匀。

#include <stdio.h>

int main(void) {
    unsigned h1 = 3, h2 = 5, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
    return 0;
}

开放寻址法中的删除

在开放寻址法中，不能直接清空一个槽位，因为这样会破坏其他键的探测链。正确做法是将其标记为墓碑，这样查找时仍会继续探测经过该位置。

链接法与开放寻址法

权衡：

链接法：能够处理较高的负载因子，删除简单，但会使用指针并进行内存分配
开放寻址法：对缓存友好，不需要为每个条目单独分配内存，但接近满载时性能会急剧下降，并且需要墓碑

探测次数演示

当槽位发生聚集时，线性探测可能需要多次尝试。这里我们统计找到空槽位所需的探测次数。

#include <stdio.h>

int main(void) {
    int slots[8] = {1,1,1,0,0,0,0,0};
    unsigned h = 0, cap = 8, probes = 0;
    for (unsigned i = 0; i < cap; i++) {
        probes++;
        if (!slots[(h + i) % cap]) break;
    }
    printf("probes used = %u\n", probes);
    return 0;
}

快速检查

测试您对冲突处理的理解。

回顾

您了解了哈希表如何解决冲突。

链接法为每个桶存储一个链表
开放寻址法探测空槽位
探测变体包括：线性探测、二次探测和双重哈希
开放寻址法需要使用墓碑来执行删除

常见问题解答

「冲突处理」课时是免费的吗？

是的 — 「冲突处理」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「冲突处理」这节课中我会学到什么？

链式法与探测法你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 2 节课，共 4 节。

「冲突处理」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy