C++哈希算法详解（从零开始掌握哈希函数与哈希表的实现）

什么是哈希函数？

哈希函数是一个将输入（通常称为“键”）转换为固定大小整数（称为“哈希值”或“哈希码”）的函数。理想情况下，不同的输入应产生不同的哈希值，但在实际中会发生“冲突”——即两个不同键产生相同哈希值。

C++哈希算法的基本要求

• 确定性：相同的输入必须始终产生相同的输出。
• 高效性：计算速度快。
• 均匀分布：尽可能减少冲突。

实现一个简单的哈希函数

我们先从字符串类型的键入手，实现一个经典的除法哈希函数：

#include <iostream>#include <string>// 简单的字符串哈希函数（除法散列法）size_t simpleHash(const std::string& key, size_t tableSize) {    size_t hash = 0;    for (char c : key) {        hash = (hash * 31 + static_cast<size_t>(c)) % tableSize;    }    return hash;}int main() {    std::string key = "hello";    size_t tableSize = 100;    size_t index = simpleHash(key, tableSize);    std::cout << "Key '" << key << "' maps to index: " << index << std::endl;    return 0;}

上面的代码使用了常见的多项式滚动哈希（乘以31），这是Java和许多其他语言中使用的经典方法。这里的 tableSize 是哈希表的大小，我们用模运算确保哈希值落在有效索引范围内。

处理哈希冲突：链地址法

当两个不同的键映射到同一个索引时，就发生了冲突。一种常用解决方法是链地址法（Chaining）：每个哈希表槽位存储一个链表，所有映射到该位置的键值对都存入这个链表。

#include <iostream>#include <vector>#include <list>#include <string>class SimpleHashTable {private:    std::vector<std::list<std::pair<std::string, int>>> table;    size_t tableSize;    size_t hash(const std::string& key) {        size_t h = 0;        for (char c : key) {            h = (h * 31 + static_cast<size_t>(c)) % tableSize;        }        return h;    }public:    SimpleHashTable(size_t size) : tableSize(size), table(size) {}    void insert(const std::string& key, int value) {        size_t index = hash(key);        // 检查是否已存在该键        for (auto& pair : table[index]) {            if (pair.first == key) {                pair.second = value; // 更新值                return;            }        }        table[index].push_back({key, value});    }    int get(const std::string& key) {        size_t index = hash(key);        for (const auto& pair : table[index]) {            if (pair.first == key) {                return pair.second;            }        }        throw std::runtime_error("Key not found");    }};int main() {    SimpleHashTable ht(10);    ht.insert("apple", 5);    ht.insert("banana", 3);    std::cout << "apple: " << ht.get("apple") << std::endl;    std::cout << "banana: " << ht.get("banana") << std::endl;    return 0;}

这段代码展示了如何用 C++ 实现一个支持插入和查找的简易哈希表。它使用 std::vector 存储多个 std::list，每个列表对应一个桶（bucket）。

为什么学习C++哈希算法很重要？

掌握C++哈希算法不仅能帮助你理解 STL 中 unordered_map 和 unordered_set 的底层原理，还能提升你在面试和实际项目中的问题解决能力。此外，良好的哈希设计能显著提高程序性能。

总结

本文详细讲解了如何用 C++ 实现基本的哈希函数和哈希表，包括冲突处理机制。通过动手编写代码，你已经掌握了哈希函数实现的核心思想。下一步可以尝试实现开放寻址法、动态扩容等高级特性。

关键词回顾：C++哈希算法、哈希函数实现、C++编程教程、哈希表原理。