【C++STL(十四)】一个哈希桶简单模拟实现unordered_map/set

2024-09-07 21:04
文章标签 简单 c++ 实现 模拟 十四 哈希 set map unordered stl

本文主要是介绍【C++STL(十四)】一个哈希桶简单模拟实现unordered_map/set，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

前言

一、改造哈希桶

改造结点类

改造主体 

模板参数改造

 迭代器(重点)

改造完整哈希桶

unordered_map模拟实现

unordered_set模拟实现

前言

前面的文章都有说unordered_map/set的底层结构就是哈希表，严格来说是哈希桶，那么接下来我们就尝试使用同一个哈希桶来模拟实现一下。整体的逻辑和一棵红黑树封装map/set类似，所以这里为了方便给出前面所实现的哈希桶

template<class K>
struct  HashFuc
{size_t operator()(const K& key){return (size_t)key;}
};
template<>
struct  HashFuc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto a : s){hash *= 131;hash += a;}return hash;}
};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 = HashFuc<K>>
class HashTable
{typedef HashNode<K, V> Node;
public:HashTable(){_h.resize(10, nullptr);_n = 0;}// 哈希桶的销毁~HashTable(){for (size_t i = 0; i < _h.size(); i++){Node* cur = _h[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_h[i] = nullptr;}_n = 0;}// 插入值为data的元素，如果data存在则不插入bool Insert(const pair<K, V>& kv){//不能存在重复if (Find(kv.first))return false;//负载因子为1时开始扩容if (_n == _h.size()){vector<Node*> newHash(_h.size() * 2, nullptr);for (size_t i = 0; i < _h.size(); i++){//将旧表的结点一个一个取下来重新映射至新表，节省空间Node* cur = _h[i];while (cur){Node* next = cur->_next;//映射至新表中Hash hs;size_t newi = hs(cur->_kv.first) % newHash.size();//哈希函数又称散列函数cur->_next = newHash[newi];newHash[newi] = cur;cur = next;}//旧表置空_h[i] = nullptr;}//交换两个表的内容即可_h.swap(newHash);}Hash hs;size_t hashi = hs(kv.first) % _h.size();//头插Node* newnode = new Node(kv);newnode->_next = _h[hashi];_h[hashi] = newnode;++_n;return true;}// 在哈希桶中查找值为key的元素，存在返回true否则返回false?Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _h.size();Node* cur = _h[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}// 哈希桶中删除key的元素，删除成功返回true，否则返回falsebool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _h.size();Node* prev = nullptr;Node* cur = _h[hashi];while (cur){if (cur->_kv.first == key){//删除的是第一个if (prev == nullptr)_h[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;return true;}else{prev = cur;cur = cur->_next;}}--_n;return false;}
private:vector<Node*> _h;size_t _n = 0;
};

可以看到。上述的哈希桶也是仅仅支持的类型是pair<K,V>这样的键值对，也就是仅可以简单模拟实现一下unordered_map,但不支持unordered_set，也就是还不够泛，所以必须先改造改造这个哈希桶，那么，来吧，开整！

一、改造哈希桶

改造结点类

这里和红黑树封装map/set如出一辙！

template <class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};

T可以是key，也可以pair<K，V>,会根据上层传来的类型去识别出实际的类型而去实例化出一个合适的模板！就很泛型！

改造主体 

模板参数改造

template<class K, class T, class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;
public:private:vector<Node*> _h;size_t _n = 0;
};

实际上和红黑树封装map/set类似，也是要带上KeyOfT这个仿函数去取对应的类型的Key来比较！

  • uordered_map的仿函数
	template<class K, class V, class Hash=HashFuc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};private:HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;};
  •  uordered_set的仿函数
	template<class K,class Hash = HashFuc<K>>class unordered_map{struct SetKeyOfT{const K& operator()(const K& key){return key;}};private:HashTable<K,K, SetKeyOfT, Hash> _ht;};

这里看到，这个改造的哈希桶参数部分就存在了四个，看官别晕！ 

 迭代器(重点)

这里的迭代器很有说法，首先就是底层依旧是结点的指针，其次就是++操作，因为是桶结构，当遍历完当前桶的所有数据时需要寻找下一个桶进行遍历，所以需要传对象的哈希表地址！

基本结构如下：

