C++ 哈希表链地址法（哈希桶）实现

C++ 哈希表链地址法实现详解。针对开放定址法数据堆积问题，采用哈希桶（链表）存储冲突元素。支持负载因子大于 1，STL 风格控制在 1 时扩容。核心逻辑包含头插法插入、扩容时旧节点迁移至新表、遍历删除节点、查找键值对及析构资源释放。代码提供模板类实现，含自定义哈希函数特化。

星落发布于 2026/3/250 浏览

C++ 哈希表链地址法（哈希桶）实现

前言

前面我们用开放定址法代码实现了哈希表。对于开放定址法来说，包含以下两种探测插入节点位置方法：

线性探测
二次探测

哈希表示意图

但是开放定址法的缺点也很明显，开放定址法容易很多数据堆积在一起，大大减少了效率。为了解决上述问题，引入了第二种方法实现哈希表——链地址法（哈希桶法）。

一、链地址法概念

开放定址法中，所有的元素都放到哈希表里。链地址法中，所有的数据不再直接存储在哈希表中。哈希表中存储一个指针，没有数据映射到这个位置时，这个指针为空；有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面。链地址法也叫做拉链法或者哈希桶。

下面演示 {19,30,5,36,13,20,21,12,24,96} 等这一组值映射到 M=11 的表中。

哈希表映射示例

二、哈希表扩容

开放定址法的负载因子必须小于 1，而链地址法的负载因子则没有限制，可以大于 1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。

STL 中 unordered_xxx 的最大负载因子基本控制在 1，当负载因子大于 1 时会扩容。我们下面的实现也使用这种方式。

也就是说，我们期望基本每个节点下面都挂一个桶，有那么一两个数据，如下图：

扩容示意

三、哈希桶插入逻辑

首先，如果不需要扩容，我们需要将一个节点挂上去，因为每一个哈希桶类似于链表，而链表的头插效率是十分高的，因此我们采用头插。

头插示意

// 如果不需要扩容
size_t hashi = hf(kv.first) % _table.size();
// 头插
Node* newnode = newNode(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;

相关免费在线工具

加密/解密文本

使用加密算法（如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

#pragma once #include<vector> namespace hash_bucket { template<classK>structDefaultHashFunc{ size_t operator()(const K& key){return(size_t)key;} }; template<>structDefaultHashFunc<string>{ size_t operator()(const string& str){ // BKDR size_t hash =0; for(auto ch : str){ hash *=131; hash += ch; } return hash; } }; template<classK,classV>structHashData{ pair<K, V> _kv; HashData<K, V>* _next; HashData(const pair<K, V>& kv):_kv(kv),_next(nullptr){} }; template<classK,classV,classHashFunc= DefaultHashFunc<K>>classHashTable{ typedef HashData<K, V> Node; public: HashTable(){ _table.resize(10,nullptr);} ~HashTable(){ for(size_t i = 0; i < _table.size(); i++){ Node* cur = _table[i]; while(cur){ Node* next = cur->_next; delete cur; cur = next; } _table[i]=nullptr; } } boolInsert(const pair<K, V>& kv){ if(Find(kv.first)){returnfalse;} // 仿函数控制 HashFunc hf; // 如果需要扩容 if(_n == _table.size()){ size_t newSize = _table.size()*2; vector<Node*> newTable; newTable.resize(newSize,nullptr); // 遍历旧表，顺手牵羊，把节点牵下来挂到新表 for(size_t i = 0; i < _table.size(); i++){ Node* cur = _table[i]; while(cur){ Node* next = cur->_next; // 头插到新表 size_t newhashi =hf(cur->_kv.first)% newSize; cur->_next = newTable[newhashi]; newTable[newhashi]= cur; cur = next; } _table[i]=nullptr; } _table.swap(newTable); } // 如果不需要扩容 size_t hashi =hf(kv.first)% _table.size(); // 头插 Node* newnode =newNode(kv); newnode->_next = _table[hashi]; _table[hashi]= newnode; ++_n; returntrue; } Node*Find(const K& key){ HashFunc hf; size_t hashi =hf(key)% _table.size(); Node* cur = _table[hashi]; while(cur){ if(cur->_kv.first == key){return cur;} cur = cur->_next; } returnnullptr; } boolErase(const K& key){ HashFunc hf; size_t hashi =hf(key)% _table.size(); Node* cur = _table[hashi]; Node* prev =nullptr; while(cur){ if(cur->_kv.first == key){ if(prev ==nullptr){ _table[hashi]= cur->_next; }else{ prev->_next = cur->_next; } delete cur; returntrue; }else{ prev = cur; cur = cur->_next; } } returnfalse; } voidPrint(){ for(size_t i = 0; i < _table.size(); i++){ printf("[%d]->", i); Node* cur = _table[i]; while(cur){ cout << cur->_kv.first <<":"<< cur->_kv.second <<"->"; cur = cur->_next; } printf("NULL\n"); } cout << endl; } private: vector<Node*> _table;// 指针数组 size_t _n =0;// 存储了多少个有效数据 }; }

C++ 哈希表链地址法（哈希桶）实现

C++ 哈希表链地址法（哈希桶）实现