《算法导论》第 11 章 - 散列表

啊阿狸不会拉杆

发布于 2026-01-21 13:23:26

1160

大家好！今天我们来深入学习《算法导论》第 11 章 —— 散列表（Hash Table）。散列表是一种非常高效的数据结构，能够在平均情况下实现 O (1) 时间复杂度的插入、删除和查找操作，因此在实际应用中被广泛使用，比如数据库索引、缓存系统、哈希映射等。

本文将按照原书的章节结构，结合代码实现，为大家详细讲解散列表的相关知识。每个知识点都会配有完整的 C++ 代码示例，确保大家可以动手实践。

思维导图

11.1 直接寻址表

原理

直接寻址表是一种简单的数据结构，当关键字的全域 U 比较小时，我们可以用一个数组（称为直接寻址表）来表示动态集合。数组的下标对应关键字，数组中的每个元素存储该关键字对应的卫星数据。

若关键字 k 属于动态集合，则直接寻址表 T [k] 中存储指向该元素的指针；
若关键字 k 不属于动态集合，则 T [k] 为 NULL。

代码实现

下面是直接寻址表的 C++ 实现，包含插入、删除和查找操作：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 定义元素结构，包含关键字和卫星数据
struct Element {
    int key;         // 关键字
    string data;     // 卫星数据
    Element(int k, string d) : key(k), data(d) {}
};

// 直接寻址表类
class DirectAddressTable {
private:
    vector<Element*> table;  // 直接寻址表数组
    int size;                // 表的大小

public:
    // 构造函数，初始化表大小
    DirectAddressTable(int n) : size(n) {
        table.resize(n, nullptr);  // 初始化为空指针
    }

    // 析构函数，释放内存
    ~DirectAddressTable() {
        for (auto& elem : table) {
            if (elem != nullptr) {
                delete elem;
                elem = nullptr;
            }
        }
    }

    // 插入操作：将关键字为key的元素插入表中
    bool insert(int key, const string& data) {
        // 检查关键字是否在有效范围内
        if (key < 0 || key >= size) {
            cerr << "关键字超出范围！" << endl;
            return false;
        }
        // 检查该位置是否已存在元素
        if (table[key] != nullptr) {
            cerr << "关键字 " << key << " 已存在！" << endl;
            return false;
        }
        // 插入新元素
        table[key] = new Element(key, data);
        return true;
    }

    // 删除操作：删除关键字为key的元素
    bool remove(int key) {
        if (key < 0 || key >= size) {
            cerr << "关键字超出范围！" << endl;
            return false;
        }
        if (table[key] == nullptr) {
            cerr << "关键字 " << key << " 不存在！" << endl;
            return false;
        }
        // 删除元素并置空
        delete table[key];
        table[key] = nullptr;
        return true;
    }

    // 查找操作：查找关键字为key的元素
    Element* search(int key) {
        if (key < 0 || key >= size) {
            cerr << "关键字超出范围！" << endl;
            return nullptr;
        }
        return table[key];  // 若不存在则返回nullptr
    }

    // 打印表中所有元素
    void print() {
        cout << "直接寻址表内容：" << endl;
        for (int i = 0; i < size; ++i) {
            if (table[i] != nullptr) {
                cout << "位置 " << i << ": 关键字=" << table[i]->key 
                     << ", 数据=" << table[i]->data << endl;
            }
        }
    }
};

// 示例用法
int main() {
    // 创建一个大小为10的直接寻址表
    DirectAddressTable dat(10);

    // 插入元素
    dat.insert(3, "苹果");
    dat.insert(7, "香蕉");
    dat.insert(2, "橙子");

    // 打印表内容
    dat.print();

    // 查找元素
    Element* elem = dat.search(7);
    if (elem != nullptr) {
        cout << "找到元素：关键字=" << elem->key << ", 数据=" << elem->data << endl;
    }

    // 删除元素
    dat.remove(3);
    cout << "删除关键字3后：" << endl;
    dat.print();

    // 尝试插入重复关键字
    dat.insert(7, "葡萄");  // 会报错

    return 0;
}

直接寻址表的优缺点

