C++经典的数据结构与算法之哈希表详解(Hash Table)

哈希表（Hash Table）：高效的键值对存储结构

哈希表（又称散列表）是一种通过哈希函数将键（Key）映射到值（Value）的高效数据结构，它能在理想情况下达到O(1)的插入、删除和查找效率，是实现字典、缓存等功能的核心结构。

哈希表的基本操作

• ‌插入（Insert）‌：将一个新的键值对添加到哈希表中。
• ‌查找（Search）‌：根据键来查找对应的值。
• ‌删除（Delete）‌：根据键来删除对应的键值对。

一、哈希表的核心原理

哈希表的工作流程基于三个关键组件：

1. 哈希函数（Hash Function）：将键映射到数组的索引位置，记为 hash(key) = index。
2. 哈希表数组：存储值的数组，索引由哈希函数计算得出。
3. 冲突解决机制：当不同键映射到同一索引时（哈希冲突）的处理策略。

1. 哈希函数设计

理想的哈希函数应满足：

• 确定性：同一键始终映射到同一索引。
• 均匀性：键分布均匀，减少冲突。
• 高效性：计算快速。

常见哈希函数示例（整数键）：

// 取模哈希（最常用）
int hashFunction(int key, int tableSize) {
    return key % tableSize; // 确保索引在数组范围内
}
// 字符串哈希（将字符ASCII值组合）
int hashString(const string& key, int tableSize) {
    int hash = 0;
    for (char c : key) {
        hash = (hash * 31 + c) % tableSize; // 31是质数，减少冲突
    }
    return hash;
}

2. 哈希冲突解决

即使哈希函数设计良好，冲突仍不可避免，常见解决方法有：

开放地址法：冲突时寻找下一个空位置（线性探测、二次探测等）。

// 线性探测：冲突时索引+1，循环查找
int linearProbe(int index, int i, int tableSize) {
    return (index + i) % tableSize; // i为探测次数
}

• 链地址法（拉链法）：每个数组元素是链表（或红黑树），冲突元素直接加入链表。
  • 优点：处理简单，不易产生聚集，适合频繁插入删除。
  • 缺点：需额外空间存储指针。

二、基于链地址法的哈希表实现

链地址法是实际应用中最常用的冲突解决策略（如Java的HashMap、C++的unordered_map），下面实现一个完整的哈希表：

#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;
template <typename K, typename V>
class HashTable {
private:
    // 键值对结构
    struct Entry {
        K key;
        V value;
        Entry(K k, V v) : key(k), value(v) {}
    };
    vector<list<Entry>> table; // 哈希表数组（每个元素是链表）
    int size;                  // 当前元素数量
    int capacity;              // 表容量
    const double loadFactorThreshold = 0.7; // 负载因子阈值（触发扩容）
    // 哈希函数（整数键）
    int hash(const K& key) const {
        // 对整数键直接取模
        return key % capacity;
    }
    // 哈希函数（字符串键）- 模板特化
    int hash(const string& key) const {
        int hash = 0;
        for (char c : key) {
            hash = (hash * 31 + c) % capacity;
        }
        return hash;
    }
    // 扩容操作
    void resize() {
        int oldCapacity = capacity;
        capacity *= 2; // 容量翻倍（通常取质数）
        vector<list<Entry>> newTable(capacity);
        // 重新哈希所有元素到新表
        for (int i = 0; i < oldCapacity; i++) {
            for (const Entry& entry : table[i]) {
                int index = hash(entry.key);
                newTable[index].push_back(entry);
            }
        }
        table.swap(newTable); // 替换为新表
    }
public:
    // 构造函数：初始容量默认31（质数）
    HashTable(int initialCapacity = 31) : capacity(initialCapacity), size(0) {
        table.resize(capacity);
    }
    // 插入键值对（若键已存在则更新值）
    void insert(const K& key, const V& value) {
        // 检查负载因子，超过阈值则扩容
        if ((double)size / capacity >= loadFactorThreshold) {
            resize();
        }
        int index = hash(key);
        // 检查是否已存在该键，存在则更新值
        for (Entry& entry : table[index]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }
        // 不存在则插入新键值对
        table[index].emplace_back(key, value);
        size++;
    }
    // 删除键值对（成功返回true）
    bool remove(const K& key) {
        int index = hash(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->key == key) {
                table[index].erase(it);
                size--;
                return true;
            }
        }
        return false; // 键不存在
    }
    // 查找键对应的值（找到返回true，值通过引用传出）
    bool find(const K& key, V& value) const {
        int index = hash(key);
        for (const Entry& entry : table[index]) {
            if (entry.key == key) {
                value = entry.value;
                return true;
            }
        }
        return false; // 键不存在
    }
    // 获取当前元素数量
    int getSize() const {
        return size;
    }
    // 打印哈希表结构（调试用）
    void print() const {
        for (int i = 0; i < capacity; i++) {
            cout << "Bucket " << i << ": ";
            for (const Entry& entry : table[i]) {
                cout << "(" << entry.key << ":" << entry.value << ") ";
            }
            cout << endl;
        }
    }
};
// 测试代码
int main() {
    // 测试整数键哈希表
    HashTable<int, string> intHash;
    intHash.insert(1, "Apple");
    intHash.insert(2, "Banana");
    intHash.insert(31, "Cherry"); // 31 % 31 = 0，与1%31=1不冲突
    intHash.insert(32, "Date");   // 32 % 31 = 1，与1冲突（拉链处理）
    cout << "整数键哈希表：" << endl;
    intHash.print();
    // 输出：
    // Bucket 0: (31:Cherry) 
    // Bucket 1: (1:Apple) (32:Date) 
    // ...（其他桶为空）
    string val;
    if (intHash.find(32, val)) {
        cout << "找到32: " << val << endl; // 输出：找到32: Date
    }
    intHash.remove(2);
    cout << "删除键2后大小：" << intHash.getSize() << endl; // 输出：3
    // 测试字符串键哈希表
    HashTable<string, int> strHash;
    strHash.insert("Alice", 25);
    strHash.insert("Bob", 30);
    strHash.insert("Charlie", 35);
    cout << "\n字符串键哈希表：" << endl;
    strHash.print();
    return 0;
}

