哈希表概念、冲突解决与 C++ 实现

哈希表通过键值对存储实现快速定位。文章介绍了哈希表概念、直接定址法、哈希冲突原因及负载因子影响。重点讲解了开放定址法（线性探测、二次探测、双重探测）和链地址法的原理与区别，并提供了基于 C++ 的链地址法哈希表完整代码实现，包含插入、查找、删除及扩容逻辑。

2177283801发布于 2026/3/27更新于 2026/4/212 浏览

哈希表的概念

哈希又称散列，本质是通过一种键值对存储的高效组织方式。通过一个哈希函数，将数据的关键字直接映射到存储的位置中，实现快速的定位。

就像在图书馆中可以根据图书的编号来快速查找图书的位置。

直接定址法

直接借用关键字作为存储位置的下标。

直接定址法示意图

class Solution {
public:
    int first(string s) {
        int count[26] = { 0 };
        for (auto e : s) {
            count[e - 'a']++;
        }
        for (size_t i = 0; i < s.size(); i++) {
            if (count[s[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
};

注：查找数组中唯一出现的字符，字符只有 26 个，直接定义一个数组来记录每个字母出现的次数。

如果数据集中没有哈希冲突，而且效率高，但是数据如果分散，会造成数据的浪费，甚至内存浪费。

哈希冲突

在使用哈希函数进行映射的时候，不可避免地会出现两个不同的关键字映射到同一个下标的情况，这就是哈希冲突。

比如：用'关键字对 11 取模'作为哈希函数（M=11），关键字 19 和 30 的计算结果都是 8（19%11=8，30%11=8），这就产生了冲突。

理想情况下，我们希望哈希函数能让关键字均匀分布在数组中，减少冲突，但实际场景中冲突无法完全避免——就像图书馆的书架位置有限，总会有新书的编号对应已被占用的位置。因此，哈希表的设计核心包含两部分：

设计优秀的哈希函数，减少冲突次数；
设计高效的冲突解决机制，处理已发生的冲突。

我们还需要介绍负载因子：

它是衡量哈希表拥挤程度的核心指标，直接影响冲突概率。

负载因子 α = 哈希表中存储的元素个数（N） / 哈希表的数组大小（M）

负载因子与哈希表性能的关系是：

α 越大：哈希表越拥挤，冲突概率越高，查询效率越低；
α 越小：哈希表越宽松，冲突概率越低，但空间利用率越低。

不同冲突解决机制对应的负载因子阈值不同：

开放定址法：α 必须小于 1（因为所有元素都存储在数组中，数组满了就无法插入）；

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; // 哈希仿函数：支持整数 Key template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; // 字符串 Key 的特化仿函数（BKDR 哈希） template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto ch : key) { hash = hash * 131 + ch; } return hash; } }; namespace hash_bucket { // 哈希链表节点 template<class K, class V> struct HashNode { pair<K, V> _kv; // 键值对 HashNode<K, V>* _next; // 下一个节点指针 // 构造函数 HashNode(const pair<K, V>& kv) : _kv(kv) , _next(nullptr) {} }; // 链地址法哈希表（哈希桶） template<class K, class V, class Hash = HashFunc<K>> class HashTable { private: typedef HashNode<K, V> Node; vector<Node*> _tables; // 桶数组（存储链表头指针） size_t _n = 0; // 存储的元素个数 // 质数表：用于扩容 static const unsigned long __stl_prime_list[]; static const int __stl_num_primes; // 获取下一个质数 unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } public: // 构造函数：初始化桶数组为第一个质数（53），所有桶为空指针 HashTable() { _tables.resize(__stl_next_prime(0), nullptr); } // 析构函数：释放所有节点和桶数组 ~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; // 桶置空 } } // 插入键值对：头插法，效率 O(1) bool Insert(const pair<K, V>& kv) { // 查找是否已存在，避免重复插入 if (Find(kv.first) != nullptr) { return false; } // 负载因子≥1，扩容 if (_n == _tables.size()) { // 新桶数组大小为下一个质数 size_t newSize = __stl_next_prime(_tables.size() + 1); vector<Node*> newTables(newSize, nullptr); Hash hash; // 遍历旧桶，将节点重新映射到新桶 for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 保存下一个节点 // 计算节点在新桶中的位置 size_t hashi = hash(cur->_kv.first) % newTables.size(); // 头插法插入新桶 cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; // 处理下一个节点 } _tables[i] = nullptr; // 旧桶置空 } // 交换新旧桶数组 _tables.swap(newTables); } Hash hash; size_t hashi = hash(kv.first) % _tables.size(); // 计算桶下标 // 头插法插入新节点 Node* newNode = new Node(kv); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return true; } // 查找 Key：返回节点指针，不存在返回 nullptr Node* Find(const K& key) { Hash hash; size_t hashi = hash(key) % _tables.size(); // 找到对应的桶 Node* cur = _tables[hashi]; // 遍历链表查找 while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; } // 删除 Key：成功返回 true，不存在返回 false bool Erase(const K& key) { Hash hash; size_t hashi = hash(key) % _tables.size(); // 找到对应的桶 Node* prev = nullptr; Node* cur = _tables[hashi]; // 遍历链表查找要删除的节点 while (cur) { if (cur->_kv.first == key) { // 找到节点，删除 if (prev == nullptr) { // 要删除的是头节点，更新桶的头指针 _tables[hashi] = cur->_next; } else { // 要删除的是中间节点，prev->next 指向 cur->next prev->_next = cur->_next; } delete cur; --_n; return true; } // 移动指针 prev = cur; cur = cur->_next; } return false; } // 获取元素个数 size_t Size() const { return _n; } // 判空 bool Empty() const { return _n == 0; } // 打印哈希表（调试用） void Print() { for (size_t i = 0; i < _tables.size(); ++i) { cout << "桶" << i << ": "; Node* cur = _tables[i]; while (cur) { cout << cur->_kv.first << "→" << cur->_kv.second << " "; cur = cur->_next; } cout << endl; } cout << "当前元素个数：" << _n << endl; cout << "当前负载因子：" << (double)_n / _tables.size() << endl; } // 禁止拷贝构造和赋值（简化实现，如需支持可自行添加深拷贝） HashTable(const HashTable&) = delete; HashTable& operator=(const HashTable&) = delete; }; // 初始化质数表 template<class K, class V, class Hash> const unsigned long HashTable<K, V, Hash>::__stl_prime_list[] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; template<class K, class V, class Hash> const int HashTable<K, V, Hash>::__stl_num_primes = sizeof(__stl_prime_list) / sizeof(__stl_prime_list[0]); } // 测试代码 int main() { hash_bucket::HashTable<string, int> ht; // 插入测试 ht.Insert({"apple", 10}); ht.Insert({"banana", 20}); ht.Insert({"orange", 30}); ht.Insert({"grape", 40}); ht.Insert({"pear", 50}); ht.Insert({"watermelon", 60}); ht.Insert({"pineapple", 70}); cout << "插入后哈希表：" << endl; ht.Print(); cout << endl; // 查找测试 auto orange = ht.Find("orange"); if (orange) { cout << "查找 orange：" << orange->_kv.first << " → " << orange->_kv.second << endl; } else { cout << "查找 orange：未找到" << endl; } auto peach = ht.Find("peach"); if (peach) { cout << "查找 peach：" << peach->_kv.first << " → " << peach->_kv.second << endl; } else { cout << "查找 peach：未找到" << endl; } cout << endl; // 删除测试 bool ret = ht.Erase("grape"); cout << "删除 grape：" << (ret ? "成功" : "失败") << endl; cout << "删除后哈希表：" << endl; ht.Print(); cout << endl; // 插入重复 Key ret = ht.Insert({"apple", 15}); cout << "插入重复的 apple：" << (ret ? "成功" : "失败") << endl; cout << "最终哈希表：" << endl; ht.Print(); return 0; }

哈希表概念、冲突解决与 C++ 实现

哈希表的概念

直接定址法

哈希冲突

更多推荐文章

相关免费在线工具

哈希冲突解决

开放定址法

线性探测

二次探测

双重探测

链地址法

实现链地址法

哈希表概念、冲突解决与 C++ 实现

哈希表的概念

直接定址法

哈希冲突

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

哈希冲突解决

开放定址法

线性探测

二次探测

双重探测

链地址法

实现链地址法