哈希查找：从概念到实战

哈希查找，说白了就是一种“以空间换时间”的查找技术。我刚开始学数据结构时，总觉得它很神秘——凭什么能在 O(1) 时间内找到数据？后来自己动手写了一个电话簿系统，才真正体会到它的威力。

哈希表的核心概念

哈希表（Hash Table）也叫散列表。它的核心思想很简单：通过一个函数，把关键字直接映射到存储位置。你想想看，如果每个关键字都能算出唯一的位置，那查找不就变成了一次计算吗？

举个例子：假设你要存储 100 个学生的学号，学号范围是 2024001~2024100。最笨的办法是开一个 2024100 大小的数组，但这样太浪费了。哈希表就能用更小的空间，完成同样的任务。

哈希函数的构造方法

哈希函数的设计，直接决定了哈希表的性能。我见过不少新手随便写个函数，结果冲突率高达 80%，那还不如用链表呢。下面介绍三种最常用的方法。

1. 直接定址法

这是最直观的方法：H(key) = a * key + b。说白了就是线性变换。

比如学生学号从 2024001 开始，我们可以用：H(key) = key - 2024000。这样学号 2024001 就映射到位置 1，2024002 映射到位置 2，完美无冲突。

2. 除留余数法

这是最通用的方法：H(key) = key % p。p 通常选一个不大于表长的质数。

为什么选质数？我举个例子你就明白了。假设表长是 10，p 选 10。那么所有以 0 结尾的关键字（10, 20, 30...）都会映射到位置 0，冲突率极高。但 p 选 7 这样的质数，分布就均匀多了。

// 除留余数法示例
#define TABLE_SIZE 13  // 选质数作为表长

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

// 测试分布
int main() {
    int keys[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    for (int i = 0; i < 10; i++) {
        printf("key=%d, hash=%d\n", keys[i], hash(keys[i]));
    }
    return 0;
}

3. 数字分析法

这种方法适合关键字位数较多的情况。比如手机号 13812345678，我们可以分析每位数字的分布规律，选取分布最均匀的几位作为哈希地址。

我记得有一次处理身份证号数据，前 6 位是地区码，分布很不均匀。但后 4 位（出生日期）分布就很好。用数字分析法，我选了后 4 位作为哈希地址，冲突率从 30% 降到了 5%。

冲突处理方法

冲突是哈希表绕不开的问题。你想想看，再好的哈希函数，也不能保证 100% 无冲突。那冲突了怎么办？有两种主流方案。

1. 开放定址法

开放定址法的思路是：如果位置被占了，就按某种规则找下一个空位。常见的有三种探测方式：

• 线性探测：H(key) + 1, H(key) + 2, ... 简单但容易产生聚集
• 二次探测：H(key) + 1², H(key) - 1², H(key) + 2², ... 能缓解聚集
• 伪随机探测：用随机数序列决定探测顺序

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

2. 链地址法

链地址法更直接：每个位置不再存数据，而是存一个链表的头指针。冲突的元素都挂在这个链表上。

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

typedef struct {
    Node** heads;  // 指针数组
    int size;
} HashTable;

// 插入操作
void insert(HashTable* ht, int key) {
    int index = hash(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = ht->heads[index];
    ht->heads[index] = newNode;  // 头插法
}

我个人更偏爱链地址法。为什么？因为它的删除操作很简单，而且表可以存超过表长的元素。我在做缓存系统时就用它，效果很稳定。

哈希查找性能分析

哈希表的性能，主要看三个指标：装填因子 α、冲突率、查找长度。

装填因子 α = 已存元素数 / 表长。α 越大，冲突概率越高，性能越差。我一般建议 α 控制在 0.7~0.8 之间。

装填因子 α	线性探测成功查找	链地址法成功查找
0.5	1.5	1.25
0.7	2.17	1.35
0.9	5.5	1.45

从表格能看出：α 超过 0.8 后，线性探测的性能急剧下降。而链地址法受 α 影响小得多，这也是我推荐它的原因。

知识体系总览

下面这张图，把哈希查找的核心知识点串起来了。你可以对照着复习：

哈希查找的精髓，在于用空间换时间。你设计得好，查找就是 O(1)；设计不好，退化成 O(n) 也是常有的事。嗯，关键就两点：选对哈希函数，处理好冲突。