template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HTIterator<K, T, KeyOfT, Hash> Self;//为了方便而进行迭代器的重命名Node* _node;//底层结构依旧是结点指针HT* _pt;//对象哈希表地址//构造函数__HTIterator(Node* node,HT* pht):_node(node),_pt(pht){}
};

++操作的逻辑：

  • 先遍历当前桶的所有结点，直到空为止。
  • 当前桶遍历结束，寻找下一个不为空的桶的第一个结点。（具体做法：先通过哈希函数算出遍历结束的桶的位置，在循环寻找下一个不为空的桶即可）
	Self& operator++(){//先遍历当前桶if (_node->_next){//当前桶没走完，就遍历当前桶的下一个结点_node = _node->_next;}else{//当前桶走完，找下一个不为空的桶的第一个结点KeyOfT kot;Hash hs;size_t i = hs(kot(_node->_data)) % _pt->_h.size();++i;for (; _pt->_h.size(); i++){if (_pt->_h[i])break;}//遍历到最后，直接返回空if (i == _pt->_h.size()){_node = nullptr;}else_node = _pt->_h[i];}return *this;}

注意：这里仅有单向迭代器，因为桶里面的结构是单向链表，所以没有重载--操作。若需要重载可以将桶中的结构改为双向链表。这里就不这样做了，因为库里没有实现。。。

大家会发现一个问题，就是这个迭代器的参数是不是变得十分的多了？若再加上封装const迭代器的实现，那么上述的迭代器的参数就变为如下

template<class K, class T, class KeyOfT, class Hash,class Ptr,class Ref>
struct __HTIterator
{}

实际上大家会发现前面四个参数和哈希桶主体的模板参数类似，同时呢我们迭代器的实现又需要使用到哈希桶，因为要访问哈希桶的私有的内部成员！类外的函数要访问一个类的私有成员变量，可以使用友元声明，还以采用内部类的方式，这样的方式会简便很多。所以对于上述迭代器，更加简便的方式就是将迭代器封装成哈希桶的内部类。内部类天生是外部类的友元

  • 放置类外
//前置声明，因为程序是向上查找函数的，迭代器是在哈希桶的上面
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash，class Ptr,class Ref>
struct __HTIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HTIterator<K, T, KeyOfT, Hash,Ptr,Ref> Self;//为了方便而进行迭代器的重命名Node* _node;//底层结构依旧是结点指针const HT* _pt;//对象哈希表地址__HTIterator(Node* node,const HT* pht):_node(node),_pt(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//先遍历当前桶if (_node->_next){//当前桶没走完，就遍历当前桶的下一个结点_node = _node->_next;}else{//当前桶走完，找下一个不为空的桶的第一个结点KeyOfT kot;Hash hs;size_t i = hs(kot(_node->_data)) % _pt->_h.size();++i;for (; i<_pt->_h.size(); i++){if (_pt->_h[i])break;}//遍历到最后，直接放回空if (i == _pt->_h.size()){_node = nullptr;}else_node = _pt->_h[i];}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};
//哈希桶
template<class K, class T, class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;
public:typedef __HTIterator<K, T, KeyOfT, Hash,Ptr,Ref> Iterator;//友元声明template<class K, class T, class KeyOfT, class Hash，class Ptr,class Ref>friend struct __HTIterator;//………………
}
  •  内部类
template<class K, class T, class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;
public://内部类template<class Ptr, class Ref>struct __HTIterator{typedef HashNode<T> Node;typedef HashTable HT;typedef __HTIterator<Ptr, Ref> Self;//为了方便而进行迭代器的重命名Node* _node;//底层结构依旧是结点指针const HT* _pt;//对象哈希表地址__HTIterator(Node* node,const HT* pht):_node(node), _pt(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//先遍历当前桶if (_node->_next){//当前桶没走完，就遍历当前桶的下一个结点_node = _node->_next;}else{//当前桶走完，找下一个不为空的桶的第一个结点KeyOfT kot;Hash hs;size_t i = hs(kot(_node->_data)) % _pt->_h.size();++i;for (; i < _pt->_h.size(); i++){if (_pt->_h[i])break;}//遍历到最后，直接放回空if (i == _pt->_h.size()){_node = nullptr;}else_node = _pt->_h[i];}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};typedef __HTIterator<T*,T&> Iterator;//普通迭代器typedef __HTIterator<const T*, const T&> const_Iterator;//const迭代器Iterator Begin(){for (size_t i = 0; i < _h.size(); i++){Node* cur = _h[i];if (cur){//this->HashTable*return Iterator(cur, this);}}return End();}Iterator End(){return Iterator(nullptr,this);}const_Iterator Begin()const{for (size_t i = 0; i < _h.size(); i++){Node* cur = _h[i];if (cur){//const this->const HashTable*return const_Iterator(cur, this);}}return End();}const_Iterator End()const{return const_Iterator(nullptr, this);}//………………
}