优点：
- 实现简单，插入和删除操作时间复杂度为 O (1)
- 查找操作在关键字存在时时间复杂度为 O (1)
缺点：
- 当关键字全域 U 很大时（如 U=10^9），存储空间开销巨大
- 关键字分布稀疏时，空间利用率极低
- 只能处理整数关键字（非整数关键字需要先映射为整数）

适用场景

直接寻址表适用于关键字全域 U 较小且密集的情况，例如：

月份（1-12）、星期（1-7）等范围有限的整数标识
某些内部状态码、错误码的映射

当关键字全域很大时，我们就需要使用散列表来节省空间。

11.2 散列表

原理

散列表（Hash Table）通过一个散列函数（Hash Function）h 将关键字 k 映射到散列表 T 中的位置 h (k)。这里的 h (k) 称为关键字 k 的散列值。

散列表的大小 m 通常远小于关键字全域 U 的大小，因此多个关键字可能被映射到同一个散列值，这种现象称为冲突（Collision）。如何处理冲突是散列表设计的核心问题。

散列表的基本结构

关键字全域 U (很大)
    ↓ 散列函数 h
散列表 T [0...m-1] (大小为m)

负载因子

散列表的负载因子（Load Factor） α 定义为： α = n /m 其中 n 是散列表中已存储的元素数量，m 是散列表的大小。

负载因子是衡量散列表拥挤程度的指标，α 越小，冲突的可能性越低；α 越大，冲突的可能性越高。

冲突解决方法

《算法导论》中介绍了两种主要的冲突解决方法：

链地址法（Chaining）：将具有相同散列值的元素存储在同一个链表中
开放寻址法（Open Addressing）：所有元素都存储在散列表本身中，当发生冲突时，通过某种探测技术寻找下一个空位置

接下来我们先实现基于链地址法的散列表。

链地址法散列表的代码实现

#include <iostream>
#include <vector>
#include <list>
#include <string>

using namespace std;

// 定义元素结构
struct HashNode {
    int key;         // 关键字
    string value;    // 数据值
    HashNode(int k, const string& v) : key(k), value(v) {}
};

// 基于链地址法的散列表类
class HashTableChaining {
private:
    vector<list<HashNode>> table;  // 散列表，每个位置是一个链表
    int m;                          // 散列表大小
    int n;                          // 当前元素数量

    // 散列函数：这里使用简单的除法散列法
    int hash(int key) const {
        // 确保散列值为非负数
        return (key % m + m) % m;
    }

public:
    // 构造函数，指定散列表大小
    HashTableChaining(int size) : m(size), n(0) {
        table.resize(m);
    }

    // 插入操作：插入关键字为key，值为value的元素
    void insert(int key, const string& value) {
        int index = hash(key);
        // 检查是否已存在该关键字（可选操作，根据需求决定是否允许重复）
        for (const auto& node : table[index]) {
            if (node.key == key) {
                cerr << "关键字 " << key << " 已存在，无法插入！" << endl;
                return;
            }
        }
        // 插入到链表头部
        table[index].emplace_front(key, value);
        n++;
    }

    // 查找操作：查找关键字为key的元素，返回其值
    string search(int key) const {
        int index = hash(key);
        for (const auto& node : table[index]) {
            if (node.key == key) {
                return node.value;  // 找到，返回值
            }
        }
        return "";  // 未找到，返回空字符串
    }

    // 删除操作：删除关键字为key的元素
    bool remove(int key) {
        int index = hash(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->key == key) {
                table[index].erase(it);  // 删除该元素
                n--;
                return true;  // 删除成功
            }
        }
        return false;  // 未找到该元素，删除失败
    }

    // 获取当前负载因子
    double loadFactor() const {
        return static_cast<double>(n) / m;
    }

    // 打印散列表内容
    void print() const {
        cout << "散列表内容（大小=" << m << ", 元素数量=" << n << ", 负载因子=" << loadFactor() << "）：" << endl;
        for (int i = 0; i < m; ++i) {
            if (!table[i].empty()) {
                cout << "索引 " << i << ": ";
                for (const auto& node : table[i]) {
                    cout << "(" << node.key << ", " << node.value << ") -> ";
                }
                cout << "NULL" << endl;
            }
        }
    }
};

