当前位置： 首页 > news >正文

【数据结构】C++的unordered_map/set模拟实现(开散列(哈希桶)作底层)

news 2025/7/4 10:22:00

本篇建立在已经熟悉map/set模拟实现和开散列的模拟实现的基础上，关于开散列，可以看上一篇文章：

【数据结构】哈希——闭散列/开散列模拟实现(C++)-CSDN博客本文对比分析了C++中unordered_map/unordered_set与map/set的主要区别。底层实现上，前者采用哈希表（O(1)时间复杂度），后者使用红黑树（O(logN)）。重点探讨了哈希冲突的两种解决方案：闭散列（开放定址法）和开散列（哈希桶）。闭散列通过线性探测或二次探测解决冲突，但存在效率问题；开散列则通过链表存储冲突元素，效率更高。文章还提供了哈希表的模拟实现代码，包括插入、查找、删除等操作，并比较了两种容器在百万级数据下的性能差异。 https://blog.csdn.net/suimingtao/article/details/149002209
【数据结构】C++的map/set模拟实现(红黑树作底层)-CSDN博客文章浏览阅读777次，点赞11次，收藏26次。本文介绍了基于红黑树实现C++中的map和set容器。通过复用单一红黑树结构，分别处理K模型(set)和KV模型(map)。重点内容包括：1) 红黑树改造，引入KeyOfValue仿函数解决不同类型值比较问题；2) 迭代器实现，包括++/--操作的中序遍历逻辑；3) map的[]运算符重载，通过insert返回pair 实现。相比传统双树实现方式，这种高级复用方案减少了代码冗余，同时保持了高效性能，插入操作时间复杂度为O(logN)。 https://blog.csdn.net/suimingtao/article/details/148928079

迭代器实现

在实现unordered_map/unordered_set之前，先将开散列的迭代器实现一下

迭代器的结构

对于迭代器来说，也需要传KOfT，Hash参数，还需要一个该哈希表的指针(即下面的_pht)，关于原因稍候早说

template<class K,class T,class KOfT,class Hash,class Ref,class Ptr>
struct HashIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KOfT, Hash> HT;typedef __HashIterator<K, T, KOfT, Hash,Ref,Ptr> Self;//迭代器本身HashIterator(Node* node,HT* pht)//默认构造:_node(node),_pht(pht){ }
private:Node* _node;//每个桶中的节点HT* _pht;//当一个桶走完时，为了可以找到下一个桶，需要该哈希表的指针};

迭代器的解引用 

迭代器中主要存的还是一个节点的指针，即_node，对于operator*和operator->重载，了解过map/set的都知道，operator*重载对应set的解引用，因为set中只存key，解引用时也只需要"*"；operator->重载对应map的解引用，因为map中存key和value，解引用时肯定需要"->"指定对应的值

Ref operator*()//unordered_set的解引用
{return _node->_data;
}Ptr operator->()//unordered_map的解引用
{return &_node->_data//在调用"it->first"时，其实是调用了"it->->first"，这里编译器省略了第一次"->"，而这里返回的就是第一次调用的结果，即pair类型的地址
}

 顺便将等于和不等于重载实现一下

bool operator!=(Self it)
{return _node != it._node;
}bool operator==(Self it)
{return _node == it._node;
}

 迭代器的++

unordered_map/unordered_set的迭代器是单向迭代器，因此只有++，没有--

假设现在的迭代器在第一个桶的第一个节点，当它遍历完该桶后，要怎么跳转到下一个有节点的桶？

此时传该哈希表的指针(即_pht)的意义就来了，有了该哈希表的指针，就可以遍历整个哈希表中所有的哈希桶，但要从哪开始遍历？程序怎么知道当前迭代器在哪个桶？

此时传KOfT和Hash的作用就来了，通过对当前迭代器的值除留余数法，就能算出当前迭代器在哪个桶，再去从该桶后面开始遍历即可