可以看出当封装成内部类时，前面的四个参数可以完全省略了，共用的是哈希桶的！这样实现起来就方便很多了，但是要注意底层可以省略，但是上层一定要传四个参数，也就是模拟实现unordered_map那层。

 还需要注意的一个细节，就是因为要传入对于哈希表的地址，即this指针，而const迭代器修饰的就是const this，那么底层的哈希地址就需要使用const指针修饰，因为如果不用const的话，当传入const this时会存在权限放大的问题。

typedef HashTable HT;
const HT* _pt;//对象哈希表地址

改造完整哈希桶

#include <iostream>
#include <vector>
using namespace std;template<class K>
struct  HashFuc
{size_t operator()(const K& key){return (size_t)key;}
};
template<>
struct  HashFuc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto a : s){hash *= 131;hash += a;}return hash;}
};template <class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};template<class K, class T, class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;
public://内部类template<class Ptr, class Ref>struct __HTIterator{typedef HashNode<T> Node;typedef HashTable HT;typedef __HTIterator<Ptr, Ref> Self;//为了方便而进行迭代器的重命名Node* _node;//底层结构依旧是结点指针const HT* _pt;//对象哈希表地址__HTIterator(Node* node, const HT* pht):_node(node), _pt(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//先遍历当前桶if (_node->_next){//当前桶没走完，就遍历当前桶的下一个结点_node = _node->_next;}else{//当前桶走完，找下一个不为空的桶的第一个结点KeyOfT kot;Hash hs;size_t i = hs(kot(_node->_data)) % _pt->_h.size();++i;for (; i < _pt->_h.size(); i++){if (_pt->_h[i])break;}//遍历到最后，直接放回空if (i == _pt->_h.size()){_node = nullptr;}else_node = _pt->_h[i];}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};typedef __HTIterator<T*,T&> Iterator;//普通迭代器typedef __HTIterator<const T*, const T&> const_Iterator;//const迭代器Iterator Begin(){for (size_t i = 0; i < _h.size(); i++){Node* cur = _h[i];if (cur){//this->HashTable*return Iterator(cur, this);}}return End();}Iterator End(){return Iterator(nullptr,this);}const_Iterator Begin()const{for (size_t i = 0; i < _h.size(); i++){Node* cur = _h[i];if (cur){//const this->HashTable*return const_Iterator(cur, this);}}return End();}const_Iterator End()const{return const_Iterator(nullptr, this);}HashTable(){_h.resize(10, nullptr);_n = 0;}// 哈希桶的销毁~HashTable(){for (size_t i = 0; i < _h.size(); i++){Node* cur = _h[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_h[i] = nullptr;}_n = 0;}// 插入值为data的元素，如果data存在则不插入pair<Iterator,bool> Insert(const T& data){KeyOfT kot;//取对应类型的key//不能存在重复Iterator it = Find(kot(data));if (it!=End())return make_pair(it,false);//负载因子为1时开始扩容if (_n == _h.size()){vector<Node*> newHash(_h.size() * 2, nullptr);for (size_t i = 0; i < _h.size(); i++){//将旧表的结点一个一个取下来重新映射至新表，节省空间Node* cur = _h[i];while (cur){Node* next = cur->_next;//映射至新表中Hash hs;size_t newi = hs(kot(cur->_data)) % newHash.size();//哈希函数又称散列函数cur->_next = newHash[newi];newHash[newi] = cur;cur = next;}//旧表置空_h[i] = nullptr;}//交换两个表的内容即可_h.swap(newHash);}Hash hs;size_t hashi = hs(kot(data)) % _h.size();//头插Node* newnode = new Node(data);newnode->_next = _h[hashi];_h[hashi] = newnode;++_n;return make_pair(Iterator(newnode,this), true);}//在哈希桶中查找值为key的元素，存在返回true否则返回falseIterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _h.size();Node* cur = _h[hashi];while (cur){if (kot(cur->_data) == key){return Iterator(cur, this);}cur = cur->_next;}return Iterator(nullptr, this);}// 哈希桶中删除key的元素，删除成功返回true，否则返回falsebool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _h.size();Node* prev = nullptr;Node* cur = _h[hashi];while (cur){if (kot(cur->_data) == key){//删除的是第一个if (prev == nullptr)_h[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;return true;}else{prev = cur;cur = cur->_next;}}--_n;return false;}size_t Size(){return _n;}bool empty()const{return _n == 0;}
private:vector<Node*> _h;size_t _n = 0;
};

