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

unordered_map/set的哈希封装

article 2025/2/5 20:03:49

【C++笔记】unordered_map/set的哈希封装

🔥个人主页：大白的编程日记

🔥专栏：C++笔记

文章目录

  • 【C++笔记】unordered_map/set的哈希封装
    • 前言
    • 一. 源码及框架分析
    • 二.迭代器
    • 三.operator[]
    • 四.使用哈希表封装unordered_map/set
    • 后言

前言

哈喽，各位小伙伴大家好!上期我们讲了哈希表的底层实现。今天我们来讲一下unordered_map/set的哈希封装。话不多说，我们进入正题！向大厂冲锋
在这里插入图片描述

一. 源码及框架分析

SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只容器的名字是hash_map和hash_set，他是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，源代码在
hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中

hash_map和hash_set的实现结构框架核心部分截取出来如下：

// stl_hash_set
template <class Value, class HashFcn = hash<Value>,
	class EqualKey = equal_to<Value>,
	class Alloc = alloc>
class hash_set
{
private:
	typedef hashtable<Value, Value, HashFcn, identity<Value>,
		EqualKey, Alloc> ht;
	ht rep;
public:
	typedef typename ht::key_type key_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;
	typedef typename ht::const_iterator iterator;
	typedef typename ht::const_iterator const_iterator;
	hasher hash_funct() const { return rep.hash_funct(); }
	key_equal key_eq() const { return rep.key_eq(); }
};
// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,
	class EqualKey = equal_to<Key>,
	class Alloc = alloc>
class hash_map
{
private:
	typedef hashtable<pair<const Key, T>, Key, HashFcn,
		select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
	ht rep;
public:
	typedef typename ht::key_type key_type;
	typedef T data_type;
	typedef T mapped_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;
	typedef typename ht::iterator iterator;
	typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template <class Value, class Key, class HashFcn,
	class ExtractKey, class EqualKey,
	class Alloc>
class hashtable {
public:
	typedef Key key_type;
	typedef Value value_type;
	typedef HashFcn hasher;
	typedef EqualKey key_equal;
private:
	hasher hash;
	key_equal equals;
	ExtractKey get_key;
	typedef __hashtable_node<Value> node;
	vector<node*, Alloc> buckets;
	size_type num_elements;
public:
	typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
		Alloc> iterator;
	pair<iterator, bool> insert_unique(const value_type& obj);
	const_iterator find(const key_type& key) const;
};
template <class Value>
struct __hashtable_node
{
	__hashtable_node* next;
	Value val;
};
  • 框架分析
    这里我们就不再画图分析了，通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复用同一个hashtable实现key和key/value结构，通过一个参数T来封装map和set,hash_set传给hash_table的是key，hash_map传给hash_table的是pair<const key, value>。通过仿函数取出T中的key。同时哈希表还要多传一个哈希函数的仿函数。

二.迭代器

  • iterator实现的大框架跟list的iterator思路是一致的，用⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
  • 这里的难点是operator++的实现。iterator中有⼀个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下⼀个结点即可。如果当前桶走完了，则需要想办法计算找到下⼀个桶。这里的难点是反而是结构设计的问题，参考上面的源码，我们可以看到iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用key值计算出当前桶位置，依次往后找下⼀个不为空的桶即可。
  • begin()返回第⼀个不为空的桶中第⼀个节点指针构造的迭代器，这里end()返回迭代器可以用空表示。
  • unordered_set的iterator也不支持修改，我们把unordered_set的第⼆个模板参数改成const K即
    可， HashTable<K, const K, SetKeyOfT, Hash> _ht;
  • unordered_map的iterator不支持修改key但是可以修改value，我们把unordered_map的第二个模板参数pair的第⼀个参数改成const K即可， HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;

三.operator[]

unoredered_map实现operator[]主要是通过insert支持。
通过insert返回的pair中的迭代器，再返回迭代器中数据即可

v& operator[](const k& key)
{
	pair<iterator, bool> ret = insert({ key,v()});
	return ret.first._node->_data.second;
}

四.使用哈希表封装unordered_map/set