Self operator++()//前置++
{assert(_node);//防止节点本来就为空if (_node->_next)//如果该桶还有节点{_node = _node->_next;}else//该桶已被遍历完，需要找下一个桶{KOfT koft;//用于从T类型取出keysize_t index = _pht->HashFunc(koft(_node->_data)) % _pht->_table.size();//除留余数法取出映射index++;for (; index < _pht->_table.size())//从下一个桶开始找非空桶{Node* cur = _pht->_table[index];if (cur){_node = cur;return *this;//若找到，就直接返回本身迭代器}}_node = nullptr;//找不到就将迭代器置end()}return *this;
}Self operator++(int)//后置++
{Self tmp = *this;++*this;return tmp;
}

改造哈希表

 首先哈希表内部与迭代器支持一下

template<class K,class T,class KOfT,class Hash>//T可能是K或pair，KOfT是为了从T中取出key的仿函数，Hash是将不同类型的K转换为整型的仿函数
class HashTable
{typedef HashNode<T> Node;typedef typename __HashIterator<K, T, KOfT, Hash, T&, T*> iterator;typedef typename __HashIterator<K, T, KOfT, Hash, const T&, const T*> const_iterator;//只读迭代器friend iterator;//将只读和读写迭代器都变为友元，迭代器不管什么类型就都可以访问HashTable的_tablefriend const_iterator;
public:iterator begin(){for (size_t i = 0; i < _table.size(); i++){if (_table[i])return iterator(_table[i], this);//将第一个节点转换为迭代器}return end();}iterator end(){return nullptr;//这里就实现的简单点吧}const_iterator begin() const{for (size_t i = 0; i < _table.size(); i++){if (_table[i])return const_iterator(_table[i], this);//将第一个节点转换为迭代器}return end();}const_iterator end() const{return nullptr;}//.................
}

由于需要unordered_map需要支持operator[]，因此需要先将原来的哈希表的Insert改造一下，返回值改为pair<iterator,bool>

pair<iterator,bool> Insert(const T& data)
{KOfT koft;//用于取出T类型的Keyif (_table.size() == _num)//负载因子到1时扩容{//1.开2倍大小空间(不一定是2倍)//2.遍历旧表数据，重新计算在新表中位置//3.释放旧表vector<Node*> newtable;size_t newsize = _table.size() ? _table.size() * 2 : 10;newtable.resize(newsize);for (auto& cur : _table){//将旧表中的节点取下来重新计算在新表中的位置，并插入进去Node* head = cur;while (head){Node* next = head->_next;size_t index = HashFunc(koft(head->_data)) % newtable.size();//头插进桶中head->_next = newtable[index];newtable[index] = head;head = next;}cur = nullptr;//将旧表该位置置空，否则最后析构旧表时就将节点都析构了}_table.swap(newtable);//旧表在出作用域后自动销毁}size_t index = HashFunc(koft(data)) % _table.size();//除留余数法取出映射//先查找值是否重复Node* cur = _table[index];while (cur){if (koft(cur->_data) == koft(data))//如果是重复值，插入失败return make_pair(iterator(cur,this),false);elsecur = cur->_next;}Node* newnode = new Node(data);//开辟新空间//头插到对应桶中(尾插也可以)newnode->_next = _table[index];_table[index] = newnode;_num++;return make_pair(iterator(newnode,this),true);
}

Find的返回值也改成迭代器

iterator Find(const K& key)
{KOfT koft;//用于取出T类型的keysize_t index = HashFunc(key) % _table.size();//算出映射//去该映射桶中找Node* cur = _table[index];while (cur){if (koft(cur->_data) == key)return iterator(cur,this);elsecur = cur->_next;}return iterator(nullptr,this);//找不到返回空
}

模拟实现unordered_map/unordered_set

和map/set时一样，只需要将哈希表套进去就可以

unordered_map

#pragma once
#include "HashTable.h"namespace valkyrie
{using namespace Open_Hash;template<class K,class V,class Hash = _Hash<K>>class unordered_map{struct KeyOfMap//用于从pair类型中取出K{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashTable<K, pair<K, V>, KeyOfMap, Hash>::iterator iterator;typedef typename HashTable<K, pair<K, V>, KeyOfMap, Hash>::const_iterator const_iterator;pair<iterator, bool> Insert(pair<K, V> kv){return _ht.Insert(kv);}iterator Find(const K& key){return _ht.Find(key);}bool Erase(const K& key){return _ht.Erase(key);}V& operator[](const K& key){pair<iterator, bool> pr = _ht.Insert(make_pair(key, V()));//不管插入失败还是成功，first中存的都是该Key的迭代器return pr.first->second;}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}void clear(){_ht.clear();}private:HashTable<K, pair<K, V>, KeyOfMap, Hash> _ht;//哈希表作底层};}

unordered_set

#pragma once
#include "HashTable.h"namespace valkyrie
{using namespace Open_Hash;template<class K, class Hash = _Hash<K>>class unordered_set{struct KeyOfSet//为了适配KeyOfMap{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, K, KeyOfSet, Hash>::iterator iterator;typedef typename HashTable<K, K, KeyOfSet, Hash>::const_iterator const_iterator;pair<iterator, bool> Insert(const K& key){return _ht.Insert(key);}iterator Find(const K& key){return _ht.Find(key);}bool Erase(const K& key){return _ht.Erase(key);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}void clear(){_ht.clear();}private:HashTable<K, K, KeyOfSet, Hash> _ht;//内部结构是哈希表};}

针对迭代器遍历的优化(思路)

在STL实现的unordered_map/unordered_set中，迭代器遍历的顺序就是插入数据的顺序，而目前我们自己实现的迭代器遍历是遍历桶来完成的，有没有什么办法可以完成像STL里的那种效果呢？

 我们可以在哈希表的节点结构中再加两个成员：_linknext和_linkprev

template<class T>
struct HashNode
{T _data;//K或KVHashNode* _next;//单链表HashNode* _linknext;//下一个插入的元素HashNode* _linkprev;//上一个插入的元素HashNode(const T& data)//默认构造，为下面的new HashNode而准备:_data(data), _next(nullptr){ }
};

 _linknext是为了遍历，_linkprev是为了在删除时可以找到上一个元素

虽然这样可以在遍历时按照插入的顺序，但这也会让哈希表的结构更加复杂.....这里就不作实现了

http://www.xdnf.cn/news/1079047.html

相关文章：

  • npm 命令入门指南（前端小白版）
  • contenteditable网页富文本编辑无法选中图片
  • 从0到1实战！用Docker部署Qwerty Learner输入法的完整实践过程
  • curl for android
  • Linux多线程（十三）之【POSIX信号量基于环形队列的生产消费模型】
  • OpenCV CUDA模块设备层-----在 GPU上高效地执行两个uint类型值的最小值比较函数vmin2()
  • LeetCode 317 最短距离选址问题详解（Swift 实现 + BFS 多源遍历）
  • 高边驱动 低边驱动
  • 多模态AI Agent技术栈解析：视觉-语言-决策融合的算法原理与实践
  • Kafka生态整合深度解析：构建现代化数据架构的核心枢纽
  • JA3指纹在Web服务器或WAF中集成方案
  • 专题：2025即时零售与各类人群消费行为洞察报告|附400+份报告PDF、原数据表汇总下载
  • MacOS Safari 如何打开F12 开发者工具 Developer Tools
  • 打造一个可维护、可复用的前端权限控制方案（含完整Demo）
  • 请求未达服务端？iOS端HTTPS链路异常的多工具抓包排查记录
  • 【CSS揭秘】笔记
  • 网络基础（3）
  • HTML初学者第二天
  • 利用tcp转发搭建私有云笔记
  • Chart.js 安装使用教程
  • 【强化学习】深度解析 GRPO：从原理到实践的全攻略
  • 怎样理解：source ~/.bash_profile
  • vscode vim插件示例json意义
  • 电子电气架构 --- SOVD功能简单介绍
  • 如何系统性评估运维自动化覆盖率：方法与关注重点
  • Spark流水线数据探查组件
  • 【字节跳动】数据挖掘面试题0002：从转发数据中求原视频用户以及转发的最长深度和二叉排序树指定值
  • 计算机视觉的新浪潮：扩散模型（Diffusion Models）技术剖析与应用前景
  • 六、软件操作手册
  • 【Python】进阶 - 数据结构与算法