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。更新已有关键字前也要先查重,否则同一个键可能在链表里出现多份,导致查找结果依赖节点顺序。

链地址法的本质是“数组负责快速选桶,链表负责容纳冲突”。只要哈希分布合理、桶数量与数据规模匹配,它就能在保持实现清晰的同时维持较稳定的平均查找效率。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

哈希冲突该怎么处理

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通