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

本文讲解 C++ 中基于链地址法的哈希表实现。对比开放定址法，链地址法利用链表处理哈希冲突，允许负载因子大于 1。内容涵盖哈希桶概念、扩容机制、插入（头插法）、删除、查找逻辑及完整代码实现，包含自定义哈希函数与析构函数细节。

机器人发布于 2026/3/270 浏览

前言

前面我们使用开放定址法实现了哈希表。

对于开放定址法来说，包含以下两种探测插入节点位置方法：

线性探测
二次探测

在这里插入图片描述

但是开放定址法的缺点也很明显，开放定址法容易很多数据堆积在一起，大大减少了效率。

为了解决上述问题，引入了第二种方法实现哈希表——链地址法（哈希桶法）

一、链地址法概念

开放定址法中，所有的元素都放到哈希表里。

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

下⾯演⽰ {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 = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
 ;

相关免费在线工具

加密/解密文本

使用加密算法（如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 = new Node(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++ 哈希表链地址法（哈希桶）实现详解