数据结构：哈希（Hashing）

目录

我们面临什么问题？(Why Hashing?)

直接定址法的缺点

如何构建映射？(Ideal Hashing & Modulus Hash Function)

理想中的哈希函数

一个简单实用的哈希函数：取模法 (Modulus Hash Function)

开始写我们的代码框架

冲突！冲突！(Drawbacks)

如何解决冲突？(Solutions)

方案一：往后站，找空位 (开放定址法 - Open Addressing)

开放定址法的缺点

方案二：在我的位置上“挂”一串 (拉链法 - Separate Chaining)

我们面临什么问题？(Why Hashing?)

想象一下，你正在为一个学校管理学生信息。每个学生都有一个独一无二的学号（比如从 10001 到 99999）。现在，你需要一个程序，能够快速地通过学号找到这个学生的全部信息（姓名、年龄等）。

最原始的想法：数组

最简单的想法，就是用一个数组来存学生信息。

struct Student {
    int id;       // 学号
    char name[50];
    // ... 其他信息
};

// 用一个大数组来存所有学生
Student student_list[100]; 
int current_size = 0; // 当前存储的学生数量

现在，问题来了：

如何通过学号 id 找到一个学生？

你只能这么做：

Student* findStudent(int target_id) {
    for (int i = 0; i < current_size; ++i) {
        if (student_list[i].id == target_id) {
            return &student_list[i]; // 找到了！
        }
    }
    return NULL; // 没找到
}

这个方法有什么缺点？非常明显，如果 student_list 里有 N 个学生，最坏的情况下（比如要找的学生在最后一个，或者根本不存在），你需要比较 N 次。我们把这个叫做时间复杂度为 O(N)。当学生数量非常庞大时，比如几万个，每次查询都可能要花费很长时间。

这太慢了。我们追求的目标是什么？

终极理想：一步到位

我们回顾一下数组最厉害的地方是什么？是它的 随机访问特性。只要你知道数组的下标 (index)，你就可以在 O(1) 的时间内，也就是一次计算就直接定位到那个元素。比如 student_list[5]，计算机可以马上找到它。

那么，我们能不能创造一种“魔法”，让 学号 (id) 和数组的 下标 (index) 产生直接的联系？

举个理想化的例子，假如我们的学号恰好是从 0, 1, 2, 3, ... 这样连续递增的，那事情就简单了。我们可以创建一个巨大的数组，直接用学号当下标。

// 这是一个非常理想化的情况
Student* student_direct_map[100000]; // 假设学号最大不超过 99999

// 存入 id 为 10001 的学生
student_direct_map[10001] = new Student(...); 

// 查找 id 为 10001 的学生
Student* s = student_direct_map[10001]; // 一步到位！O(1)

这种“直接用 key (关键字，这里指学号) 当作 index (下标)”的方法，我们称之为直接定址法 (Direct Addressing)。

直接定址法的缺点

1. 空间浪费：如果学号是 10001, 10002, 88888 这三个，我们却要为了 88888 这个学号，创建一个大小为 88889 的数组，中间大部分空间都浪费了。

2. Key 的类型限制：如果我们的 Key 不是整数，而是一个字符串（比如用学生姓名作为 Key），那怎么办？你总不能写 student_map["张三"] 吧？（在基础 C/C++ 语法里不行）。

所以，我们需要一个更普适性的方案，这个方案需要做到✅：

1. 能将 Key (无论是整数还是字符串) 转换成一个合法的数组下标 (index)。

2. 转换后的下标要尽可能地分布均匀，以节约空间。

这个将 Key 转换为 Index 的“转换过程”或者“转换函数”，就是我们接下来要讲的 哈希函数 (Hash Function)。而使用了这种思想的数据结构，就叫做 哈希表 (Hash Table)。

Hashing 的根本目的，是为了实现一种“映射关系”，将不适合直接做数组下标的、庞大且复杂的 Key 集合，转换为一个范围较小的、可以直接用作数组下标的 Index 集合，从而追求 O(1) 的查询效率。

如何构建映射？(Ideal Hashing & Modulus Hash Function)

这个“转换函数”，我们叫它 hash()。它的作用就是 index = hash(key)。

理想中的哈希函数

最理想的哈希函数应该是什么样的？

1️⃣ 一一对应 (One-to-one Mapping)：对于任意不同的 key1 和 key2，必须保证 hash(key1) 不等于 hash(key2)。这样，每个 Key 都有自己专属的“储物柜”，绝不会跟别人抢。

2️⃣ 计算速度快：这个转换过程本身不能太复杂，否则光是计算下标就花了很多时间，就得不偿失了。

3️⃣ 均匀分布：计算出来的 index 应该均匀地分布在数组的各个位置，避免扎堆，这样才能有效利用空间。

