🔥个人主页：胡萝卜3.0

📖个人专栏：  《C语言》、《数据结构》 、《C++干货分享》、LeetCode&牛客代码强化刷题

《Linux系统编程》

⭐️人生格言：不试试怎么知道自己行不行

🎥胡萝卜3.0🌸的简介：

目录

一、浅看源码和框架

1.1 源码

1.2 框架

二、设计解析：如何用一个哈希表同时封装 unordered_map 和 unordered_set

2.1 设计基石：理解底层哈希表架构

2.1.1 节点的关键设计：如何同时存储 unordered_set 的 Key 与 unordered_map  的 pair

2.1.2 模板的艺术：通过模板参数决定容器类型 (T = K 或 T = pair )

2.2 核心操作：处理 map 的 pair 与 set 的 key 的插入逻辑

2.3 迭代器实现的核心挑战：桶间跳跃与桶内遍历

2.3.1 哈希表中的begin()和end()

2.4 key不支持修改的问题

2.5 核心操作：基于键的高效搜索

2.6 核心操作：基于键的快速删除

三、unordered_map和unordered_set

3.1 完整接口实现

3.2 unordered_map 的特殊操作：operator[] 的实现

完整代码

一、浅看源码和框架

1.1 源码

SGL-STL30版本源代码中没有unordered_map和unordered_set，SGL-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGL-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;
};

1.2 框架

通过上面的源码，我们不能发现，模拟实现unordered_map和unordered_set的方法是通过封装哈希表，通过封装哈希表来实现相应的功能：

由stl_hashtable.h中的第二个模板参数Key决定__hashtable_node存储的数据类型

  • 如果Key是key的类型，那__hashtable_node中存的就是一个key
  • 如果Key是key_value的类型，那__hashtable_node中存的就是一个pair<k,v>

传第一个模板参数Value是为了find和erase，对于unoredered_map和unoredered_set，调用find/erase时的函数参数都是key，所以第一个模板参数是传给find/erase等函数做参数的类型。

  • 对于unoredered_set来说两个参数是一样的
  • 但是对于unoredered_map来说就不一样了，unoredered_map在调用insert时，传的是key_value的pair对象，但是在调用find/erase时传的是key对象

需要注意的是：源码里面跟map/set源码类似，命名风格比较乱，这里的比map和set还乱，hash_set模板参数居然用的是Value命名的，hash_map用的是Key和T命名的，可见大佬有时写代码也，不规范。下面我们模拟一份自己的出来，就按自己的风格走啦~

二、设计解析：如何用一个哈希表同时封装 unordered_map 和 unordered_set

2.1 设计基石：理解底层哈希表架构

2.1.1 节点的关键设计：如何同时存储 unordered_set 的 Key 与 unordered_map  的 pair<Key, Value>

由stl_hashtable.h中的第二个模板参数Key决定__hashtable_node存储的数据类型

  • 如果Key是key的类型，那__hashtable_node中存的就是一个key
  • 如果Key是key_value的类型，那__hashtable_node中存的就是一个pair<k,v>

unordered_set实例化hashtable时第二个模板参数给的是key， unordered_map实例化hashtable是第二个模板参数给的是pair<const k,v>

2.1.2 模板的艺术：通过模板参数决定容器类型 (T = K 或 T = pair<const K, V>)

ok，既然我们已经知道源码中是使用第二模板参数来决定我哈希表中存的是什么数据，那我们也可以按照此方法对我们的哈希表进行改造：

注意：这里使用的哈希表使用的是链地址法！！！

  • 使用模板，让哈希表中的节点存一个T类型的数据（T是什么类型，底层不知道）

传入第一个模板参数k的原因是——

  • 因为find和erase传参传的是key，对于unordered_set而言调用insert/find/erase传的k和T的两个参数是一样的，但是对于unordered_map而言是不一样的，insert传的是pair，但是find/erase是key

所以我们需要传第一个模板参数！！！

我们现在来看看unordered_set和unordered_map——

