第60章 哈希表

哈希表(Hash Table)，又称散列表，是一种通过哈希函数将键(Key)映射到值(Value)的高效数据结构。它能够在平均情况下实现$O(1)$时间复杂度的插入、删除和查找操作，是解决查找问题的最优选择之一。

60.1 哈希表的基本概念

60.1.1 核心定义

1. 哈希函数(Hash Function)：hash(key)=index，把键映射为数组下标。
2. 哈希表：底层是数组，数组每个位置称为桶(Bucket)，存放键值对。
3. 冲突(Collision)：两个不同的key经过哈希计算得到相同下标，即$key_1 \neq key_2$但$hash(key_1)=hash(key_2)$。

60.1.2 核心目标

1. 哈希函数尽可能均匀分布键，减少冲突；
2. 设计高效冲突解决方案，保证操作平均复杂度接近$O(1)$。

60.2 哈希函数的构造方法

60.2.1 直接定址法

公式：$hash(key)=a \times key + b$ 适用场景：键连续、数值范围小（如学号、年龄）。 示例：学号范围10002000，hash(学号)=学号-1000，映射到01000下标。

60.2.2 除留余数法

$hash(key) = key \bmod m$ 要求$m$取质数，降低冲突概率；是编程最常用哈希方法。 示例：$m=13$，$25 \bmod 13 = 12$，$38 \bmod 13 = 12$（产生冲突）。

60.2.3 数字分析法

选取数字分布均匀的片段作为哈希地址，适合固定长度数字（手机号后四位）。

60.4 折叠法

将数字分段求和，再对哈希表长度取模，处理超长数字。

60.2.5 字符串多项式哈希

$hash(s) = (s_0 \times P^{n-1} + s_1 \times P^{n-1} + ... + s_{n-1}) \bmod m$ $P$常用质数31、131，$s_i$为字符ASCII码。 示例：字符串abc，$P=31,m=100$。

60.3 冲突解决策略

60.3.1 开放地址法

冲突时向后探测空桶，通用探测公式： $hash_i(key) = (hash(key)+d_i) \bmod m$

1. 线性探测：$d_i = i$，依次向后查找，易产生数据聚集；
2. 二次探测：$d_i = \pm i^2$，分布更均匀；
3. 伪随机探测：$d_i$为固定随机序列。

60.3.2 链地址法（拉链法）

每个桶挂载链表，所有冲突键存入同一条链表。 优势：无聚集、扩容简单；劣势：链表占用额外内存。

60.3.3 两种方法对比

策略	优点	缺点	适用场景
开放地址法	无需额外链表内存	聚集、删除复杂	数据量固定、内存紧张
链地址法	冲突处理简单、易扩容	链表消耗空间	数据动态变化、冲突多

60.4 哈希表基础操作（链地址C++实现）

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

template <typename K, typename V>
class HashTable{
private:
    vector<list<pair<K, V>>> buckets;
    size_t capacity;
    size_t size;
    const double loadFactorThreshold = 0.7;

    // 简化哈希函数
    size_t hash (const K& key) const {
        return static_cast<size_t>(key) % capacity;
    }

    // 扩容重哈希
    void rehash(){
        size_t oldCap = capacity;
        capacity *= 2;
        vector<list<pair<K, V>>> newBuckets(capacity);
        for(size_t i = 0; i < oldCap; i++){
            for(auto& p : buckets[i]){
                size_t idx = hash(p.first);
                newBuckets[idx].push_back(p);
            }
        }
        buckets.swap(newBuckets);
    }
public:
    HashTable(size_t initialCapacity = 11): capacity(initialCapacity), size(0){
        buckets.resize(capacity);
    }

    // 插入/更新键值
    void insert(const K& key, const V& value){
        if((double)size / capacity >= loadFactorThreshold){
            rehash();
        }
        size_t idx = hash(key);
        for(auto& p : buckets[idx]){
            if(p.first == key){
                p.second = value;
                return;
            }
        }
        buckets[idx].emplace_back(key, value);
        size++;
    }

    // 查找，返回是否存在
    bool find(const K& key, V& value) const {
        size_t idx = hash(key);
        for(const auto& p : buckets[idx]){
            if(p.first == key){
                value = p.second;
                return true;
            }
        }
        return false;
    }

    // 删除键
    bool erase(const K& key){
        size_t idx = hash(key);
        for(auto it = buckets[idx].begin(); it != buckets[idx].end(); ++it){
            if(it->first == key){
                buckets[idx].erase(it);
                size--;
                return true;
            }
        }
        return false;
    }
};

60.5 哈希表性能分析

60.5.1 负载因子

$负载因子 = 元素总数 \div 哈希表容量$ 负载越大冲突越多，通常阈值设0.7，超过自动扩容。

60.5.2 时间复杂度

• 平均情况：插入/查找/删除 $O(1)$；
• 最坏情况：全部哈希到同一桶，退化为链表 $O(n)$。

60.5.3 空间复杂度

链地址法：$O(m+n)$，$m$为桶数量，$n$存储元素。

60.6 C++标准哈希容器

60.6.1 unordered_map / unordered_set

1. unordered_map<Key,T>：键值对，键唯一；
2. unordered_set<T>：仅存储唯一元素； 底层采用链地址法，元素无序，平均$O(1)$操作。

60.6.2 使用示例

#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;

int main(){
    // unordered_map示例
    unordered_map<string, int> score;
    score["Alice"] = 90;
    score.insert({"Bob", 85});
    if(score.find("Alice") != score.end()){
        cout << "Alice:" << score["Alice"] << endl;
    }
    score.erase("Bob");

    // unordered_set示例
    unordered_set<int> nums = {1,2,3};
    nums.insert(4);
    if(nums.count(2)){
        cout << "包含数字2" << endl;
    }
    return 0;
}