满足第一条的哈希函数我们称之为 完美哈希函数 (Perfect Hash Function)。但是，在大多数情况下，特别是当 Key 的范围和数量都无法预知时，设计一个完美的哈希函数是极其困难甚至是不可能的。

为什么？想象一下，你的 Key 可以是任意一个 5 位数的学号（90000个可能性），但你的哈希表数组大小只有 100。根据鸽巢原理 (Pigeonhole Principle)，你把 90000 只“鸽子”（Keys）放进 100 个“巢”（Indices），必然会有很多鸽子挤在同一个巢里。

所以，在现实中，我们必须接受一个残酷的事实：

不同的 Key，可能会计算出相同的 Index。

这个问题，我们称为 哈希冲突 (Hash Collision)。

我们先暂时忽略冲突问题，先来设计一个简单实用的哈希函数。

一个简单实用的哈希函数：取模法 (Modulus Hash Function)

对于整数类型的 Key，最常用、最简单的哈希函数就是取模法。

公式非常简单： index = key % TableSize

• key: 就是我们的关键字，比如学号 12345。

• TableSize: 就是我们哈希表（数组）的大小。

• %: 是取模运算符。

为什么这个方法可行❓

1. 结果合法：key % TableSize 的结果范围永远在 0 到 TableSize - 1 之间，这正好是数组的合法下标范围。

2. 计算简单：CPU 对取模运算的支持非常好，速度极快。

📌TableSize 的选择有讲究吗？

有。通常建议选择一个素数 (Prime Number)。为什么？

如果 TableSize 是一个合数，比如 10，那么 key 的某些因数特征会很容易导致冲突。

举个例子，如果 TableSize = 10，那么所有以 0 结尾的学号（10010, 10020, 10030...）都会哈希到下标 0，所有以 1 结尾的学号都会哈希到下标 1... 如果你的学号分配有某种规律，就很容易造成冲突扎堆。

而如果 TableSize 是一个素数，比如 13，那么 Key 和 TableSize 拥有公因数的可能性就会大大降低，使得数据分布得更“散”，更均匀。

开始写我们的代码框架

我们先定义出哈希表的结构。它本质上就是一个数组。数组里存什么呢？我们存指向学生信息的指针，这样如果某个位置没有学生，我们用 NULL 来表示，非常清晰。

#include <iostream>
#include <string.h>

// 1. 先定义数据结构
struct Student {
    int id;
    char name[50];
    // ... 其他信息
};

// 2. 定义哈希表的大小，选择一个素数
const int TABLE_SIZE = 11;

// 3. 定义哈希表，它是一个指针数组
Student* hashTable[TABLE_SIZE];

// 4. 实现我们的哈希函数 (取模法)
int hash_function(int key) {
    return key % TABLE_SIZE;
}

// 初始化哈希表，所有位置都设为 NULL
void init_hash_table() {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        hashTable[i] = NULL;
    }
}

到目前为止，我们已经有了哈希表的骨架。但它还不能工作，因为我们还没解决前面提到的“哈希冲突”问题。

冲突！冲突！(Drawbacks)

我们来模拟一下插入过程，看看冲突是怎么发生的。 假设 TABLE_SIZE = 11。

插入学号为 25 的学生 "张三":

• hash_function(25) -> 25 % 11 = 3。

• hashTable[3] 当前是 NULL，太好了，直接放进去。

• hashTable[3] = new Student{25, "张三"};

插入学号为 47 的学生 "李四":

• hash_function(47) -> 47 % 11 = 3。

• ⚠️冲突发生！ hashTable[3] 已经被 "张三" 占用了！我们该怎么办？"李四" 的数据无处安放了。

这就是哈希表最核心的挑战：冲突解决 (Collision Resolution)。

由于 Key 的空间远大于 Index 的空间，哈希冲突是不可避免的。因此，一个哈希表的实现好坏，很大程度上取决于它如何优雅地解决冲突。

如何解决冲突？(Solutions)

解决冲突的主流思想有两种，我们一步步来看。

方案一：往后站，找空位 (开放定址法 - Open Addressing)

这个思想很朴素：如果我的“储物柜”被人占了，我就看看下一个柜子是不是空的，如果是就用，如果还被占了，就再看下一个... 直到找到一个空柜子为止。

这种方法中最简单的叫做线性探测 (Linear Probing)。

• 计算初始哈希地址 index = hash(key)。

• 如果 hashTable[index] 被占用，就尝试 (index + 1) % TABLE_SIZE。

• 如果还被占用，就尝试 (index + 2) % TABLE_SIZE...

• 以此类推，直到找到一个空位 NULL。

我们来逐步完善代码，实现基于线性探测的插入和查找。

逐步完善代码：插入 (Insert)