由于std::unordered_map和 std::unordered_set 的底层通常使用红黑树实现，因此在我们自定义的 unoredered_map 和 unordered_set 类中，需要在私有成员区域定义一个哈希表对象作为底层容器。

  • unordered_map

  • unordered_set

这样我们就可以很清晰的看出了——

2.2 核心操作：处理 map 的 pair 与 set 的 key 的插入逻辑

ok，当我们继续调整插入代码时，还是会出现这种问题——

通过前面的学习，我们知道，Find的参数是一个key，但是我这里的是data，data的类型是什么，不知道，有可能是key，也有可能是key_value的pair，但是这里我只需要key。

那此时我们就需要在unordered_map和unordered_set中各自写这么一个仿函数——用来将各自数据中的key给提取出来，然后将这个仿函数作为第三个模板参数传给哈希表

  • unordered_map

  • unordered_set

  • 代码演示：
//插入
bool Insert(const T& data)
{
	//不允许插入相同的key
	if (Find(kot(data)))
	{
		return false;
	}
	//空间不够，当负载因子==1是需要进行扩容操作
	if (_n == _table.size())
	{
		//重新创建一个vector，将旧表中的数据重新映射到新表中
		//然后交换
		vector<node*> newtalbe(__stl_next_prime(_table.size() + 1));
		for (size_t i = 0; i < _table.size(); i++)
		{
			node* cur = _table[i];
			while (cur)
			{
				//需要保存旧表中cur的下一个节点
				node* next = cur->_next;
				//重新映射
				size_t hashi = hs(kot(cur->_data)) % newtalbe.size();
				//头插到新表中
				cur->_next = newtalbe[hashi];
				newtalbe[hashi] = cur;
				cur = next;
			}
			_table[i] = nullptr;
		}
		_table.swap(newtalbe);
	}
	//空间足够，之间算出要映射的位置
	size_t hashi = hs(kot(data)) % _table.size();
	node* newnode = new node(data);
	//头插
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	++_n;
	return true;
}

ok，我们插入一些数据看一下——

成功插入，说明我们的逻辑没有问题，接下来我们来看一下这里的迭代器是怎么实现的——

2.3 迭代器实现的核心挑战：桶间跳跃与桶内遍历

这里的迭代器的实现还是通过用一个类来封装节点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。

这里的难点就是operator++的实现。

在一个桶里面，如果当前桶还有节点，则++it就是下一个节点的指针

但是，这里的问题是：当前桶走完了，怎么找到下一个桶？

也许会有uu说，遍历一下vector，找到下一个不为空的桶就行了，确实是这样的，但是这里我是直接拷贝一份这个哈希表中的vector吗？（好像有点不太行，这里是深拷贝）。

那传vector的指针？（好像也不行，如果传vector的指针，那我就可以通过指针来修改数据了，这不是我们想要的）

ok，那我们来看一下源码：

😯，源码中的实现的封装迭代器中，不仅有节点的指针，还有哈希表的指针，通过哈希表的指针我们就可以拿到底层的vector

哈希表指针的作用 = 提供遍历所需的"上下文信息"

有了哈希表指针，迭代器就能：

  1. ✅ 知道哈希表的总容量

  2. ✅ 访问任意位置的桶

  3. ✅ 实现完整的遍历逻辑

  4. ✅ 保持O(1)的空间开销