  • 其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂⼀点，但是
    大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K，还是pair<K, V>，
    那么insert内部进行插入时要用K对象转换成整形取模和K比较相等，因为pair的value不参与计算取模，且默认支持的是key和value⼀起比较相等，我们需要时的任何时候只需要比较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K比较相等，具体细节参考如下代码实现。
	template<class T>
	struct HashData
	{
		HashData<T>* _next;
		T _data;
		HashData(const T& key)
			:_next(nullptr)
			,_data(key)
		{}
	};
	template<class k, class T, class KeyofT, class HashFun>
	class HashTable;//前置声明,解决相互依赖
	template<class k, class T, class Ref, class Ptr, class KeyofT, class HashFun>
	struct HashIterator
	{
		using node = HashData<T>;
		using self = HashIterator<k, T, Ref, Ptr, KeyofT, HashFun>;
		using ht = HashTable<k, T, KeyofT, HashFun>;
		const ht* _ht;
		node* _node;
		HashIterator(const ht* const& HT,node* node)
			:_ht(HT)
			, _node(node)
		{}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator&()
		{
			return &_node->_data;
		}
		bool operator==(const self& tmp) const
		{
			return _node == tmp._node;
		}
		bool operator!=(const self& tmp) const
		{
			return _node != tmp._node;
		}
		self& operator++()
		{
			KeyofT kot;
			HashFun hash;
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				size_t hash0 = hash(kot(_node->_data)) % _ht->_table.size();
				hash0++;
				while (hash0<_ht->_table.size())
				{
					if (_ht->_table[hash0])
					{
						break;
					}
					else
					{
						hash0++;
					}
				}
				if (hash0 == _ht->_table.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _ht->_table[hash0];
				}
			}
			return *this;
		}
	};
	template<class k, class T, class KeyofT, class HashFun>
	class HashTable
	{
		template<class k, class T, class Ref, class Ptr, class KeyofT, class HashFun>
		friend struct HashIterator;//友元声明
	public:
		HashTable()
			:_table(__stl_next_prime(0))
			, _n(0)
		{}
		using node = HashData<T>;
		using Iterator = HashIterator<k, T, T&, T*, KeyofT, HashFun>;
		using Const_Iterator=HashIterator<k, T, const T&, const T*, KeyofT, HashFun>;
		Iterator  End()
		{
			return Iterator(this, nullptr);
		}
		Iterator  Begin()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				if (_table[i])
				{
					return Iterator(this, _table[i]);
				}
			}
			return End();
		}
		Const_Iterator End() const
		{
			return Const_Iterator(this, nullptr);
		}
		Const_Iterator Begin() const
		{
			for (int i = 0; i < _table.size(); i++)
			{
				if (_table[i])
				{
					return Const_Iterator(this, _table[i]);
				}
			}
			return End();
		}
		pair<Iterator,bool> Insert(const T& kv)
		{
			HashFun hash;
			KeyofT kot;
			Iterator it = Find(kot(kv));
			if (it!=End())
			{
				return { it,false };
			}
			if (_n * 10 / _table.size() >= 7)
			{
				vector<node*> newtable;
				newtable.resize(__stl_next_prime(newtable.size() + 1));
				for (auto& x : _table)
				{
					node* cur = x;
					x = nullptr;
					while (cur)
					{
						size_t hash0 = hash(kot(cur->_data)) % newtable.size();
						node* next = cur->_next;
						cur->_next=newtable[hash0];
						newtable[hash0] = cur;
						cur = next;
					}
				}
				_table.swap(newtable);
			}
			size_t hash0 = hash(kot(kv)) % _table.size();
			node* cur = new node(kv);
			cur->_next = _table[hash0];
			_table[hash0] = cur;
			_n++;
			return { Iterator(this,cur),true};
		}
		Iterator Find(const k& key)
		{
			HashFun hash;
			KeyofT kot;
			size_t hash0 = hash(key) % _table.size();
			node* cur = _table[hash0];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(this, cur);
				}
				cur = cur->_next;
			}
			return End();
		}
		bool Erase(const k& key)
		{
			HashFun hash;
			KeyofT kot;
			size_t hash0 = hash(key) % _table.size();
			node* cur = _table[hash0];
			node* pre = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (cur == _table[hash0])
					{
						_table[hash0] = cur->_next;
					}
					else
					{
						pre->_next = cur->_next;
					}
					return true;
				}
				else
				{
					pre = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
	private:
		vector<node*> _table;
		size_t _n;
	};


后言

这就是unordered_map/set的哈希封装。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~


http://www.kler.cn/a/532848.html

相关文章：

  • [创业之路-273]：《发现利润区》的主要内容与核心思想
  • 人类心智逆向工程：AGI的认知科学基础
  • MSP430 单独使用CCR1不触发的问题解决
  • kaggle-ISIC 2024 - 使用 3D-TBP 检测皮肤癌-学习笔记
  • Java：日期时间范围的处理
  • 软件工程概论试题五
  • 模型蒸馏原理介绍
  • 驰骋数据源设计与基础概念
  • 洛谷 P1387 最大正方形 C语言
  • 如何安全地管理Spring Boot项目中的敏感配置信息
  • C#中的if判断语句详解
  • DeepSeek本地部署的一些使用体会
  • Linux 系统上安装 Docker 并进行配置
  • OpenAI新商标申请曝光：AI硬件、机器人、量子计算全线布局？
  • 【Linux】解决 apt-key 弃用问题：GPG 直接管理密钥代替 apt-key
  • 蓝桥杯python基础算法（2-2）——基础算法（D）——进制转换*
  • 【异常记录Java-20250204】调用讯飞星火AI（Spark lite 版本）Api 授权错误问题处理
  • 电子电器架构 --- 电子电气架构设计要求与发展方向
  • 【怎么用系列】短视频戒除—1—对推荐算法进行干扰
  • 2.6学习记录
  • 结合深度学习、自然语言处理（NLP）与多准则决策的三阶段技术框架，旨在实现从消费者情感分析到个性化决策
  • Autosar-以太网是怎么运行的？（原理部分）
  • Node.js 调用 DeepSeek API 完整指南
  • java使用pcap4j进行报文发送和接收
  • Go语言指针的解引用和间接引用
  • 深入理解Node.js_架构与最佳实践