---

前言

在 C++ 编程里，哈希表（散列表） 是查询、插入、删除效率接近 O(1) 的顶级数据结构，也是 C++11 unordered_map / unordered_set 的底层核心。

很多新手觉得哈希表很难，但其实它的思想非常简单：用数组做存储，用哈希函数把数据映射到数组下标。

这篇博客我会用最通俗的语言，带你从原理 → 哈希函数 → 冲突解决 → 扩容 → 完整 C++ 代码，一步步实现一个工业级的链式哈希表，新手也能直接看懂、直接运行。

---

一、什么是哈希表？为什么它这么快？

1. 核心思想

哈希表 = 数组 + 哈希函数

• 数组：支持随机访问 O (1)
• 哈希函数：将任意 key 转换成数组下标

我们要存一个数据时：

1. 用哈希函数计算：index = hash(key)
2. 直接把数据放在数组 index 位置
3. 查找时同样计算下标，直接读取

这就是 O (1) 效率的来源！

2. 两个核心问题（必须解决）

1. 哈希冲突：两个不同 key 算出来的 index 相同怎么办？
2. 负载因子过高：数据越来越多，数组装不下怎么办？

---

二、哈希冲突解决方案（最常用：链式哈希）

最经典、最实用、C++ STL 标准使用的方案：拉链法（开散列）

原理

• 数组里不直接存数据，而是存链表的头指针
• 发生冲突时，把数据挂在链表后面

结构：

数组下标：[0] [1] [2] [3] [4] ...
           ↓   ↓   ↓   ↓   ↓
         链表 链表 链表 链表 链表

优点：实现简单、冲突处理高效、不会堆积。

---

三、哈希表扩容机制

什么是负载因子？

负载因子 = 有效元素个数 / 数组大小

负载因子越大，冲突概率越高，效率越低。

STL 默认负载因子：1.0

• 当 元素个数 > 数组大小时，自动扩容
• 一般扩容为 原大小的 2 倍
• 扩容后要重新计算所有元素的下标（重新哈希）

---

四、C++ 实现哈希表（完整可运行代码）

下面实现一个通用哈希表，支持任意类型 key，支持插入、删除、查找、扩容。

1. 哈希节点结构

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 哈希表节点（链表节点）
template <class T>
struct HashNode {
    T _data;           // 存储数据
    HashNode<T>* _next; // 链表指针

    HashNode(const T& data)
        : _data(data)
        , _next(nullptr)
    {}
};

2. 哈希表核心实现

template <class T, class KeyOfT>
class HashTable {
    typedef HashNode<T> Node;
public:
    // 构造函数：初始大小10
    HashTable(size_t size = 10) {
        _tables.resize(size, nullptr);
        _size = 0; // 有效元素个数
    }

    // 析构函数
    ~HashTable() {
        for (size_t i = 0; i < _tables.size(); ++i) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
    }

    // 插入
    bool Insert(const T& data) {
        // 检查是否需要扩容
        if (_size >= _tables.size())
            Expand();

        KeyOfT kot;
        size_t index = Hash(kot(data)); // 计算下标
        Node* cur = _tables[index];

        // 检查是否已存在
        while (cur) {
            if (kot(cur->_data) == kot(data))
                return false;
            cur = cur->_next;
        }

        // 头插（比尾插快）
        cur = new Node(data);
        cur->_next = _tables[index];
        _tables[index] = cur;
        _size++;
        return true;
    }

    // 查找
    Node* Find(const T& data) {
        KeyOfT kot;
        size_t index = Hash(kot(data));
        Node* cur = _tables[index];

        while (cur) {
            if (kot(cur->_data) == kot(data))
                return cur;
            cur = cur->_next;
        }
        return nullptr;
    }

    // 删除
    bool Erase(const T& data) {
        KeyOfT kot;
        size_t index = Hash(kot(data));
        Node* cur = _tables[index];
        Node* prev = nullptr;

        while (cur) {
            if (kot(cur->_data) == kot(data)) {
                if (prev == nullptr)
                    _tables[index] = cur->_next;
                else
                    prev->_next = cur->_next;

                delete cur;
                _size--;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

    size_t Size() const { return _size; }

private:
    // 哈希函数（除留余数法）
    size_t Hash(const size_t& key) {
        return key % _tables.size();
    }

    // 扩容：2倍扩容
    void Expand() {
        size_t newSize = _tables.size() * 2;
        vector<Node*> newTables;
        newTables.resize(newSize, nullptr);

        // 遍历旧表，重新哈希
        for (size_t i = 0; i < _tables.size(); ++i) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                size_t index = Hash(cur->_data) % newSize;

                // 头插新表
                cur->_next = newTables[index];
                newTables[index] = cur;
                cur = next;
            }
        }

        // 交换
        _tables.swap(newTables);
    }

private:
    vector<Node*> _tables; // 哈希表数组
    size_t _size;          // 有效元素个数
};

---

五、测试哈希表

// 测试int类型
void TestHashTable() {
    // 仿函数：获取key
    struct KeyOfT {
        size_t operator()(int data) {
            return data;
        }
    };

    HashTable<int, KeyOfT> ht;
    ht.Insert(1);
    ht.Insert(2);
    ht.Insert(3);
    ht.Insert(11); // 冲突
    ht.Insert(21); // 冲突

    cout << "元素个数：" << ht.Size() << endl;

    if (ht.Find(11))
        cout << "找到 11" << endl;

    ht.Erase(11);
    cout << "删除11后个数：" << ht.Size() << endl;
}

int main() {
    TestHashTable();
    return 0;
}

运行结果

元素个数：5
找到 11
删除11后个数：4

---

六、核心知识点总结（面试必问）

1. 哈希表为什么快？

直接通过哈希函数计算下标，一步定位，不需要像树一样一步步查找。

2. 什么是哈希冲突？怎么解决？

不同 key 得到相同下标，叫冲突。解决方案：拉链法（最常用）、开放寻址法、再哈希法。

3. 为什么要扩容？

减少冲突概率，保证查询效率稳定在 O (1)。

4. STL 中 unordered_map /unordered_set 底层是什么？

哈希表（拉链法）平均 O (1)，比 map /set（红黑树 O (logN)）快很多。

---

七、哈希表 vs 红黑树

表格

结构	查找	插入	删除	有序	应用
哈希表	O(1)	O(1)	O(1)	无序	unordered_map
红黑树	O(logN)	O(logN)	O(logN)	有序	map / set

---

八、总结

这篇博客你学到了：

✅ 哈希表本质：数组 + 哈希函数

✅ 冲突解决：拉链法

✅ 自动扩容机制

✅ C++ 完整实现通用哈希表

哈希表是 C++ 开发最常用、最高效的容器结构，也是面试必考重点。