三、哈希表的关键特性

• 负载因子（Load Factor）：
  • 定义：负载因子 = 元素数量 / 表容量。
  • 作用：衡量哈希表的拥挤程度，负载因子越大，冲突概率越高。
  • 策略：当负载因子超过阈值（通常0.7）时，触发扩容（容量翻倍），重新哈希所有元素。
• 时间复杂度：
  • 理想情况（无冲突）：插入、删除、查找均为O(1)。
  • 最坏情况（所有元素冲突）：退化为链表操作，O(n)。
  • 实际应用：通过合理设计哈希函数和扩容策略，平均复杂度接近O(1)。
• 与其他数据结构对比：

四、C++标准库中的哈希表

C++11引入了unordered_map和unordered_set，底层基于哈希表（链地址法）实现：

#include <unordered_map>
#include <unordered_set>
#include <iostream>
int main() {
    // unordered_map：键值对存储
    unordered_map<string, int> umap;
    umap["Apple"] = 5;
    umap["Banana"] = 3;
    // 查找
    if (umap.find("Apple") != umap.end()) {
        cout << "Apple: " << umap["Apple"] << endl;
    }
    // unordered_set：唯一元素存储
    unordered_set<int> uset = {1, 2, 3, 2}; // 自动去重
    for (int x : uset) {
        cout << x << " "; // 输出顺序不确定（无序）
    }
    return 0;
}

特点：

• 不保证元素顺序，迭代顺序可能随插入/删除变化。
• 支持自定义哈希函数和相等性判断（通过模板参数）。
• 性能优于map/set（红黑树），适合频繁查询的场景。

五、哈希表的应用场景

1. 缓存系统：如浏览器缓存、数据库缓存，用哈希表快速查找缓存内容。
2. 数据库索引：部分数据库用哈希索引加速等值查询（如MongoDB）。
3. 去重操作：如unordered_set快速判断元素是否存在。
4. 计数器：统计词频（如“给定字符串，找出出现次数最多的字符”）。
5. 哈希映射：如URL短链接服务，将长URL映射为短码。

总结

哈希表通过哈希函数直接映射索引，结合冲突解决机制，实现了接近O(1)的操作效率，是平衡“时间-空间”的优秀选择。实际开发中，C++开发者通常直接使用unordered_map/unordered_set，但理解其底层原理（哈希函数、冲突处理、扩容机制）有助于更好地优化性能。哈希表的核心挑战在于哈希函数设计和冲突处理，合理的参数设置（如初始容量、负载因子）能显著提升其表现。