0Pricing
C Academy · 课时

插入、查找、删除

核心操作

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

三个核心操作

每个哈希表都支持三种操作：插入、查找和删除。使用良好的哈希函数并保持合理的负载因子时，这三种操作的平均时间复杂度都是 O(1)。

我们将逐步构建一个基于链接法的哈希表。

哈希表与节点类型

我们定义一个节点，用于存放复制后的键字符串和一个整数值；此外还定义一个哈希表结构，用于存放桶数组及其容量。

#include <stdio.h>

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

typedef struct {
    Node **buckets;
    unsigned capacity;
    unsigned size;
} HashTable;

int main(void) {
    printf("types defined\n");
    return 0;
}

创建哈希表

使用 calloc 分配哈希表和已清零的桶数组，这样每个桶初始都是 NULL。

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

typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;

HashTable *ht_create(unsigned cap) {
    HashTable *t = malloc(sizeof *t);
    t->buckets = calloc(cap, sizeof(Node *));
    t->capacity = cap; t->size = 0;
    return t;
}

int main(void) {
    HashTable *t = ht_create(16);
    printf("capacity=%u size=%u\n", t->capacity, t->size);
    return 0;
}

哈希辅助函数

我们重新使用 DJB2，并将其结果缩小为桶索引。三个操作都会使用这个辅助函数。

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381; int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

unsigned bucket_of(const char *key, unsigned cap) {
    return (unsigned)(djb2(key) % cap);
}

int main(void) {
    printf("%u\n", bucket_of("name", 16));
    return 0;
}

插入：更新或插入到头部

插入时，先搜索对应的桶。如果键已存在，就更新它的值。否则分配一个新节点（通过 strdup 复制键），并将其插入链表头部。

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

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

Node *insert(Node *head, const char *key, int val) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) { p->value = val; return head; }
    Node *n = malloc(sizeof *n);
    n->key = strdup(key); n->value = val; n->next = head;
    return n;
}

int main(void) {
    Node *b = NULL;
    b = insert(b, "a", 1);
    b = insert(b, "a", 99); /* update */
    printf("%s=%d\n", b->key, b->value);
    return 0;
}

查找

查找操作会先计算键的哈希值，然后遍历桶链表，并使用 strcmp 比较键。找到时返回指向值的指针；如果不存在，则返回 NULL。

#include <stdio.h>
#include <string.h>

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

int *lookup(Node *head, const char *key) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) return &p->value;
    return NULL;
}

int main(void) {
    Node n2 = {"y", 20, NULL};
    Node n1 = {"x", 10, &n2};
    int *v = lookup(&n1, "y");
    printf("%d\n", v ? *v : -1);
    return 0;
}

删除：重新链接链表

删除操作遍历桶，同时保存指向前一个节点的指针，然后绕过目标节点重新连接链表，并释放目标节点（包括复制的键和节点本身）。

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

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

Node *delete_key(Node *head, const char *key) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next; else head = cur->next;
            free(cur->key); free(cur);
            return head;
        }
        prev = cur; cur = cur->next;
    }
    return head;
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("a"); b->value = 1; b->next = NULL;
    b = delete_key(b, "a");
    printf("%s\n", b ? "left" : "empty");
    return 0;
}

整合起来

完整的哈希表会先计算桶索引，再将操作交给链表辅助函数。下面展示一个完整的小型哈希表运行示例。

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

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

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

#define CAP 16
Node *table[CAP];

void put(const char *k, int v) {
    unsigned i = djb2(k) % CAP;
    Node *n = malloc(sizeof *n);
    n->key = strdup(k); n->value = v; n->next = table[i];
    table[i] = n;
}
int get(const char *k) {
    for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
        if (!strcmp(p->key, k)) return p->value;
    return -1;
}

int main(void) {
    put("age", 30); put("score", 95);
    printf("age=%d score=%d\n", get("age"), get("score"));
    return 0;
}

为什么要复制键

我们使用 strdup 存储键，使哈希表拥有自己的副本。如果直接存储调用者的指针，键可能在我们使用期间被修改或释放，从而破坏查找。

这也意味着删除时必须对复制的键调用 free。

时间复杂度

当哈希函数分布均匀，并将负载因子保持在 0.75 附近时：

  • 插入：平均 O(1)
  • 查找：平均 O(1)
  • 删除：平均 O(1)

最坏情况下，如果所有键都冲突到同一个桶中，复杂度为 O(n)。

释放整个哈希表

为避免内存泄漏，请释放每个桶中的所有节点，然后释放桶数组，最后释放哈希表结构。

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

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

void free_bucket(Node *head) {
    while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("k"); b->value = 1; b->next = NULL;
    free_bucket(b);
    printf("freed\n");
    return 0;
}

快速检查

测试您对核心操作的理解。

回顾

您使用链接法实现了哈希表的三个核心操作。

  • 插入会更新节点，或将节点插入链表头部
  • 查找使用 strcmp 遍历桶链表
  • 删除会重新链接链表，并释放键和节点
  • 使用 strdup 管理键的所有权，并在销毁时释放所有内容

常见问题解答

「插入、查找、删除」课时是免费的吗？

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

「插入、查找、删除」这节课中我会学到什么？

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

学习 C Academy 需要有经验吗？

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

「插入、查找、删除」课时需要多长时间？

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

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

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

此课程中的所有课时

  1. 哈希函数
  2. 冲突处理
  3. 插入、查找、删除
  4. 调整大小与负载因子
← 返回 C Academy