// 示例用法
int main() {
    // 创建一个大小为7的散列表
    HashTableChaining ht(7);

    // 插入元素
    ht.insert(10, "苹果");
    ht.insert(20, "香蕉");
    ht.insert(30, "橙子");
    ht.insert(1, "葡萄");
    ht.insert(8, "西瓜");  // 10和8模7都为3，会产生冲突
    ht.insert(15, "草莓");
    ht.insert(22, "樱桃"); // 22模7为1，与15模7相同（15%7=1）

    // 打印散列表
    ht.print();

    // 查找元素
    string val = ht.search(8);
    if (!val.empty()) {
        cout << "查找关键字8: " << val << endl;
    } else {
        cout << "未找到关键字8" << endl;
    }

    // 删除元素
    bool removed = ht.remove(20);
    if (removed) {
        cout << "删除关键字20成功" << endl;
    } else {
        cout << "删除关键字20失败" << endl;
    }

    // 打印删除后的散列表
    ht.print();

    return 0;
}

链地址法的性能分析

在链地址法中，散列表操作的平均时间取决于链表的长度。

若散列函数是均匀的，则每个链表的期望长度为 α = n/m
插入操作：O (1)（在链表头部插入）
查找和删除操作：O (1 + α)（需要遍历链表）

当 α = O (1) 时（即 m = Θ(n)），所有操作的平均时间复杂度为 O (1)。

11.3 散列函数

散列函数 h 将关键字全域 U 映射到散列表的索引 {0, 1, ..., m-1}。一个好的散列函数应尽可能避免冲突，使关键字均匀分布在散列表中。

11.3.1 除法散列法

除法散列法是最简单的散列函数之一，它通过取关键字 k 除以 m 的余数来得到散列值：

h(k) = k mod m

选择 m 的注意事项：

不应选择 m 为 2 的幂，因为此时 h (k) 仅取决于 k 的最低 log2m 位
通常选择 m 为一个不太接近 2 的幂的质数，这样可以使关键字的分布更均匀

代码实现（除法散列法）：

// 除法散列法
int divisionHash(int key, int m) {
    // 确保结果为非负数
    return (key % m + m) % m;
}

11.3.2 乘法散列法

乘法散列法的步骤：

用关键字 k 乘上常数 A（0 < A < 1），提取 k*A 的小数部分
用这个小数部分乘以 m，取结果的整数部分

公式：h (k) = floor (m * (k * A mod 1))

其中 "k * A mod 1" 表示取 kA 的小数部分，即 kA - floor(k*A)。

常数 A 的选择：

最优的 A 值约为 (√5 - 1)/2 ≈ 0.6180339887...，这是黄金分割比例的倒数。

代码实现（乘法散列法）：

// 乘法散列法
int multiplicationHash(int key, int m) {
    const double A = (sqrt(5) - 1) / 2;  // 黄金分割比例的倒数
    double fractional = key * A - floor(key * A);  // 取小数部分
    return static_cast<int>(floor(m * fractional));
}

11.3.3 全域散列法

全域散列法通过随机选择散列函数，来防止最坏情况的发生（例如恶意选择的关键字）。

一个散列函数全域 H 是一组散列函数，其中每个函数 h 将关键字全域 U 映射到 {0, 1, ..., m-1}。

全域散列法的定义：对于任意两个不同的关键字 k 和 l，满足 h (k) = h (l) 的散列函数 h 在 H 中的数量至多为 | H|/m。

一种简单的全域散列函数构造：

设 m 是一个质数，定义散列函数：

h_{a,b}(k) = ((a*k + b) mod m)，其中 a ∈ {1, 2, ..., m-1}，b ∈ {0, 1, ..., m-1}

这样的函数集合 H = {h_{a,b} | 1 ≤ a ≤ m-1, 0 ≤ b ≤ m-1} 是一个全域散列函数集合。

代码实现（全域散列法）：

#include <cstdlib>
#include <ctime>

// 全域散列法：初始化a和b
void initUniversalHash(int& a, int& b, int m) {
    srand(time(0));  // 随机数种子
    a = rand() % (m - 1) + 1;  // a ∈ [1, m-1]
    b = rand() % m;            // b ∈ [0, m-1]
}

// 全域散列函数
int universalHash(int key, int a, int b, int m) {
    return ((a * key + b) % m + m) % m;
}

不同散列函数的对比示例

