哈希表的概念与原理

哈希表是一种非常高效的数据结构，它通过一个叫做“哈希函数”的映射规则，让数据能够几乎瞬间被找到。你可以把它想象成一本“魔法电话簿”或“超级索引”：你不需要一页页翻，只要说出名字，它就能直接告诉你号码在哪儿。哈希表常用于需要快速查找、插入和删除的场景，比如缓存系统、数据库索引、编程语言中的字典（Dictionary）或映射（Map）类型。

从生活中的例子说起

想象一下，你有一本巨大的电话簿，里面记录了所有人的电话号码。如果电话簿是按姓氏拼音顺序排列的，你要找“张三”的电话，就得从“Z”开头的部分一页一页翻，这很慢。但如果有一台神奇的机器，你输入“张三”，它立刻就能告诉你电话号码在哪里——这台机器就是“哈希表”的灵感来源。

再比如，你去图书馆借书，每本书都有一个编号（比如“TP312”）。如果管理员把所有书按编号放在对应的书架上，你只要知道编号，就能直接走到那个书架前找到书，而不用遍历整个图书馆。这个编号就是“哈希值”，书架就是“哈希表”中的位置。

更多贴近生活的例子：

零食分发：老师有 100 个学生，每人的学号最后两位是 00~99。老师把学号最后两位相同的零食放在同一个篮子（桶）里，想吃零食的学生报上学号后两位，直接去对应篮子拿。学号后两位就是“哈希值”，篮子就是“桶”。
体育课分组：体育老师让同学们按出生月份（1~12）排成 12 列。每来一个新同学，老师问“你几月出生？”然后直接让 TA 站到第几列。这样找人或集合时，只要知道月份就能立即找到对应的队伍。月份就是“哈希值”，12 列就是“哈希表”。

什么是哈希表？

哈希表（Hash Table），也叫散列表，是一种数据结构。它通过一个叫做“哈希函数”（Hash Function）的规则，把我们要存储的数据（比如名字、学号）转换成一个数字（哈希值），然后用这个数字决定数据存放在数组的哪个位置。

核心思想：我们想快速找到某个数据，就不必一个一个地比较，而是直接根据数据的“特征”算出它应该所在的位置。

生活中的类比：

每个学生有一个学号（比如2024001），学校把学号对1000取模（学号 % 1000 = 1），然后把所有学号尾数为1的学生信息放在第1号柜子。这样，要找一个学生，直接看他的学号尾数，就去对应的柜子找。这里“学号 % 1000”就是哈希函数，1000个柜子就是哈希表。

哈希表的原理与核心思想

哈希表本质上是一个数组（或链表数组），数组的每个位置叫做“槽”（Slot）或“桶”（Bucket）。哈希函数把“键”（Key）映射到数组的索引。

假设我们有一个长度为 M 的数组，哈希函数 h(key) 返回一个 0 到 M-1 之间的整数。当我们要插入一个键值对 (key, value) 时，先计算 index = h(key)，然后把 value 存储到数组的 index 位置。查找时，同样计算 h(key)，然后直接去那个位置取。

示意图：

键: "apple"  ->  哈希函数 h("apple") = 3  ->  数组位置 3 存储 "苹果" 的信息
键: "banana" ->  h("banana") = 7  ->  位置 7 存 "香蕉"
键: "cherry" ->  h("cherry") = 3  ->  哎呀，和 "apple" 冲突了！（后面会讲冲突处理）

ASCII 示意图：

      +-----+-----+-----+-----+-----+-----+-----+-----+
索引: | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   |
      +-----+-----+-----+-----+-----+-----+-----+-----+
数据: |     |     |     |apple|     |     |     |banana|
      +-----+-----+-----+-----+-----+-----+-----+-----+

冲突与处理方法

不同 key 可能算出相同的哈希值，这就叫冲突（Collision）。比如上面的 “apple” 和 “cherry” 都映射到索引 3。冲突是哈希表需要解决的核心问题。常见处理方法有两种：

链地址法（Separate Chaining）：每个数组位置不存一个数据，而是存一个链表（或列表）。所有哈希值相同的 key 都挂到同一个链表中。查找时，先定位到桶，再在链表中顺序查找。
开放地址法（Open Addressing）：如果发现目标位置已被占用，就按某种规则（比如向后挪一个位置）寻找下一个空位。优点是节省空间，但删除时更复杂。

我们下面用链地址法实现，因为它最直观、最容易理解。

简单实现：用链表数组处理冲突

下面我们用一个简单的例子来实现哈希表：假设键是整数，哈希函数取模（key % tableSize）。我们使用链地址法（相同哈希值的键放在同一个链表中）。

C++ 完整代码实现

#include <iostream>
#include <vector>
#include <list>
using namespace std;

// 哈希表类，链地址法
class HashTable {
private:
    int size;                     // 哈希表大小（桶的数量）
    vector<list<int>> table;      // 数组，每个元素是一个链表（存键）

