C++哈希表从零开始（手把手教你实现基础哈希表）

哈希函数原理

哈希函数的作用是将任意大小的输入（如字符串、整数等）转换为固定范围内的整数（通常是数组下标）。例如，对整数 key，我们可以使用取模运算：

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

这个简单的哈希函数就是 哈希函数原理 的体现。但在实际中，我们还要处理“冲突”问题——即两个不同的 key 映射到同一个索引。

处理冲突：链地址法

最常用的解决冲突的方法是“链地址法”（Chaining）：每个数组元素是一个链表，所有哈希到同一位置的元素都存入该链表中。

C++哈希表基础实现

下面，我们用 C++ 实现一个支持整数键的简单哈希表。我们将使用 vector 存储桶（buckets），每个桶是一个 list（链表）。

#include <iostream>#include <vector>#include <list>using namespace std;class SimpleHashTable {private:    vector<list<int>> buckets;    int tableSize;    // 哈希函数    int hash(int key) {        return key % tableSize;    }public:    // 构造函数    SimpleHashTable(int size = 10) : tableSize(size) {        buckets.resize(tableSize);    }    // 插入元素    void insert(int key) {        int index = hash(key);        buckets[index].push_back(key);    }    // 查找元素    bool search(int key) {        int index = hash(key);        for (int value : buckets[index]) {            if (value == key) {                return true;            }        }        return false;    }    // 删除元素（只删除第一个匹配项）    void remove(int key) {        int index = hash(key);        auto& bucket = buckets[index];        for (auto it = bucket.begin(); it != bucket.end(); ++it) {            if (*it == key) {                bucket.erase(it);                return;            }        }    }    // 打印哈希表（用于调试）    void print() {        for (int i = 0; i < tableSize; ++i) {            cout << "Bucket " << i << ": ";            for (int val : buckets[i]) {                cout << val << " ";            }            cout << endl;        }    }};// 测试代码int main() {    SimpleHashTable ht(7); // 创建大小为7的哈希表    ht.insert(10);    ht.insert(20);    ht.insert(15);    ht.insert(7);    ht.print();    cout << "Search 15: " << (ht.search(15) ? "Found" : "Not Found") << endl;    cout << "Search 25: " << (ht.search(25) ? "Found" : "Not Found") << endl;    ht.remove(15);    cout << "After removing 15:\n";    ht.print();    return 0;}

代码说明

• 构造函数：初始化哈希表大小，并创建对应数量的空链表。
• hash 函数：使用取模运算将 key 映射到 [0, tableSize-1] 范围内。
• insert：将 key 插入对应桶的链表尾部。
• search：遍历对应桶的链表，查找是否存在 key。
• remove：找到并删除第一个匹配的 key。

总结

通过本教程，你已经掌握了 C++哈希表实现 的基本思路。虽然这个版本非常基础（仅支持整数、无动态扩容、无负载因子控制），但它涵盖了 哈希表基础教程 的核心概念：哈希函数、冲突处理、插入/查找/删除操作。

下一步你可以尝试：支持字符串 key、实现动态扩容、使用更高效的哈希函数（如 djb2）、或改用开放寻址法处理冲突。掌握这些，你就真正理解了 C++ 中 unordered_map 的底层原理！