下面是一个综合示例，展示了三种散列函数对同一组关键字的映射结果：

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

// 除法散列法
int divisionHash(int key, int m) {
    return (key % m + m) % m;
}

// 乘法散列法
int multiplicationHash(int key, int m) {
    const double A = (sqrt(5) - 1) / 2;  // 黄金分割比例的倒数
    double fractional = key * A - floor(key * A);  // 取小数部分
    return static_cast<int>(floor(m * fractional));
}

// 全域散列法
int universalHash(int key, int a, int b, int m) {
    return ((a * key + b) % m + m) % m;
}

int main() {
    int m = 11;  // 散列表大小（选择一个质数）
    vector<int> keys = {10, 20, 30, 1, 8, 15, 22, 35, 47, 12};  // 测试关键字
    
    // 初始化全域散列的a和b
    srand(time(0));
    int a = rand() % (m - 1) + 1;  // a ∈ [1, m-1]
    int b = rand() % m;            // b ∈ [0, m-1]
    
    // 输出三种散列函数的映射结果
    cout << "散列表大小 m = " << m << endl;
    cout << "全域散列参数 a = " << a << ", b = " << b << endl;
    cout << "关键字\t除法散列\t乘法散列\t全域散列" << endl;
    cout << "-----------------------------------------" << endl;
    
    for (int key : keys) {
        int h1 = divisionHash(key, m);
        int h2 = multiplicationHash(key, m);
        int h3 = universalHash(key, a, b, m);
        cout << key << "\t" << h1 << "\t\t" << h2 << "\t\t" << h3 << endl;
    }
    
    return 0;
}

运行结果可能如下（全域散列的结果每次运行可能不同）：

从结果可以看出，不同的散列函数对相同的关键字会产生不同的散列值。在实际应用中，应根据关键字的特点选择合适的散列函数。

11.4 开放寻址法

开放寻址法是另一种解决冲突的方法，它不使用链表，所有元素都直接存储在散列表中。当发生冲突时，通过探测（Probing） 技术寻找下一个空位置。

开放寻址法的散列表查找、插入和删除操作都需要探测序列。对于关键字 k，探测序列是一个散列表索引序列 h (k, 0), h (k, 1), ..., h (k, m-1)，其中 h (k, i) 是第 i 次探测的位置。

开放寻址法的基本思想

插入元素时，按照探测序列依次检查散列表中的位置，直到找到一个空位置
查找元素时，按照同样的探测序列依次检查，直到找到该元素或遇到空位置
删除元素时，不能简单地将位置置空（会影响其他元素的查找），通常需要标记为 "已删除"

三种常见的探测方法

1. 线性探测

