散列表（哈希表，Hash Table）介绍

散列表（Hash Table）是一种 基于哈希函数（Hash Function） 实现的 键值对（key-value）存储结构，支持 O(1) 级别的查找、插入和删除 操作，广泛用于 数据库索引、缓存系统、集合操作 等。

1. 为什么需要散列表？

(1) 线性查找 vs. 二分查找 vs. 平衡二叉树

数据结构	查找	插入	删除	适用场景
数组（无序）	O(n)	O(1)	O(n)	小规模数据
数组（有序）+ 二分查找	O(log n)	O(n)	O(n)	静态数据
平衡二叉树（AVL/红黑树）	O(log n)	O(log n)	O(log n)	动态数据
散列表（Hash Table）	O(1)	O(1)	O(1)	快速查找

总结：

二叉搜索树（BST）适用于区间查找、排序查询。
哈希表适用于快速查找，不要求顺序存储。

2. 散列表的基本原理

核心思想：

哈希函数（Hash Function）：将 key 映射到 哈希值（哈希桶索引）。
冲突解决（Collision Resolution）：
- 拉链法（Separate Chaining）
- 开放地址法（Open Addressing）
动态扩容（Resizing）：
- 负载因子（Load Factor） 超过阈值（如 0.75），进行 扩容（rehashing）。

3. 哈希函数

哈希函数的作用是将 任意大小的 key 映射到固定范围的索引。

(1) 常见哈希函数

除留余数法（Modulo Method）：

int hash(int key, int size) {
    return key % size;
}

乘法散列法（Multiplication Method）：

int hash(int key, int size) {
    double A = 0.6180339887; // 黄金比例
    return (int)(size * (key * A - (int)(key * A)));
}

字符串哈希（BKDRHash）：

unsigned int BKDRHash(string str) {
    unsigned int seed = 131; // 31, 131, 1313...
    unsigned int hash = 0;
    for (char ch : str) {
        hash = hash * seed + ch;
    }
    return hash;
}

4. 哈希冲突解决方案

(1) 拉链法（Separate Chaining）

思路：每个哈希桶存储一个链表，发生冲突时，将新元素插入链表中。
优点：避免哈希表扩容，适用于大规模数据。
缺点：链表查找最坏 O(n)。

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

using namespace std;

class HashTable {
private:
    vector<list<int>> table;
    int size;

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

public:
    HashTable(int s) : size(s) {
        table.resize(size);
    }

    void insert(int key) {
        int index = hash(key);
        table[index].push_back(key);
    }

    bool search(int key) {
        int index = hash(key);
        for (int num : table[index]) {
            if (num == key) return true;
        }
        return false;
    }
};

int main() {
    HashTable ht(10);
    ht.insert(15);
    ht.insert(25);
    cout << ht.search(15) << endl; // 输出 1
    cout << ht.search(20) << endl; // 输出 0
}

(2) 开放地址法（Open Addressing）

思路：若发生冲突，则寻找 下一个空位（线性探测/二次探测/双重哈希）。
优点：节省空间，无需额外链表。
缺点：删除困难（可能需要懒惰删除）。

#include <iostream>
#include <vector>

using namespace std;

class OpenAddressingHashTable {
private:
    vector<int> table;
    int size;
    int EMPTY = -1;

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

public:
    OpenAddressingHashTable(int s) : size(s) {
        table.resize(size, EMPTY);
    }

    void insert(int key) {
        int index = hash(key);
        while (table[index] != EMPTY) {  // 线性探测
            index = (index + 1) % size;
        }
        table[index] = key;
    }

    bool search(int key) {
        int index = hash(key);
        int start = index;
        while (table[index] != EMPTY) {
            if (table[index] == key) return true;
            index = (index + 1) % size;
            if (index == start) break;
        }
        return false;
    }
};

int main() {
    OpenAddressingHashTable ht(10);
    ht.insert(15);
    ht.insert(25);
    cout << ht.search(15) << endl; // 输出 1
    cout << ht.search(20) << endl; // 输出 0
}

5. 动态扩容（Rehashing）

当负载因子 > 0.75，进行扩容。
扩容规则：
1. 新建更大数组（通常为原来的 2 倍）。
2. 重新计算哈希值并插入新数组。

void rehash() {
    vector<list<int>> oldTable = table;
    size *= 2;
    table.clear();
    table.resize(size);

    for (auto &bucket : oldTable) {
        for (int key : bucket) {
            insert(key);
        }
    }
}

6. 哈希表的实际应用

数据库索引（如 MySQL Hash Index）。
缓存系统（如 Redis）。
去重查重（如 unordered_set）。
字符串模式匹配（如 Rabin-Karp 算法）。

7. 哈希表 vs. 二叉搜索树（BST）

特性	哈希表（Hash Table）	二叉搜索树（BST）
查找	O(1)	O(log n)
插入	O(1)	O(log n)
删除	O(1)	O(log n)
有序性	❌（无序）	✅（有序）
区间查找	❌（不支持）	✅（支持）
动态性	可能需要 Rehash	动态插入删除
适用场景	快速查找、集合	需要排序的场景