// 插入函数（使用线性探测）
void insert_linear_probing(int id, const char* name) {
    // 1. 创建新节点
    Student* newStudent = new Student;
    newStudent->id = id;
    strcpy(newStudent->name, name);

    // 2. 计算初始哈希地址
    int index = hash_function(id);

    // 3. 线性探测寻找空位
    while (hashTable[index] != NULL) {
        // 这里可以加一个判断，如果表满了就报错退出
        index = (index + 1) % TABLE_SIZE;
    }

    // 4. 找到空位，放入新学生
    hashTable[index] = newStudent;
    std::cout << "学生 " << name << " 插入到位置 " << index << std::endl;
}

查找 (Search) 呢？

查找也必须遵循同样的探测路径。

• 计算初始哈希地址 index = hash(key)。

• 检查 hashTable[index] 里的学生 ID 是不是我要找的。

• 如果不是，就继续往后找 (index + 1) % TABLE_SIZE，直到：

• A. 找到了匹配的 ID。

• B. 遇到了一个 NULL 的位置。如果遇到 NULL，说明要找的人肯定不在表里（因为如果他在，当初插入时就一定会占据这条路径上的某个位置）。

逐步完善代码：查找 (Search)

// 查找函数（使用线性探测）
Student* search_linear_probing(int id) {
    // 1. 计算初始哈希地址
    int index = hash_function(id);

    // 2. 沿着探测路径查找
    // 探测的终止条件是遇到 NULL
    while (hashTable[index] != NULL) {
        if (hashTable[index]->id == id) {
            // 找到了！
            return hashTable[index];
        }
        // 没找到，继续向后探测
        index = (index + 1) % TABLE_SIZE;
    }
    
    // 遇到了 NULL，说明不存在
    return NULL;
}

开放定址法的缺点

它会导致一种叫做 “一次聚集” (Primary Clustering) 的问题。就是说，一旦发生冲突，后面的元素就更有可能填补到冲突位置的旁边，导致冲突的元素会“扎堆”连成一片。

当这一片越来越长，新来的元素要探测的次数就越来越多，查找效率就越来越低，逐渐退化成 O(N)。

有没有更好的办法，让冲突的元素不要互相影响呢？

方案二：在我的位置上“挂”一串 (拉链法 - Separate Chaining)

这个思想是，哈希表数组的每个位置，不再只存储一个元素，而是把它看作一个“链条”的头。所有哈希到这个位置的元素，都以链表的形式，“挂”在这个位置后面。

• hashTable[i] 不再是 Student* 类型，而是 Node*，指向一个链表的头节点。

• 发生冲突时，我们不需要去别的位置找空位，只需要把新来的元素加到对应位置的链表中即可。

我们来重新设计和完善我们的代码。

第一步：改造我们的数据结构

Student 结构体需要一个 next 指针，这样才能形成链表。

struct Student {
    int id;
    char name[50];
    Student* next; // 指向下一个学生的指针
};

第二步：改造哈希表定义

哈希表还是一个指针数组，但现在每个指针都指向一个 Student 节点的链表头。

// 哈希表大小
const int TABLE_SIZE = 11;
// 哈希表，每个元素都是一个链表的头指针
Student* hashTable[TABLE_SIZE]; 

// 初始化函数不变，还是把所有头指针都设为 NULL
void init_hash_table() {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        hashTable[i] = NULL;
    }
}

// 哈希函数也不变
int hash_function(int key) {
    return key % TABLE_SIZE;
}

第三步：实现插入 (Insert)

插入操作变得非常简单，就是在对应链表的头部插入一个新节点。

// 插入函数（使用拉链法）
void insert_chaining(int id, const char* name) {
    // 1. 创建新节点
    Student* newStudent = new Student;
    newStudent->id = id;
    strcpy(newStudent->name, name);
    newStudent->next = NULL; // 很重要，新节点的 next 是 NULL

    // 2. 计算哈希地址
    int index = hash_function(id);

    // 3. 插入到链表头部
    // 新节点的 next 指向原来链表的头
    newStudent->next = hashTable[index]; 
    // 哈希表的头指针指向新的节点
    hashTable[index] = newStudent; 

    std::cout << "学生 " << name << " 插入到链表 " << index << std::endl;
}

第四步：实现查找 (Search)

查找操作就是两步：

1. 通过哈希函数定位到是哪条链表。

2. 遍历这条链表，找到对应的节点。

// 查找函数（使用拉链法）
Student* search_chaining(int id) {
    // 1. 计算哈希地址，定位到链表
    int index = hash_function(id);
    
    // 2. 遍历该链表
    Student* current = hashTable[index];
    while (current != NULL) {
        if (current->id == id) {
            // 找到了！
            return current;
        }
        current = current->next;
    }
    
    // 遍历完链表都没找到
    return NULL;
}