线性探测的探测序列为： h (k, i) = (h'(k) + i) mod m, 其中 i = 0, 1, ..., m-1

h'(k) 是一个辅助散列函数，通常是除法散列或乘法散列。

缺点：容易产生一次聚集（Primary Clustering），即连续被占用的位置会形成块，导致探测序列变长。

2. 二次探测

二次探测的探测序列为： h (k, i) = (h'(k) + c1i + c2i²) mod m, 其中 i = 0, 1, ..., m-1

c1 和 c2 是正的常数。《算法导论》中使用的形式是： h (k, i) = (h'(k) + i + i²/2) mod m

缺点：可能产生二次聚集（Secondary Clustering），即具有相同 h'(k) 的关键字会有相同的探测序列。

3. 双重散列

双重散列使用两个散列函数 h1 和 h2，探测序列为： h (k, i) = (h1 (k) + i*h2 (k)) mod m, 其中 i = 0, 1, ..., m-1

h2 (k) 必须满足：h2 (k) ≠ 0 mod m，以保证探测序列能覆盖整个散列表。

优点：能避免聚集问题，是开放寻址法中性能最好的探测方法之一。

开放寻址法散列表的代码实现（双重散列）

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

// 散列表的三种状态
enum State {
    EMPTY,      // 空位置
    OCCUPIED,   // 已占用
    DELETED     // 已删除
};

// 开放寻址法散列表的元素结构
struct HashEntry {
    int key;         // 关键字
    string value;    // 数据值
    State state;     // 状态

    HashEntry() : key(0), value(""), state(EMPTY) {}
    HashEntry(int k, const string& v) : key(k), value(v), state(OCCUPIED) {}
};

// 开放寻址法散列表类（使用双重散列）
class HashTableOpenAddressing {
private:
    vector<HashEntry> table;  // 散列表
    int m;                    // 散列表大小
    int n;                    // 当前元素数量

    // 第一个散列函数 h1(k) = k mod m（确保m是质数）
    int h1(int key) const {
        return (key % m + m) % m;
    }

    // 第二个散列函数 h2(k) = 1 + (k mod (m-2))（确保h2(k) ≠ 0）
    int h2(int key) const {
        return 1 + ((key % (m - 2) + (m - 2)) % (m - 2));
    }

    // 双重散列的探测函数
    int probe(int key, int i) const {
        return (h1(key) + i * h2(key)) % m;
    }

public:
    // 构造函数，指定散列表大小（最好是质数）
    HashTableOpenAddressing(int size) : m(size), n(0) {
        table.resize(m);
    }

    // 插入操作：插入关键字为key，值为value的元素
    bool insert(int key, const string& value) {
        // 散列表已满
        if (n == m) {
            cerr << "散列表已满，无法插入！" << endl;
            return false;
        }

        int i = 0;
        while (true) {
            int index = probe(key, i);
            // 找到空位置或已删除的位置
            if (table[index].state == EMPTY || table[index].state == DELETED) {
                table[index] = HashEntry(key, value);
                n++;
                return true;
            }
            // 已存在该关键字
            if (table[index].state == OCCUPIED && table[index].key == key) {
                cerr << "关键字 " << key << " 已存在，无法插入！" << endl;
                return false;
            }
            i++;
            // 理论上不会到达这里，因为n < m
        }
    }

    // 查找操作：查找关键字为key的元素，返回其值
    string search(int key) const {
        int i = 0;
        while (true) {
            int index = probe(key, i);
            // 找到空位置，说明不存在该关键字
            if (table[index].state == EMPTY) {
                return "";
            }
            // 找到该关键字
            if (table[index].state == OCCUPIED && table[index].key == key) {
                return table[index].value;
            }
            i++;
            // 探测了m次仍未找到，说明不存在
            if (i == m) {
                return "";
            }
        }
    }

    // 删除操作：删除关键字为key的元素
    bool remove(int key) {
        int i = 0;
        while (true) {
            int index = probe(key, i);
            // 找到空位置，说明不存在该关键字
            if (table[index].state == EMPTY) {
                return false;
            }
            // 找到该关键字，标记为已删除
            if (table[index].state == OCCUPIED && table[index].key == key) {
                table[index].state = DELETED;
                n--;
                return true;
            }
            i++;
            // 探测了m次仍未找到，说明不存在
            if (i == m) {
                return false;
            }
        }
    }

    // 获取当前负载因子
    double loadFactor() const {
        return static_cast<double>(n) / m;
    }

    // 打印散列表内容
    void print() const {
        cout << "开放寻址法散列表内容（大小=" << m << ", 元素数量=" << n << ", 负载因子=" << loadFactor() << "）：" << endl;
        for (int i = 0; i < m; ++i) {
            cout << "索引 " << i << ": ";
            if (table[i].state == OCCUPIED) {
                cout << "关键字=" << table[i].key << ", 数据=" << table[i].value;
            } else if (table[i].state == DELETED) {
                cout << "已删除";
            } else {
                cout << "空";
            }
            cout << endl;
        }
    }
};

// 示例用法
int main() {
    // 创建一个大小为11（质数）的开放寻址法散列表
    HashTableOpenAddressing ht(11);

    // 插入元素
    ht.insert(10, "苹果");
    ht.insert(20, "香蕉");
    ht.insert(30, "橙子");
    ht.insert(1, "葡萄");
    ht.insert(8, "西瓜");  // 会与10冲突（h1(10)=10, h1(8)=8，可能不冲突，取决于具体数值）
    ht.insert(15, "草莓");
    ht.insert(22, "樱桃");
    ht.insert(35, "芒果");
    ht.insert(47, "菠萝");

    // 打印散列表
    ht.print();

    // 查找元素
    string val = ht.search(8);
    if (!val.empty()) {
        cout << "查找关键字8: " << val << endl;
    } else {
        cout << "未找到关键字8" << endl;
    }

    // 删除元素
    bool removed = ht.remove(20);
    if (removed) {
        cout << "删除关键字20成功" << endl;
    } else {
        cout << "删除关键字20失败" << endl;
    }

    // 尝试插入被删除位置的元素
    ht.insert(55, "猕猴桃");

    // 打印修改后的散列表
    ht.print();

    return 0;
}

开放寻址法的性能分析

开放寻址法的性能受负载因子 α = n/m 的影响很大：

当 α 较小时（如 α = 0.5），查找的期望探测次数约为 2
当 α 接近 1 时，查找的期望探测次数会急剧增加
实际应用中，开放寻址法的散列表通常将 α 控制在 0.5 ~ 0.7 之间

对于成功查找和不成功查找，期望探测次数分别为：

成功查找：(1/α) * ln (1/(1-α))
不成功查找：1/(1-α)

11.5 完全散列

完全散列（Perfect Hashing）是一种两级散列方法，能够在 O (1) 的最坏情况下完成查找操作。

原理

完全散列使用两级散列：

第一级：使用一个全域散列函数 h 将 n 个关键字散列到 m 个槽中
第二级：对于每个槽 j，如果槽 j 中有 nj 个关键字，则为该槽分配一个大小为 nj² 的二级散列表 Sj，并使用一个全域散列函数 hj 将这些关键字散列到 Sj 中

通过这种两级结构，完全散列可以保证在最坏情况下也没有冲突，从而实现 O (1) 的查找时间。

完全散列的结构示意图

一级散列表 T [0...m-1]
    |
    |-- 槽0: 包含n0个关键字 -> 二级散列表 S0 [0...n0²-1]
    |-- 槽1: 包含n1个关键字 -> 二级散列表 S1 [0...n1²-1]
    |-- ...
    |-- 槽m-1: 包含nm-1个关键字 -> 二级散列表 Sm-1 [0...nm-1²-1]

完全散列的代码实现（简化版）

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

// 二级散列表的槽状态
enum SlotState {
    SLOT_EMPTY,
    SLOT_OCCUPIED
};

// 二级散列表的元素
struct SecondaryEntry {
    int key;
    string value;
    SlotState state;

    SecondaryEntry() : key(0), value(""), state(SLOT_EMPTY) {}
    SecondaryEntry(int k, const string& v) : key(k), value(v), state(SLOT_OCCUPIED) {}
};

// 二级散列表
class SecondaryHashTable {
private:
    vector<SecondaryEntry> table;
    int size;  // 大小为n²，n是关键字数量
    int a, b;  // 全域散列参数

    // 全域散列函数
    int hash(int key) const {
        return ((a * key + b) % size + size) % size;
    }

public:
    // 构造函数，传入关键字集合
    SecondaryHashTable(const vector<pair<int, string>>& entries) {
        int n = entries.size();
        if (n == 0) {
            size = 0;
            return;
        }

        size = n * n;  // 二级散列表大小为n²

        // 随机选择全域散列参数，直到没有冲突
        bool hasCollision;
        srand(time(0));
        
        do {
            hasCollision = false;
            table.assign(size, SecondaryEntry());
            
            // 随机选择a和b（a ∈ [1, size-1], b ∈ [0, size-1]）
            if (size > 1) {
                a = rand() % (size - 1) + 1;
            } else {
                a = 1;
            }
            b = rand() % size;

            // 插入所有关键字
            for (const auto& entry : entries) {
                int key = entry.first;
                const string& value = entry.second;
                int index = hash(key);
                
                // 检查冲突
                if (table[index].state == SLOT_OCCUPIED) {
                    hasCollision = true;
                    break;
                }
                table[index] = SecondaryEntry(key, value);
            }
        } while (hasCollision);  // 有冲突则重新选择散列参数
    }

    // 查找关键字
    string search(int key) const {
        if (size == 0) return "";
        
        int index = hash(key);
        if (table[index].state == SLOT_OCCUPIED && table[index].key == key) {
            return table[index].value;
        }
        return "";  // 未找到
    }

    // 获取大小
    int getSize() const {
        return size;
    }
};

// 完全散列（一级散列表）
class PerfectHashTable {
private:
    vector<SecondaryHashTable*> secondaryTables;
    int m;  // 一级散列表大小（通常取n）
    int a, b;  // 一级散列参数

    // 一级散列函数
    int hash(int key) const {
        return ((a * key + b) % m + m) % m;
    }

public:
    // 构造函数，传入所有关键字
    PerfectHashTable(const vector<pair<int, string>>& entries) {
        int n = entries.size();
        if (n == 0) {
            m = 0;
            return;
        }

        m = n;  // 一级散列表大小为n
        secondaryTables.resize(m, nullptr);

        // 第一步：使用全域散列将关键字分配到一级散列表的槽中
        vector<vector<pair<int, string>>> slots(m);
        srand(time(0));
        
        // 随机选择一级散列参数
        if (m > 1) {
            a = rand() % (m - 1) + 1;
        } else {
            a = 1;
        }
        b = rand() % m;

        // 分配关键字到各个槽
        for (const auto& entry : entries) {
            int key = entry.first;
            int index = hash(key);
            slots[index].push_back(entry);
        }

        // 第二步：为每个槽创建二级散列表
        for (int i = 0; i < m; ++i) {
            if (!slots[i].empty()) {
                secondaryTables[i] = new SecondaryHashTable(slots[i]);
            } else {
                secondaryTables[i] = nullptr;
            }
        }
    }

    // 析构函数
    ~PerfectHashTable() {
        for (auto st : secondaryTables) {
            if (st != nullptr) {
                delete st;
            }
        }
    }

    // 查找关键字
    string search(int key) const {
        if (m == 0) return "";
        
        int index = hash(key);
        if (secondaryTables[index] == nullptr) {
            return "";
        }
        return secondaryTables[index]->search(key);
    }

    // 打印散列表信息
    void printInfo() const {
        if (m == 0) {
            cout << "完全散列为空" << endl;
            return;
        }
        
        cout << "完全散列信息：" << endl;
        cout << "一级散列表大小: " << m << endl;
        cout << "一级散列参数 a = " << a << ", b = " << b << endl;
        
        for (int i = 0; i < m; ++i) {
            if (secondaryTables[i] != nullptr) {
                cout << "槽 " << i << " 的二级散列表大小: " << secondaryTables[i]->getSize() << endl;
            }
        }
    }
};

// 示例用法
int main() {
    // 测试数据
    vector<pair<int, string>> entries = {
        {10, "苹果"}, {20, "香蕉"}, {30, "橙子"},
        {1, "葡萄"}, {8, "西瓜"}, {15, "草莓"},
        {22, "樱桃"}, {35, "芒果"}, {47, "菠萝"}
    };

    // 创建完全散列
    PerfectHashTable pht(entries);
    pht.printInfo();

    // 查找测试
    vector<int> testKeys = {10, 20, 35, 99, 1};
    for (int key : testKeys) {
        string val = pht.search(key);
        if (!val.empty()) {
            cout << "查找关键字 " << key << ": " << val << endl;
        } else {
            cout << "未找到关键字 " << key << endl;
        }
    }

    return 0;
}

完全散列的性能分析

空间复杂度：期望空间复杂度为 O (n)，因为二级散列表的总大小为 Σnj²，其期望值为 O (n)
查找时间：最坏情况下为 O (1)，因为保证了没有冲突
预处理时间：可能较长，因为需要为每个二级散列表找到无冲突的散列函数

完全散列适用于关键字集合静态（即不经常变动）且需要频繁查找的场景，例如某些数据库的静态索引。

综合案例：使用散列表统计词频

下面我们使用散列表（链地址法）来实现一个词频统计工具，统计一段文本中每个单词出现的次数。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <cctype>
#include <algorithm>

using namespace std;

// 词频统计项
struct WordCount {
    string word;    // 单词
    int count;      // 出现次数
    WordCount(const string& w) : word(w), count(1) {}
};

// 词频统计散列表
class WordFrequencyHashTable {
private:
    vector<list<WordCount>> table;  // 链地址法散列表
    int m;                          // 散列表大小

    // 字符串散列函数（将字符串转换为整数再进行散列）
    int hash(const string& word) const {
        int hashValue = 0;
        // 简单的字符串散列算法
        for (char c : word) {
            hashValue = 37 * hashValue + c;
        }
        // 确保散列值在有效范围内
        return (hashValue % m + m) % m;
    }

public:
    // 构造函数
    WordFrequencyHashTable(int size) : m(size) {
        table.resize(m);
    }

    // 插入单词，若已存在则计数加1
    void insert(const string& word) {
        int index = hash(word);
        // 查找单词是否已存在
        for (auto& wc : table[index]) {
            if (wc.word == word) {
                wc.count++;  // 已存在，计数加1
                return;
            }
        }
        // 不存在，插入新单词
        table[index].emplace_back(word);
    }

    // 获取单词出现次数
    int getCount(const string& word) const {
        int index = hash(word);
        for (const auto& wc : table[index]) {
            if (wc.word == word) {
                return wc.count;
            }
        }
        return 0;  // 未找到
    }

    // 打印所有单词及其出现次数
    void printAll() const {
        for (const auto& bucket : table) {
            for (const auto& wc : bucket) {
                cout << wc.word << ": " << wc.count << "次" << endl;
            }
        }
    }

    // 获取所有单词及其出现次数
    vector<pair<string, int>> getAllWords() const {
        vector<pair<string, int>> result;
        for (const auto& bucket : table) {
            for (const auto& wc : bucket) {
                result.emplace_back(wc.word, wc.count);
            }
        }
        // 按出现次数降序排序
        sort(result.begin(), result.end(),
             [](const pair<string, int>& a, const pair<string, int>& b) {
                 return a.second > b.second;
             });
        return result;
    }
};

// 预处理单词：转换为小写，去除非字母字符
string processWord(const string& word) {
    string processed;
    for (char c : word) {
        if (isalpha(c)) {  // 只保留字母
            processed += tolower(c);  // 转换为小写
        }
    }
    return processed;
}

// 统计文本文件中的词频
void countWordFrequency(const string& filename) {
    ifstream file(filename);
    if (!file.is_open()) {
        cerr << "无法打开文件: " << filename << endl;
        return;
    }

    // 创建散列表（大小为1009，一个质数）
    WordFrequencyHashTable wfht(1009);
    string word;

    // 读取文件中的单词
    while (file >> word) {
        string processed = processWord(word);
        if (!processed.empty()) {  // 忽略空字符串
            wfht.insert(processed);
        }
    }

    file.close();

    // 获取并打印结果
    vector<pair<string, int>> words = wfht.getAllWords();
    cout << "词频统计结果（按出现次数降序）：" << endl;
    for (const auto& p : words) {
        cout << p.first << ": " << p.second << "次" << endl;
    }
}

int main() {
    // 统计当前目录下的test.txt文件的词频
    countWordFrequency("test.txt");
    return 0;
}

使用说明：

在程序同目录下创建一个 test.txt 文件，写入一些文本内容
运行程序，将统计该文本中每个单词的出现次数，并按出现次数降序排列输出

这个案例展示了散列表在实际应用中的价值：通过高效的插入和查找操作，能够快速统计大量数据中元素的出现频率。

思考题

比较链地址法和开放寻址法的优缺点，在什么情况下应该选择哪种方法？
为什么在除法散列法中，通常选择 m 为质数？如果 m 是 2 的幂，会有什么问题？
开放寻址法中，为什么删除元素时不能简单地将位置置空，而要标记为 "已删除"？
完全散列能够保证 O (1) 的最坏情况查找时间，但其构造过程可能需要较长时间，你认为完全散列适用于哪些场景？
设计一个散列函数，用于处理字符串关键字，使其能够均匀分布在散列表中。

本章注记

散列表是计算机科学中最实用的数据结构之一，在编译器、数据库、缓存系统等领域有广泛应用
散列函数的选择对散列表性能至关重要，实际应用中需要根据关键字的特点选择合适的散列函数
负载因子是影响散列表性能的关键参数，需要根据具体应用场景合理设置
除了本章介绍的方法外，还有许多高级的散列技术，如布谷鸟散列（Cuckoo Hashing）、跳房子散列（Hopscotch Hashing）等，这些方法在某些场景下能提供更好的性能
在 Java 的 HashMap、Python 的 dict 等语言内置的数据结构中，都使用了散列表作为底层实现