//类模板的前置声明需要加上模板参数
//需要加上前置声明，若不加哈希表结构的前置声明，迭代器中就不认识哈希表结构
template<class k, class T, class KeyOfT, class hash>
class HashTable;
//封装迭代器
template<class k, class T,class Ref,class Ptr, class KeyOfT, class hash = hashFunc<k>>
struct HTIterator
{
	//节点
	typedef HashNode<T> node;
	//哈希表
	typedef HashTable<k, T, KeyOfT, hash> HashTable;
	typedef HTIterator<k, T, Ref, Ptr, KeyOfT, hash> Self;
	//节点的指针
	node* _node;
	//哈希表指针
	HashTable* _pht;
	HTIterator(node* node,HashTable* pht)
		:_node(node)
		,_pht(pht)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	KeyOfT kot;//拿出对应的key
	hash hs;//转换成可以进行取模的size_t 类型
	Self operator++()
	{
		//当前桶没有走完，++就是下一个节点的位置
		if (_node->_next)
		{
			_node = _node->_next;
		}
		//当前桶走完了，需要找到下一个不为空的桶的位置
		else
		{
			//首先算出当前的桶的位置
			//通过_node和哈希表指针拿到容量大小
			size_t hashi = hs(kot(_node->_data)) % _pht->_table.size();
			//hashi先++，否则还是在当前位置
			++hashi;
			//遍历vector，找下一个不为空的桶
			while (hashi < _pht->_table.size())
			{
				//找到不为空的桶，++就是该桶的第一个节点
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					break;
				}
				//没找到，继续往后找
				else
				{
					++hashi;
				}
			}
			//都遍历完了，还没有找到下一个桶，要++到end()的位置
			//在这里我们让nullptr作为end()
			if (hashi == _pht->_table.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};

ok，这里需要注意的是：

需要在迭代器的前面加上哈希表结构的模板声明，若不加哈希表结构的前置声明，迭代器中就不认识哈希表结构

我们要让迭代器这个结构成为哈希表结构的友元，否则我们拿不到哈希表的私有成员vector（或者可以在哈希表结构中写一个获取私有成员的函数，然后在迭代器中调用，也是可以的）

注意：类模板的前置声明和友元中不需要加上该类模板的缺省参数！！！也就是上面的class hash 不能写成class hash = hashFunc<k>

ok，有了迭代器的封装，我们就可以实现相应的Begin()和End()

2.3.1 哈希表中的begin()和end()
  • begin()：begin()就是第一个不为空的桶的第一个节点
  • end()：让nullptr作为end()
typedef HTIterator<k, T, T&, T*, KeyOfT, hash> Iterator;
typedef HTIterator<k, T, const T&,const T*, KeyOfT, hash> const_Iterator;

Iterator Begin()
{
	//Begin()就是第一个不为空的桶的第一个节点的位置
	//先找到第一个不为空的桶
	for (size_t i = 0; i < _table.size(); i++)
	{
		if (_table[i]) {
			return { _table[i],this };
		}
	}
	//都是空的桶，直接返回End()
	return End();
}
Iterator End()
{
	return { nullptr,this };
}
const_Iterator Begin() const	
{
	//Begin()就是第一个不为空的桶的第一个节点的位置
	//先找到第一个不为空的桶
	for (size_t i = 0; i < _table.size(); i++)
	{
		if (_table[i]) {
			return { _table[i],this };
		}
	}
	//都是空的桶，直接返回End()
	return End();
}
const_Iterator End() const
{
	return { nullptr,this };
}

加上了const迭代器，我们就需要对封装迭代器中一些地方进行修改——

由于在const迭代器中，加上了const，那么this也就被const修饰了，如果还按照原先的写法，会导致权限的放大，这是不行的，所以我们应该这么写：

  • 修改后的迭代器完整代码：
//类模板的前置声明需要加上模板参数
//需要加上前置声明，若不加哈希表结构的前置声明，迭代器中就不认识哈希表结构
template<class k, class T, class KeyOfT, class hash>
class HashTable;
//封装迭代器
template<class k, class T,class Ref,class Ptr, class KeyOfT, class hash = hashFunc<k>>
struct HTIterator
{
	//节点
	typedef HashNode<T> node;
	//哈希表
	typedef HashTable<k, T, KeyOfT, hash> HashTable;
	typedef HTIterator<k, T, Ref, Ptr, KeyOfT, hash> Self;
	//节点的指针
	node* _node;
	//哈希表指针
	const HashTable* _pht;
	HTIterator(node* node,const HashTable* pht)
		:_node(node)
		,_pht(pht)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	KeyOfT kot;//拿出对应的key
	hash hs;//转换成可以进行取模的size_t 类型
	Self operator++()
	{
		//当前桶没有走完，++就是下一个节点的位置
		if (_node->_next)
		{
			_node = _node->_next;
		}
		//当前桶走完了，需要找到下一个不为空的桶的位置
		else
		{
			//首先算出当前的桶的位置
			//通过_node和哈希表指针拿到容量大小
			size_t hashi = hs(kot(_node->_data)) % _pht->_table.size();
			//hashi先++，否则还是在当前位置
			++hashi;
			//遍历vector，找下一个不为空的桶
			while (hashi < _pht->_table.size())
			{
				//找到不为空的桶，++就是该桶的第一个节点
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					break;
				}
				//没找到，继续往后找
				else
				{
					++hashi;
				}
			}
			//都遍历完了，还没有找到下一个桶，要++到end()的位置
			//在这里我们让nullptr作为end()
			if (hashi == _pht->_table.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};

在上面的操作中，无论是unordered_set中的key还是unordered_map中的key都是可以修改的，但是库中的key是不能修改的，接下来我们来看看如何实现这个——

2.4 key不支持修改的问题

ok，这个问题还是比较容易解决的——

  • unordered_set

  • unordered_map

提醒：这里有了修改，相应的地方也要做对应的修改！！！

2.5 核心操作：基于键的高效搜索

ok，有了迭代器之后，我们就可以让查找返回相应结果的迭代器了：

  • 找到了，返回该位置的迭代器
  • 没有找到，返回end()迭代器
//查找
Iterator Find(const k& key)
{
	//算出key映射的位置
	size_t hashi = hs(key) % _table.size();
	//在指针数组的相应的指针所指向的链表中查找
	node* cur = _table[hashi];
	while (cur)
	{
		if (kot(cur->_data) == key)
		{
			return { cur,this };
		}
		cur = cur->_next;
	}
	//cur到nullptr还没找到，说明没有该key
	return { nullptr,this };
}

2.6 核心操作：基于键的快速删除

//erase删除
bool Erase(const k& key)
{
	//先算出key映射的位置
	size_t hashi = hs(key) % _table.size();
	node* cur = _table[hashi];
	node* prev = nullptr;
	//在对应的映射位置下的链表中查找到该Key
	while (cur)
	{
		if (kot(cur->_data) == key)
		{
			//删除
			if (prev == nullptr)
			{
				//第一个就是要删除的数据
				_table[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}
			delete cur;
			cur = nullptr;
			--_n;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	//cur到nullptr还没找到，说明没有该值
	return false;
}

ok，有了底层哈希表的结构，我们就可以使用该哈希表的相应功能来封装unordered_map和unordered_set的相应功能了

三、unordered_map和unordered_set

3.1 完整接口实现

  • unordered_set
namespace hash_bucket
{
	template<class k>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const k& operator()(const k& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<k, const k, SetKeyOfT>::Iterator iterator;
		typedef typename HashTable<k, const k, SetKeyOfT>::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();
		}
		//插入
		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);
		}
	private:
		//unordered_set的底层是哈希表，所以我们需要一个哈希表的对象
		HashTable<k, const k, SetKeyOfT> ht;
	};
}
  • unordered_map
namespace hash_bucket
{
	template<class k,class v>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const k& operator()(const pair<k, v>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<k, pair<const k, v>, MapKeyOfT>::Iterator iterator;
		typedef typename HashTable<k, pair<const k, v>, MapKeyOfT>::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();
		}
		bool insert(const 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);
		}
	private:
		//unordered_map的底层是哈希表，所以我们需要一个哈希表的对象
		HashTable<k, pair<const k, v>, MapKeyOfT> ht;
	};
}

3.2 unordered_map 的特殊操作：operator[] 的实现

operator[]是unordered_map 的一个重要的接口，通过前面的学习，我们这里就可以很容易实现这个 [ ] 的运算符重载：

  • 修改insert的返回值为pair<iterator,bool>

  • unordered_map中实现 operator[ ] 的运算符重载
v& operator[](const k& key)
{
	pair<iterator, bool> ret = ht.Insert({ key,v() });
	return ret.first->second;
}

ok，这里还有一个需要注意的——

我们需要将上面写的函数模板——hashFunc（将不能取模的类型变成可以取模的），放在外层，而不应该放在内层，也就是这样：

使用这种写法，我可以在定义自定义类之后，就地编写仿函数，将无法直接取模的类型转换成可哈希的整型值。

// 1. 定义自定义类（不能直接取模）
class MyClass { string name; vector<int> data; };

// 2. 局部实现转换仿函数（解决"不能取模→能取模"）
struct MyHash {
    size_t operator()(const MyClass& obj) {
        return hash<string>()(obj.name) ^ obj.data.size();
    }
};

// 3. 立即使用（无需全局修改）
unordered_map<MyClass, int, MyHash> myMap;  // ✅ 即插即用

相较于全局特化 hashFunc<k> 的传统方式，这种写法让我能在使用现场为自定义类型实现仿函数，直接将不能取模的对象转换成可用于哈希计算的整数值。

完整代码

  • hash.h
#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;
namespace hash_bucket
{
	//使用下面的函数就可以实现了建议M取不太接近2的整数次幂的一个质数（素数）
	//以保证key的每一位2进制都参与运算
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
	  53,         97,         193,       389,       769,
	  1543,       3079,       6151,      12289,     24593,
	  49157,      98317,      196613,    393241,    786433,
	  1572869,    3145739,    6291469,   12582917,  25165843,
	  50331653,   100663319,  201326611, 402653189, 805306457,
	  1610612741, 3221225473, 4294967291
	};

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		// >= n
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	//节点结构
	template<class T>
	struct HashNode
	{
		T _data;//存储的数据是T，T是什么类型，不知道
		HashNode<T>* _next;//存放下一个节点的地址
		//构造一个节点结构
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};
	template<class k>
	struct hashFunc
	{
		size_t operator()(const k& key)
		{
			return size_t(key);
		}
	};
	//上面的函数模板还是不能将string转换成整型，我们可以特化一下
	template<>
	struct hashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto& e : s)
			{
				hash += e;
				hash *= 131;
			}
			return hash;
		}
	};
	//类模板的前置声明需要加上模板参数
	//需要加上前置声明，若不加哈希表结构的前置声明，迭代器中就不认识哈希表结构
	template<class k, class T, class KeyOfT, class hash>
	class HashTable;
	//封装迭代器
	template<class k, class T,class Ref,class Ptr, class KeyOfT, class hash>
	struct HTIterator
	{
		//节点
		typedef HashNode<T> node;
		//哈希表
		typedef HashTable<k, T, KeyOfT, hash> HashTable;
		typedef HTIterator<k, T, Ref, Ptr, KeyOfT, hash> Self;
		//节点的指针
		node* _node;
		//哈希表指针
		const HashTable* _pht;
		HTIterator(node* node,const HashTable* pht)
			:_node(node)
			,_pht(pht)
		{}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		KeyOfT kot;//拿出对应的key
		hash hs;//转换成可以进行取模的size_t 类型
		Self operator++()
		{
			//当前桶没有走完，++就是下一个节点的位置
			if (_node->_next)
			{
				_node = _node->_next;
			}
			//当前桶走完了，需要找到下一个不为空的桶的位置
			else
			{
				//首先算出当前的桶的位置
				//通过_node和哈希表指针拿到容量大小
				size_t hashi = hs(kot(_node->_data)) % _pht->_table.size();
				//hashi先++，否则还是在当前位置
				++hashi;
				//遍历vector，找下一个不为空的桶
				while (hashi < _pht->_table.size())
				{
					//找到不为空的桶，++就是该桶的第一个节点
					if (_pht->_table[hashi])
					{
						_node = _pht->_table[hashi];
						break;
					}
					//没找到，继续往后找
					else
					{
						++hashi;
					}
				}
				//都遍历完了，还没有找到下一个桶，要++到end()的位置
				//在这里我们让nullptr作为end()
				if (hashi == _pht->_table.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}
		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};
	//哈希表
	template<class k, class T,class KeyOfT, class hash>
	class HashTable
	{
		//让迭代器成为友元，这样迭代器中可以访问HashTable的私有成员
		template<class k, class T, class Ref, class Ptr, class KeyOfT, class hash>
		friend struct HTIterator;
		typedef HashNode<T> node;
	public:
		typedef HTIterator<k, T, T&, T*, KeyOfT, hash> Iterator;
		typedef HTIterator<k, T, const T&,const T*, KeyOfT, hash> const_Iterator;

		Iterator Begin()
		{
			//Begin()就是第一个不为空的桶的第一个节点的位置
			//先找到第一个不为空的桶
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) {
					return { _table[i],this };
				}
			}
			//都是空的桶，直接返回End()
			return End();
		}
		Iterator End()
		{
			return { nullptr,this };
		}
		const_Iterator Begin() const	
		{
			//Begin()就是第一个不为空的桶的第一个节点的位置
			//先找到第一个不为空的桶
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) {
					return { _table[i],this };
				}
			}
			//都是空的桶，直接返回End()
			return End();
		}
		const_Iterator End() const
		{
			return { nullptr,this };
		}
		KeyOfT kot;//将data中的key取出来
		hash hs;//仿函数将不能进行取模的数据转换成size_t，用来取模
		HashTable()
			:_table(__stl_next_prime(1))
			, _n(0)
		{}
		//插入
		pair<Iterator,bool> Insert(const T& data)
		{
			//不允许插入相同的key
			if (auto ret = Find(kot(data));ret!=End())
			{
				return {ret,false};
			}
			//空间不够，当负载因子==1是需要进行扩容操作
			if (_n == _table.size())
			{
				//重新创建一个vector，将旧表中的数据重新映射到新表中
				//然后交换
				vector<node*> newtalbe(__stl_next_prime(_table.size() + 1));
				for (size_t i = 0; i < _table.size(); i++)
				{
					node* cur = _table[i];
					while (cur)
					{
						//需要保存旧表中cur的下一个节点
						node* next = cur->_next;
						//重新映射
						size_t hashi = hs(kot(cur->_data)) % newtalbe.size();
						//头插到新表中
						cur->_next = newtalbe[hashi];
						newtalbe[hashi] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtalbe);
			}
			//空间足够，之间算出要映射的位置
			size_t hashi = hs(kot(data)) % _table.size();
			node* newnode = new node(data);
			//头插
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			return { Iterator(newnode,this),true };
		}
		//查找
		Iterator Find(const k& key)
		{
			//算出key映射的位置
			size_t hashi = hs(key) % _table.size();
			//在指针数组的相应的指针所指向的链表中查找
			node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return { cur,this };
				}
				cur = cur->_next;
			}
			//cur到nullptr还没找到，说明没有该key
			return { nullptr,this };
		}
		//erase删除
		bool Erase(const k& key)
		{
			//先算出key映射的位置
			size_t hashi = hs(key) % _table.size();
			node* cur = _table[hashi];
			node* prev = nullptr;
			//在对应的映射位置下的链表中查找到该Key
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					//删除
					if (prev == nullptr)
					{
						//第一个就是要删除的数据
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					cur = nullptr;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			//cur到nullptr还没找到，说明没有该值
			return false;
		}
	private:
		//链地址法中不需要直接在表中存储数据
		//而是存在挂在表的下面的链表中，
		// 所以我们需要一个指针数组，指针是指向链表中第一个节点的指针
		vector<node*> _table;
		size_t _n;//存入的数据个数
	};
}
  • unordered_map.h
