C / C++ / 系统课时
哈希冲突该怎么处理
哈希冲突该怎么处理
不同关键字可能经过哈希函数后落到同一个桶,这就是哈希冲突。链地址法不强行让每个桶只放一个元素,而是让桶保存链表头指针,把冲突元素串在一起。本节用 C 的“数组 + 单链表”实现可插入、查找和释放的最小哈希表。
学习目标
- 理解链地址法如何让多个关键字共享同一个桶
- 能用 C 语言实现桶数组、链表插入和按键查找
- 能根据装载因子判断链表过长对性能的影响
冲突发生时数据放在哪里
假设有 5 个桶,使用 key % 5。关键字 1、6、11 的余数都是 1,因此都会落到桶 1。链地址法让数组的每个元素保存一个链表头指针,冲突元素作为链表节点继续挂在该桶后面。

这种结构的关键点是:哈希函数只负责找到桶,真正的键匹配在桶内链表中完成。冲突不会覆盖旧数据,只会增加该桶需要比较的节点数量。
用数组加链表实现
下面的示例采用头插法。相同关键字再次插入时更新原值;新关键字发生冲突时分配新节点并挂到对应桶的链表头。
c
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#define BUCKET_COUNT 5
typedef struct Node {
int key;
int value;
struct Node *next;
} Node;
static size_t hash_int(int key) {
int r = key % BUCKET_COUNT;
return (size_t)(r < 0 ? r + BUCKET_COUNT : r);
}
static void put(Node *buckets[], int key, int value) {
size_t index = hash_int(key);
for (Node *p = buckets[index]; p != NULL; p = p->next) {
if (p->key == key) {
p->value = value;
return;
}
}
Node *node = malloc(sizeof(*node));
if (node == NULL) {
exit(EXIT_FAILURE);
}
node->key = key;
node->value = value;
node->next = buckets[index];
buckets[index] = node;
}
static int get(Node *const buckets[], int key, int *value) {
size_t index = hash_int(key);
for (Node *p = buckets[index]; p != NULL; p = p->next) {
if (p->key == key) {
*value = p->value;
return 1;
}
}
return 0;
}
static void print_bucket(Node *const buckets[], size_t index) {
printf("bucket[%zu]:", index);
for (Node *p = buckets[index]; p != NULL; p = p->next) {
printf(" (%d,%d)", p->key, p->value);
if (p->next != NULL) {
printf(" ->");
}
}
putchar('\n');
}
static void destroy(Node *buckets[]) {
for (size_t i = 0; i < BUCKET_COUNT; ++i) {
Node *p = buckets[i];
while (p != NULL) {
Node *next = p->next;
free(p);
p = next;
}
buckets[i] = NULL;
}
}
int main(void) {
Node *buckets[BUCKET_COUNT] = {0};
put(buckets, 1, 10);
put(buckets, 6, 60);
put(buckets, 11, 110);
put(buckets, 2, 20);
print_bucket(buckets, 1);
int value;
if (get(buckets, 6, &value)) {
printf("find key=6, value=%d\n", value);
}
destroy(buckets);
return 0;
}预期输出
text
bucket[1]: (11,110) -> (6,60) -> (1,10)
find key=6, value=60输出顺序是 11、6、1,因为示例使用头插法:后插入的新节点总是成为该桶链表的新头节点。
查找到底要走多少步
查找键 6 时,先通过哈希函数定位到桶 1,再从链表头开始比较:先看 11,再看 6,第二次比较命中。链地址法把“全表扫描”缩小成“只扫描一个桶里的链表”。
如果元素能比较均匀地分散到各桶,平均每个桶只有少量节点,查找通常仍接近 O(1)。常用装载因子 α = 元素数量 / 桶数量 描述桶的拥挤程度;α 越大,链表平均越长。极端情况下所有键都落入同一个桶,查找会退化到 O(n)。
实现时容易漏掉的边界
链地址法需要管理动态内存,因此删除节点和销毁哈希表时都必须 free。更新已有关键字前也要先查重,否则同一个键可能在链表里出现多份,导致查找结果依赖节点顺序。
链地址法的本质是“数组负责快速选桶,链表负责容纳冲突”。只要哈希分布合理、桶数量与数据规模匹配,它就能在保持实现清晰的同时维持较稳定的平均查找效率。
按自己的节奏,确认真正理解。