第八章 哈希表：哈希函数设计、冲突解决方法与C语言实现

哈希表，说白了就是“用空间换时间”的典型代表。你想想看，数组查找是O(1)，但前提是你得知道下标。链表插入是O(1)，但查找得遍历。哈希表呢？它把这两者的优点结合了——通过一个函数，把关键字直接映射成存储位置。

我刚开始学哈希表时，总觉得这东西很玄乎。后来在项目中做缓存系统，才真正体会到它的威力。嗯，今天我们就把它彻底讲透。

8.1 哈希函数设计——好的哈希函数长什么样？

哈希函数的核心任务，就是把任意长度的输入，压缩成固定长度的输出。这个输出，我们叫它哈希值。

一个好的哈希函数，需要满足三个条件：

• 计算简单——不能比查找本身还慢，那就本末倒置了
• 分布均匀——尽量避免不同的key映射到同一个位置
• 冲突少——理想情况下，每个key都有自己专属的位置

常见的哈希函数设计方法有几种：

方法	原理	适用场景
直接定址法	H(key) = a * key + b	关键字分布连续且已知
除留余数法	H(key) = key % p	最常用，p一般取质数
数字分析法	取关键字中分布均匀的几位	关键字已知且位数固定
平方取中法	key²后取中间几位	关键字分布不均匀时
折叠法	将关键字分成几段后相加	关键字位数较多时

我个人习惯用除留余数法，简单高效。但要注意，p的选择很关键。我曾经在一个项目中，p选了1000，结果数据分布极不均匀——因为关键字全是10的倍数。后来改成997（质数），问题就解决了。

8.2 冲突解决方法——两个key撞车了怎么办？

哈希函数再完美，冲突也是不可避免的。为什么？因为哈希表的大小是有限的，而输入空间是无限的。根据鸽巢原理，当数据量超过表长时，必然有冲突。

解决冲突，主要有两种思路：

8.2.1 开放地址法

开放地址法的核心思想是：既然这个位置被人占了，那我就去找下一个空位。找空位的方式有几种：

• 线性探测：H(key) + 1, +2, +3... 直到找到空位。简单，但容易产生“堆积”现象——冲突的数据会挤在一起。
• 二次探测：H(key) + 1², -1², +2², -2²... 可以缓解堆积，但可能找不到所有空位。
• 双重哈希：用第二个哈希函数计算步长。H(key) + i * H₂(key)。我个人比较推荐这种方法，分布更均匀。

8.2.2 链地址法

链地址法的思路更直接：每个哈希表位置，挂一个链表。冲突的元素，直接链在同一个位置后面。

链地址法的优点很明显：

• 插入和删除操作简单，不需要处理“已删除”标记
• 表的装载因子可以大于1（开放地址法不行）
• 适合不知道数据规模的情况

缺点呢？如果链表太长，查找效率会退化到O(n)。所以当链表长度超过某个阈值时，可以考虑把链表换成红黑树——Java的HashMap就是这么干的。

8.3 哈希表C语言实现——手写一个能用的哈希表

光说不练假把式。我们来实现一个基于链地址法的哈希表。为什么选链地址法？因为实现简单，而且我在项目中用得最多。

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

#define TABLE_SIZE 101  // 质数

// 链表节点
typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

// 哈希表
typedef struct {
    Node **buckets;  // 桶数组，每个桶是一个链表头
    int size;
} HashTable;

// 哈希函数：除留余数法
int hash(const char *key, int size) {
    unsigned long h = 0;
    while (*key) {
        h = (h << 5) + *key++;  // 类似Java的String.hashCode()
    }
    return h % size;
}

// 创建哈希表
HashTable* createTable(int size) {
    HashTable *table = malloc(sizeof(HashTable));
    table->size = size;
    table->buckets = calloc(size, sizeof(Node*));
    return table;
}

// 插入
void insert(HashTable *table, const char *key, int value) {
    int index = hash(key, table->size);
    Node *node = table->buckets[index];
    
    // 检查key是否已存在
    while (node) {
        if (strcmp(node->key, key) == 0) {
            node->value = value;  // 更新
            return;
        }
        node = node->next;
    }
    
    // 头插法
    Node *newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = table->buckets[index];
    table->buckets[index] = newNode;
}

// 查找
int* search(HashTable *table, const char *key) {
    int index = hash(key, table->size);
    Node *node = table->buckets[index];
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return &node->value;
        }
        node = node->next;
    }
    return NULL;  // 没找到
}

// 删除
void delete(HashTable *table, const char *key) {
    int index = hash(key, table->size);
    Node *node = table->buckets[index];
    Node *prev = NULL;
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) {
                prev->next = node->next;
            } else {
                table->buckets[index] = node->next;
            }
            free(node->key);
            free(node);
            return;
        }
        prev = node;
        node = node->next;
    }
}

// 释放哈希表
void freeTable(HashTable *table) {
    for (int i = 0; i < table->size; i++) {
        Node *node = table->buckets[i];
        while (node) {
            Node *tmp = node;
            node = node->next;
            free(tmp->key);
            free(tmp);
        }
    }
    free(table->buckets);
    free(table);
}

8.4 哈希表的核心知识体系

下面这张图，把哈希表的核心知识点串起来了。你仔细看看，就能明白各个部分之间的关系。

8.5 避坑指南——我踩过的那些坑

哈希表看起来简单，但实际用起来，坑不少。我分享几个亲身经历：

• 哈希函数不要用随机数：我曾经图省事，用rand()做哈希。结果每次程序重启，同一个key的哈希值都不一样，数据全乱套了。哈希函数必须是确定性的。
• 注意字符串的哈希计算：如果key是字符串，一定要考虑大小写。我有个项目，用户输入"Hello"和"hello"被当成两个不同的key，查了半天才发现是大小写问题。
• 装载因子要控制：链地址法虽然可以超过1，但超过2之后性能就开始明显下降。我一般控制在0.75左右，超过就扩容。
• 扩容要rehash：表长变了，所有元素的哈希值都要重新计算。不能直接复制过去，否则查找会出错。

嗯，哈希表的内容就讲到这里。代码我已经贴出来了，建议你亲手敲一遍，跑几个测试用例试试。只有自己动手，才能真正理解里面的细节。