哈希表：从理论到实战，我的一些经验之谈

哈希表，说白了就是“用空间换时间”的典型代表。你想想看，我们想要一个数据结构，能在 O(1) 时间内完成查找、插入、删除。数组能做到，但前提是你得知道下标。链表能做到，但得从头遍历。哈希表就是那个“中间人”——它把任意数据映射成一个整数下标，然后直接去数组里取。

嗯，今天我们就来聊聊哈希表的几个核心问题：哈希函数怎么构造？冲突了怎么办？装填因子又是什么鬼？

哈希函数构造：直接定址法与除留余数法

哈希函数的目标很简单：把关键字映射到数组下标。但映射得好不好，直接决定了哈希表的性能。

直接定址法

直接定址法是最简单粗暴的方式。公式是：hash(key) = a * key + b。比如，你要存储学生学号，学号范围是 1001~2000，那你可以直接取 hash(key) = key - 1001，这样下标就是 0~999。

我在项目中遇到过一种情况：某个系统需要存储设备ID，ID是连续递增的整数。我当时就直接用了直接定址法，简单高效，没有任何冲突。但你要注意，直接定址法只适用于关键字分布均匀且范围不大的场景。如果关键字范围很大，比如 0~2^32，你不可能开一个 40 亿长度的数组吧？

除留余数法

这是最常用的方法。公式：hash(key) = key % p。p 一般取一个质数，且接近表长。

为什么取质数？我举个例子你就明白了。假设表长是 10，p 取 10。那么所有 key 的哈希值只取决于 key 的最后一位。如果 key 都是偶数，那哈希值全是偶数，一半空间浪费了。取质数能最大程度地打散分布。

// 除留余数法示例
#define TABLE_SIZE 13  // 取质数

int hash(int key) {
    return key % TABLE_SIZE;
}

冲突处理：开放地址法与链地址法

哈希函数再完美，冲突也是不可避免的。你想想看，100 个鸡蛋放 10 个篮子，总有几个篮子要装多个蛋。冲突处理就是解决“多个 key 映射到同一个下标”的问题。

开放地址法

开放地址法的思路是：如果当前位置被占了，就按某种规则去找下一个空位。常见的探测方式有线性探测、二次探测、双重哈希。

线性探测：冲突了就往后挪一位，直到找到空位。

// 线性探测插入
int insert(int table[], int key) {
    int index = key % TABLE_SIZE;
    while (table[index] != EMPTY) {
        index = (index + 1) % TABLE_SIZE;  // 往后挪
    }
    table[index] = key;
    return index;
}

线性探测有个问题——聚集现象。一旦连续几个位置被占，后面的 key 会不断往后挤，形成一大片“拥堵区”。我曾经在一个项目中用线性探测，装填因子到了 0.7 之后，查找性能急剧下降，插入一个元素要探测七八次。

二次探测：探测步长是 1², 2², 3²... 这样能缓解聚集，但要注意，二次探测不一定能遍历所有位置。

// 二次探测
int index = key % TABLE_SIZE;
int i = 1;
while (table[index] != EMPTY) {
    index = (index + i * i) % TABLE_SIZE;
    i++;
}

链地址法

链地址法更直观：每个数组元素不再存数据，而是存一个链表的头指针。冲突的元素直接挂在链表后面。

// 链地址法结构
typedef struct Node {
    int key;
    struct Node *next;
} Node;

Node *hashTable[TABLE_SIZE];

void insert(int key) {
    int index = key % TABLE_SIZE;
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = hashTable[index];  // 头插法
    hashTable[index] = newNode;
}

链地址法的好处是：装填因子可以大于 1，而且删除操作很方便。我在做缓存系统时特别喜欢用链地址法，因为缓存经常要删除过期数据，链表操作比开放地址法灵活得多。

装填因子与查找性能

装填因子 α = 表中元素个数 / 表长。它直接反映了哈希表的“拥挤程度”。

你想想看，α = 0.5 意味着表有一半是空的，冲突概率低，查找快。α = 0.9 意味着表快满了，冲突频繁，查找慢。

对于开放地址法，平均查找长度（ASL）与 α 的关系是：

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

对于链地址法，平均查找长度：

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

装填因子 α	开放地址法（成功查找）	链地址法（成功查找）
0.5	1.5	1.25
0.7	2.17	1.35
0.9	5.5	1.45

看到没？α 从 0.7 升到 0.9，开放地址法的查找次数从 2.17 飙升到 5.5，而链地址法只从 1.35 涨到 1.45。这就是为什么我建议：如果无法预估数据量，优先选链地址法。

知识体系总览

下面这张图是我自己整理的哈希表知识结构，你可以对照着回顾一下：

哈希表的核心就这些：选好哈希函数，处理好冲突，控制好装填因子。我在实际项目中，90% 的情况都用链地址法，因为它的性能更稳定，不容易出现极端情况。开放地址法我只在内存极度受限的嵌入式场景下使用。

好了，哈希表的内容就到这里。记住一句话：没有完美的哈希表，只有适合场景的哈希表。

---

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