一、哈希表：用空间换时间的艺术

哈希表，说白了就是一种「通过关键字直接访问」的数据结构。我刚开始学的时候，觉得它就是个高级数组——数组用下标找值，哈希表用哈希函数把关键字映射成下标。

你想想看，如果我们要在10000个学生里找学号2024001的同学。用链表？得一个个遍历。用平衡树？也得O(log n)。但哈希表呢？理想情况下O(1)！这就是它的魅力所在。

1.1 哈希表的基本概念

哈希表由三部分组成：

• 哈希函数：把关键字转换成数组下标的函数
• 哈希表（散列表）：存储数据的数组
• 冲突解决机制：当两个关键字映射到同一位置时的处理办法

我在项目中遇到过一个问题：用哈希表做IP地址快速查找。当时选了个不好的哈希函数，结果大量IP都挤到同一个槽位上，性能还不如线性查找。嗯，这里要注意——哈希函数的设计，直接决定了哈希表的生死。

1.2 哈希函数设计

好的哈希函数，应该满足三个条件：

1. 计算简单——不能比查找本身还慢
2. 分布均匀——关键字尽量均匀分布在表中
3. 冲突少——不同关键字映射到同一位置的概率低

常见的哈希函数有几种：

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

我个人习惯用除留余数法。简单，而且只要p选得好，效果就不错。p怎么选？选一个接近表长且不包含小于20的质因数的质数。比如表长1000，p可以选997。

1.3 冲突处理方法

冲突是哈希表绕不开的坎。再好的哈希函数，也难免有碰撞。处理冲突，主流有两种思路：

开放地址法

思想很简单：如果位置被占了，就按某种规则找下一个空位。

常见的探测方式有三种：

• 线性探测：H(key) + 1, +2, +3... 直到找到空位
• 平方探测：H(key) + 1², -1², +2², -2²...
• 双哈希探测：用第二个哈希函数决定步长

线性探测最容易实现，但有个问题——聚集现象。一旦发生冲突，冲突的元素会挤在一起，后续插入和查找都会变慢。我做过测试，当装载因子超过0.7时，线性探测的性能会急剧下降。

平方探测能缓解聚集，但要注意：它不一定能探测到所有空位。只有表长是4k+3的质数时，才能保证探测到整个表。

// 线性探测插入示例
int hash_insert(int *table, int size, int key) {
    int index = key % size;
    int i = 0;
    
    while (table[(index + i) % size] != EMPTY) {
        if (table[(index + i) % size] == key) {
            return -1;  // 已存在
        }
        i++;
        if (i == size) return -1;  // 表满
    }
    
    table[(index + i) % size] = key;
    return 0;
}

链地址法

这个方法更直接：每个槽位不存数据，而是存一个链表的头指针。冲突的元素，直接挂到链表后面。

我个人更偏爱链地址法，原因有三：

1. 装载因子可以大于1——链表能无限挂下去
2. 删除操作简单——直接从链表里摘掉节点就行
3. 性能退化平滑——不会像开放地址法那样突然崩溃

// 链地址法插入示例
typedef struct Node {
    int key;
    struct Node *next;
} Node;

void chain_insert(Node **table, int size, int key) {
    int index = key % size;
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->key = key;
    new_node->next = table[index];
    table[index] = new_node;  // 头插法
}

1.4 哈希表的查找与性能分析

哈希表的查找，理想情况下是O(1)。但实际性能取决于三个因素：

• 哈希函数的质量——分布越均匀，冲突越少
• 装载因子α——α = 已存元素数 / 表长
• 冲突处理方法——不同方法在不同α下表现不同

对于开放地址法：

• 成功查找：ASL ≈ 1/2 * (1 + 1/(1-α))
• 失败查找：ASL ≈ 1/2 * (1 + 1/(1-α)²)

对于链地址法：

• 成功查找：ASL ≈ 1 + α/2
• 失败查找：ASL ≈ α

你看，当α=0.5时，开放地址法成功查找平均需要1.5次，链地址法只需要1.25次。当α=0.9时，开放地址法需要5.5次，链地址法只需要1.45次。差距很明显。

1.5 哈希表知识体系图

下面这张图，把哈希表的核心知识点串起来了：

1.6 总结

哈希表是个好东西，但用不好就是灾难。我见过太多人随便选个哈希函数，结果性能惨不忍睹。记住三点：

• 哈希函数要均匀——除留余数法选质数p
• 冲突处理要选对——链地址法更灵活，开放地址法省内存
• 装载因子要控制——超过0.75就扩容

嗯，哈希表的内容就这些。下一章我们聊聊树，那又是另一片天地了。

---