#pragma once
#include"hash.h"
namespace hash_bucket
{
	template<class k,class v, class hash = hashFunc<k>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const k& operator()(const pair<k, v>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<k, pair<const k, v>, MapKeyOfT, hash>::Iterator iterator;
		typedef typename HashTable<k, pair<const k, v>, MapKeyOfT, 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 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> ret = ht.Insert({ key,v() });
			return ret.first->second;
		}
	private:
		//unordered_map的底层是哈希表，所以我们需要一个哈希表的对象
		HashTable<k, pair<const k, v>, MapKeyOfT, hash> ht;
	};
}
  • unordered_set.h
#pragma once
#include"hash.h"
namespace hash_bucket
{
	template<class k, class hash = hashFunc<k>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const k& operator()(const k& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<k, const k, SetKeyOfT,hash>::Iterator iterator;
		typedef typename HashTable<k, const 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);
		}
		//查找
		iterator find(const k& key)
		{
			return ht.Find(key);
		}
		//删除
		bool erase(const k& key)
		{
			return ht.Erase(key);
		}
	private:
		//unordered_set的底层是哈希表，所以我们需要一个哈希表的对象
		HashTable<k, const k, SetKeyOfT, hash> ht;
	};
}
  • test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include"unordered_map.h"
#include"unordered_set.h"
namespace hash_bucket
{
	void Print(const unordered_set<int>& s)
	{
		unordered_set<int>::const_iterator it = s.begin();
		while (it != s.end())
		{
			//*it = 1;

			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void testset()
	{
		unordered_set<int> us;
		us.insert(3);
		us.insert(1000);
		us.insert(2);
		us.insert(102);
		us.insert(2111);
		us.insert(22);
		//Print(us);
		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		us.erase(22);
		for (auto& num : us)
		{
			cout << num << " ";
		}
		cout << endl;
		unordered_set<int>::iterator ret = us.find(102);
		if (ret != us.end())
		{
			cout << "找到了" << endl;
		}
		else
		{
			cout << "没有找到" << endl;
		}
	}
	void Print1(const unordered_map<string, string> dict)
	{
		unordered_map<string, string>::const_iterator it = dict.begin();
		for (auto& [k, v] : dict)
		{
			/*k += 'x';
			v += 'x';*/
			cout << k << ":" << v << endl;
		}
		cout << endl;
	}
	void testMap()
	{
		unordered_map<string, string> dict;
		dict.insert({ "string","字符串" });
		dict.insert({ "left", "左边" });
		dict.insert({ "right", "右边" });
		//Print1(dict);
		for (auto& [k, v] : dict)
		{
			//k += 'x';
			v += 'x';
			cout << k << "-" << v << endl;
		}
		cout << endl;
		// 修改
		dict["left"] = "左";

		// 插入
		dict["insert"];

		// 插入并且修改
		dict["map"] = "地图";
		dict.erase("string");
		cout << endl;
		for (auto& [k, v] : dict)
		{
			//k += 'x';
			//v += 'x';
			cout << k << "-" << v << endl;
		}
	}
}
int main()
{
	//hash_bucket::testset();
	hash_bucket::testMap();
	return 0;
}

# 散列表 # 数据结构 # c++ # 开发语言 # 人工智能 # 哈希算法 # 算法
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

导师推荐！8款一键生成论文工具测评：本科生毕业论文全攻略

avatar 2048 AI社区

【信息科学与工程学】专业领域

一个前沿课题（如自动驾驶）可能同时涉及计算机视觉、机器人、边缘计算、芯片、安全、伦理等多个领域。：如计算生物学、AI for Science、脑机接口、AI辅助药物设计。：新兴热门专业，专注于机器学习、深度学习、自然语言处理、计算机视觉等。：侧重于信息获取、处理的硬件与电路系统，包括通信、信号处理。：如计算社会科学、数字经济、算法治理、AI伦理与政策。：结合计算机技术与艺术，涉及图形学、游戏、虚拟

avatar 2048 AI社区
cover

MBA必备9个降AI率工具，高效避坑指南！

avatar 2048 AI社区