    // 哈希函数：取模（假设 key 非负）
    int hashFunction(int key) {
        return key % size;
    }

public:
    // 构造函数，初始化表大小
    HashTable(int s) : size(s) {
        table.resize(size);   // 为数组分配 size 个空链表
    }

    // 插入键
    void insert(int key) {
        int index = hashFunction(key);        // 计算桶索引
        table[index].push_back(key);          // 将键添加到对应链表的末尾
    }

    // 查找键是否存在
    bool search(int key) {
        int index = hashFunction(key);        // 计算桶索引
        // 遍历该位置的链表
        for (int k : table[index]) {
            if (k == key) return true;
        }
        return false;
    }

    // 删除键（简单实现，只删第一个匹配的）
    void remove(int key) {
        int index = hashFunction(key);        // 计算桶索引
        table[index].remove(key);             // 调用 list 的 remove 方法
    }

    // 打印哈希表（调试用）
    void print() {
        for (int i = 0; i < size; ++i) {
            cout << "桶 " << i << ": ";
            for (int k : table[i]) {
                cout << k << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    HashTable ht(7);   // 创建一个大小为7的哈希表（7个桶）
    ht.insert(10);
    ht.insert(22);
    ht.insert(31);
    ht.insert(4);
    ht.insert(15);
    ht.insert(28);
    ht.insert(17);
    ht.insert(88);
    ht.insert(59);

    cout << "哈希表内容：" << endl;
    ht.print();

    cout << "\n查找 22: " << (ht.search(22) ? "找到" : "未找到") << endl;
    cout << "查找 100: " << (ht.search(100) ? "找到" : "未找到") << endl;

    ht.remove(22);
    cout << "\n删除 22 后查找 22: " << (ht.search(22) ? "找到" : "未找到") << endl;

    return 0;
}

代码关键点说明：

使用 vector<list<int>> 作为存储结构，每个 bucket 是一个 list<int>。
hashFunction 简单取模，如果 key 是负数需要调整（这里假设非负）。
插入、查找、删除都是先计算索引，然后操作对应的链表（list）。

Python 完整代码实现

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]  # 每个位置初始化为空列表（桶）

    def _hash(self, key):
        """哈希函数：取模"""
        return key % self.size

    def insert(self, key):
        """插入键"""
        index = self._hash(key)            # 计算桶索引
        # 如果键已存在，可以不重复插入（这里简单处理，允许重复）
        self.table[index].append(key)

    def search(self, key):
        """查找键是否存在"""
        index = self._hash(key)            # 计算桶索引
        return key in self.table[index]    # 利用列表的 in 操作符

    def remove(self, key):
        """删除键（只删第一个匹配的）"""
        index = self._hash(key)            # 计算桶索引
        if key in self.table[index]:
            self.table[index].remove(key)

    def print_table(self):
        """打印哈希表"""
        for i, bucket in enumerate(self.table):
            print(f"桶 {i}: {bucket}")


# 测试
ht = HashTable(7)
ht.insert(10)
ht.insert(22)
ht.insert(31)
ht.insert(4)
ht.insert(15)
ht.insert(28)
ht.insert(17)
ht.insert(88)
ht.insert(59)

print("哈希表内容：")
ht.print_table()

print("\n查找 22:", "找到" if ht.search(22) else "未找到")
print("查找 100:", "找到" if ht.search(100) else "未找到")

ht.remove(22)
print("\n删除 22 后查找 22:", "找到" if ht.search(22) else "未找到")

Python 版更简洁：直接用列表的列表，每个桶是一个 Python 列表（相当于动态数组）。

哈希表的特点总结

优点：在理想情况下（没有冲突或冲突很少），插入、查找、删除的时间复杂度都是 O(1) —— 常数时间，非常快！
缺点：占用空间可能较大（需要预分配数组）；哈希函数设计不好会导致大量冲突，性能下降；不能保持元素的顺序（无法像数组那样按索引遍历排序）。
核心概念：哈希函数、冲突、负载因子（已有元素个数 ÷ 表大小）、动态扩容。

负载因子与扩容：负载因子 = 元素总数 / 桶数量。如果负载因子太大（比如超过 0.75），冲突会变多，效率下降。此时需要“扩容”：创建一个更大的哈希表（通常是原大小的两倍），然后把所有数据重新插入（重新计算哈希），这个过程叫 Rehash。

新手常犯的错误

哈希函数设计太差：比如对所有 key 都用 key % 2，结果只有两个桶，所有数据挤在一起，哈希表退化成链表。
忽略负载因子：不扩容，导致链表越来越长，查找变成 O(n)。
删除时直接操作数组而不考虑链表中其他元素：链地址法里删除一个 key 后，必须有办法恢复其他元素的访问路径（用链表删除即可，但开放地址法要小心）。
使用可变对象作为键：如果键是可变的（比如列表），哈希值会在插入后改变，导致再也找不到。所以键通常是不可变的（整数、字符串、元组）。
对负数取模得到负数索引：取模结果可能为负数（在 C++ 中）。应确保索引在 0 ~ size-1 之间，通常使用 (key % size + size) % size。