unordered_map模拟实现

实际上就是封装哈希桶，没啥的，重点在底层哈希桶结构，这里直接给出完整代码

#include "HashTable.h"
namespace um
{template<class K, class V, class Hash=HashFuc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashTable<K, pair<K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename HashTable<K, pair<K, V>, MapKeyOfT, Hash>::const_Iterator const_iterator;pair<iterator,bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin()const{return _ht.Begin();}const_iterator end()const{return _ht.End();}iterator Find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}size_t size(){return _ht.Size();}bool empty(){return _ht.empty();}//重载[]V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));iterator it = ret.first;return it->second;}private:HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;//底层对哈希桶的封装};

unordered_set模拟实现

namespace us
{template<class K,class Hash = HashFuc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, K, SetKeyOfT, Hash>::Iterator iterator;typedef typename HashTable<K, K, SetKeyOfT, Hash>::const_Iterator const_iterator;iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin()const{return _ht.Begin();}const_iterator end()const{return _ht.End();}pair<iterator,bool> insert(const K& key){return _ht.Insert(key);}bool erase(const K& key){return _ht.Erase(key);}size_t size(){return _ht.Size();}bool empty(){return _ht.empty();}private:HashTable<K,K, SetKeyOfT, Hash> _ht;};
}

好了，今天的分享就到这里，如果对你有所帮助，欢迎点赞+关注!

这篇关于【C++STL(十四)】一个哈希桶简单模拟实现unordered_map/set的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1146155。

相关文章

分布式锁在Spring Boot应用中的实现过程

分布式锁在Spring Boot应用中的实现过程

《分布式锁在SpringBoot应用中的实现过程》文章介绍在SpringBoot中通过自定义Lock注解、LockAspect切面和RedisLockUtils工具类实现分布式锁,确保多实例并发操作... 目录Lock注解LockASPect切面RedisLockUtils工具类总结在现代微服务架构中，分布
阅读更多...
Java使用Thumbnailator库实现图片处理与压缩功能

Java使用Thumbnailator库实现图片处理与压缩功能

《Java使用Thumbnailator库实现图片处理与压缩功能》Thumbnailator是高性能Java图像处理库,支持缩放、旋转、水印添加、裁剪及格式转换,提供易用API和性能优化,适合Web应... 目录1. 图片处理库Thumbnailator介绍2. 基本和指定大小图片缩放功能2.1 图片缩放的
阅读更多...
Python使用Tenacity一行代码实现自动重试详解

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门：一行代码实现优雅重试精细控制：让重试按我
阅读更多...
Redis客户端连接机制的实现方案

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连
阅读更多...
Python实现网格交易策略的过程

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略，其核心思想是在价格上下预设多个“网格”，当价格触发特定网格时执行买
阅读更多...
python设置环境变量路径实现过程

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法：临时设置（Windows用`set`,Linux/macOS用`export`）、永久设置（系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量（适用于当前会话）永久设置环境变量（Windows系统
阅读更多...
python运用requests模拟浏览器发送请求过程

python运用requests模拟浏览器发送请求过程

《python运用requests模拟浏览器发送请求过程》模拟浏览器请求可选用requests处理静态内容,selenium应对动态页面,playwright支持高级自动化,设置代理和超时参数,根据需... 目录使用requests库模拟浏览器请求使用selenium自动化浏览器操作使用playwright
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2