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

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

说到哈希表，本质上就是通过一个哈希函数，把键（Key）直接映射到值（Value）的高效数据结构。想象一下，你有一个黑箱子，扔进去一个钥匙，“啪”的一下就能弹出对应的物品——理想情况下，插入、删除和查找都能在 O(1) 时间里搞定。字典、缓存这些核心功能，背后几乎都离不开它。

哈希表的基本操作其实很直观：

• 插入（Insert）：把一个新的键值对放进去。
• 查找（Search）：通过键找到对应的值。
• 删除（Delete）：通过键把键值对移除。

一、哈希表的核心原理

哈希表能跑得这么快，主要靠三个关键组件协同工作：

1. 哈希函数（Hash Function）——负责把键映射到数组的某个位置，记作 hash(key) = index。
2. 哈希表数组——真正存值的地方，每个索引对应一个槽位。
3. 冲突解决机制——不同键算出来同一个索引（也就是哈希冲突）时，怎么妥善处理。

1. 哈希函数设计

什么样的哈希函数才算理想？核心要求就三条：

• 确定性：同一个键，不管什么时候计算，结果必须一样。
• 均匀性：所有键能尽可能均匀地散列到各个槽位，减少冲突。
• 高效性：计算本身要快，不能拖后腿。

最常见的整数哈希就是取模运算，字符串哈希则会把字符的ASCII值组合起来。来看两个典型例子：

// 取模哈希（最常用）
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、+2……直到找到空位为止。

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

• 链地址法（拉链法）：每个数组元素不再直接存值，而是存一个链表（或者红黑树）。冲突的元素直接挂在这个链上。
  • 优点：实现简单，不会产生聚集（Clustering），频繁插入删除也很友好。
  • 缺点：需要额外空间存储指针。

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

链地址法可以说是实际应用中最常用的策略，Ja va 的 HashMap、C++ 的 unordered_map 底层都在用。下面给出一个完整的实现：

#include 
#include 
#include 
#include 
using namespace std;
template 
class HashTable {
private:
    // 键值对结构
    struct Entry {
        K key;
        V value;
        Entry(K k, V v) : key(k), value(v) {}
    };
    vector> 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> 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 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 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 
#include 
#include 
int main() {
    // unordered_map：键值对存储
    unordered_map umap;
    umap["Apple"] = 5;
    umap["Banana"] = 3;
    // 查找
    if (umap.find("Apple") != umap.end()) {
        cout << "Apple: " << umap["Apple"] << endl;
    }
    // unordered_set：唯一元素存储
    unordered_set 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 就行，但深入理解它背后的哈希函数、冲突处理、扩容机制，往往能在调优时帮上大忙。说到底，哈希表的核心挑战就两个：哈希函数怎么设计，冲突怎么处理。合理的初始容量、合适的负载因子，这些参数选好了，性能表现会提升一大截。