哈希表：让查找飞起来的数据结构

各位同学，今天我们来聊聊哈希表。说实话，我当年刚学数据结构时，第一次接触哈希表的感觉就是——这玩意儿太聪明了！它不像二分查找那样需要数据有序，也不像链表那样一个个遍历。哈希表追求的是：你给一个键，我直接算出位置，一步到位。

但别高兴太早。哈希表虽然快，但坑也不少。我在项目中就吃过它的亏，今天一并讲给你们听。

哈希表的核心思想

说白了，哈希表就是通过一个函数，把关键字映射到数组的某个位置。这个函数叫哈希函数，这个数组叫哈希表。

举个例子：假设你有一个班级，每个学生有学号。你想快速找到某个学号的学生信息。最笨的办法是遍历——O(n)。好一点的是排序后二分——O(log n)。但哈希表能做到什么？O(1)！

怎么做到的？你设计一个函数 f(key) = key % 100，然后直接把学号对100取余，余数就是数组下标。查的时候同样算一次余数，直接定位。是不是很爽？

哈希函数构造：好函数长什么样？

哈希函数是哈希表的灵魂。一个糟糕的哈希函数会让所有键挤到同一个位置——那还不如用链表呢。

我个人习惯，构造哈希函数时关注三点：

• 计算简单——不能比查找本身还慢
• 分布均匀——尽量避免冲突
• 减少碰撞——不同键尽量映射到不同位置

常见的构造方法有几种：

方法	做法	适用场景
直接定址法	f(key) = a * key + b	关键字分布连续且已知
除留余数法	f(key) = key % p	最常用，p选质数效果更好
数字分析法	取关键字中分布均匀的几位	关键字位数较多时
平方取中法	先平方，再取中间几位	关键字分布不均匀时
折叠法	将关键字分成几段，再相加	关键字位数很长时

我在项目中用得最多的是除留余数法。为什么？简单、高效、够用。但注意那个p——我建议选质数，而且不要接近2的幂。为什么？你想想看，如果p是偶数，那么所有偶数key都会映射到偶数位置，奇数key到奇数位置——分布就不均匀了。

冲突处理方法：躲不开的坎

哈希函数再完美，冲突也是不可避免的。为什么？因为映射空间通常小于关键字空间——这是数学上的鸽巢原理。

冲突处理有两种主流思路：

1. 开放地址法

当位置被占用了，就按某种规则找下一个空位。常见的探测方式有：

• 线性探测：依次往后找。简单，但容易产生「堆积」——冲突的键会挤在一起。
• 二次探测：按 1², -1², 2², -2²... 的步长找。能缓解堆积，但可能跳不到某些位置。
• 双重哈希：用第二个哈希函数计算步长。效果最好，但计算量也最大。

我记得有一次做嵌入式项目，内存非常紧张，只能用开放地址法。我选了线性探测，结果数据量一上来，查找性能急剧下降。后来换成双重哈希，虽然每次计算多了几个指令，但整体查找时间反而降下来了。嗯，这里要注意：开放地址法对装载因子非常敏感，超过0.7性能就开始跳水。

2. 链地址法

每个哈希表位置挂一个链表。冲突了？直接往链表后面加。这是我最喜欢的方式——简单、直观、不怕冲突。

// 链地址法哈希表节点定义
typedef struct HashNode {
    int key;
    int value;
    struct HashNode *next;
} HashNode;

// 哈希表
typedef struct {
    HashNode **buckets;  // 指针数组，每个元素指向一个链表
    int size;            // 桶的数量
} HashMap;

// 插入
void hashmap_insert(HashMap *map, int key, int value) {
    int index = key % map->size;
    HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    // 头插法
    node->next = map->buckets[index];
    map->buckets[index] = node;
}

// 查找
int hashmap_find(HashMap *map, int key) {
    int index = key % map->size;
    HashNode *cur = map->buckets[index];
    while (cur) {
        if (cur->key == key) return cur->value;
        cur = cur->next;
    }
    return -1;  // 没找到
}

哈希查找分析：到底有多快？

哈希表的查找时间复杂度，理论上说是O(1)。但这是有前提的：

• 哈希函数足够均匀
• 冲突处理得当
• 装载因子控制合理

实际工程中，哈希查找的平均时间可以近似为：

链地址法： 1 + α/2 （α是装载因子）
开放地址法： 1/(1-α) （线性探测）

你看，当α=0.5时，链地址法平均查找1.25次，开放地址法平均2次。当α=0.9时，链地址法1.45次，开放地址法直接飙到10次！

所以我的建议是：链地址法把α控制在0.75~1.0之间，开放地址法控制在0.5~0.7之间。超过这个范围，就该扩容了。

哈希表的知识体系

下面这张图，是我梳理的哈希表核心知识脉络。你看一遍，心里就有谱了。

实际项目中的避坑指南

最后，分享几个我亲身踩过的坑：

• 不要用字符串直接当key：字符串哈希计算开销大。我一般先转成整数再哈希，或者用FNV-1a这种轻量哈希算法。
• 多线程环境要加锁：哈希表不是线程安全的。我习惯用读写锁——读多写少时性能影响很小。
• 删除操作要小心：开放地址法删除不能直接置空，否则会断链。要用「惰性删除」标记。链地址法就没这问题。
• 哈希表不是万能的：数据量很小（比如几十个）时，线性查找可能更快——因为哈希计算也有开销。

好了，哈希表的内容就讲到这里。记住一句话：哈希表用得好，查找没烦恼；哈希表用不好，调试到天亮。各位下去多写代码，遇到问题欢迎交流。

---

公众号:蓝海资料掘金营，微信deep3321