从零实现STL哈希容器：unordered_map/unordered

本篇文章是对C++学习的STL哈希容器自主实现部分的学习分享

希望也能为你带来些帮助~

那咱们废话不多说，直接开始吧！

一、源码结构分析

1. SGISTL30实现剖析

// hash_set核心结构
template <class Value, class HashFcn, ...>
class hash_set {
  typedef hashtable<Value, Value, HashFcn, identity<Value>> ht;
  ht rep;  // 复用哈希表
};

// hash_map核心结构
template <class Key, class T, ...>
class hash_map {
  typedef hashtable<pair<const Key, T>, Key, ...> ht;
};

不难看出无论是unordered_map还是unordered_set，内部的底层结构都是哈希表，基于这种事实我们可以用一句话来阐述这两个容器：

unordered_map和unordered_set是基于哈希表实现的、分别用于存储键值对和唯一键的、提供平均O(1)时间复杂度的快速查找、插入和删除操作但不保证元素的顺序性的无序关联容器。

2. HashTable关键设计

2.1 **桶结构：`vector<node*> buckets`**

核心作用
哈希表的底层存储是一个动态数组（vector），每个数组元素（称为“桶”）指向一个链表头节点（开链法解决冲突）。

数组下标：通过哈希函数将键（Key）映射到具体桶位置（hash(key) % buckets.size()）。
链表节点：同一桶内的元素以链表形式链接，解决哈希冲突（不同键映射到同一桶）。

vector<Node*> buckets;  // 如buckets[3]指向链表：NodeA -> NodeB -> nullptr

2.2 节点结构 `_hashtable_node{ next; }`

链表节点设计：每个节点需存储数据和指向下一节点的指针：

template<class T>
struct HashNode
{
	T _data;
	HashNode* _next;

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

开链法（Separate Chaining）：冲突时，新节点直接链接到桶对应的链表头部（头插法，O(1)时间）。

2.3 模板参数

在cplusplus上面两个容器的模板参数包含这几个：

模板参数	作用	示例（unordered_map场景）
`Key`	键的类型，用于哈希计算和比较	`int`、`std::string`
`T`	实际存储的数据类型（对`unordered_set`是Key，对`unordered_map`是pair）	pair<const int, string>
`Hash（KeyOfT）`	从`Value`中提取`Key`的仿函数（解决数据泛化问题）	从`pair<const int, string>`提取`int`
`Pred`	判断两个`Key`是否相等的仿函数（默认`std::equal_to`）	自定义字符串比较（如忽略大小写）
`Alloc`	内存分配器类型，用于管理`pair<const Key, T>`的内存分配（默认`std::allocator`）	自定义内存池分配器

为什么需要 Hash？

统一接口：哈希表本身不知道Value是Key（set）还是pair<Key, T>（map），需通过仿函数提取键。

// unordered_set的Hash（直接返回Key）
struct SetKeyOfT {
    const K& operator()(const K& key) { return key; }
};

// unordered_map的Hash（返回pair.first）
struct MapKeyOfT {
    const K& operator()(const pair<K, V>& kv) { return kv.first; }
};

为什么需要Pred？

自定义比较规则：默认使用operator==，但某些场景需特殊处理（如字符串比较时忽略大小写）。

struct CaseInsensitiveEqual {
    bool operator()(const string& a, const string& b) const {
        return tolower(a[0]) == tolower(b[0]);  // 仅比较首字母（示例）
    }
};

2.4 工作流程示例（插入操作）

提取Key：通过ExtractKey从Value中获取Key（如从pair<int,string>提取int）。
计算桶位置：对Key调用哈希函数，取模得到桶下标。
处理冲突：遍历桶对应的链表，用EqualKey比较是否已存在相同Key。
插入节点：若不存在，将新节点插入链表头部。

2.5 设计优势

泛化性：一套哈希表实现通过模板参数同时支持unordered_map和unordered_set。
灵活性：允许用户自定义哈希函数（Hash）和键比较规则（EqualKey）。
高效性：开链法在负载因子合理时（如0.7~1.0）保证O(1)操作。

二、模拟实现核心架构

1. 容器-哈希表关系图

不难看出，两种容器的底层是哈希表，且哈希表的底层是哈希桶以及迭代器，

同时哈希桶的底层又是节点HashNode，

因此在我们完整实现出unordered_map以及unordered_set之前，先将这两个基本元素完成就显得至关重要了

2. 关键仿函数设计：

2.1 统一键值提取接口

SetKeyOfT：K -> K
MapKeyOfT：pair<K,V> -> K

//unordered_map
struct MapKeyOfT
{
	const K& operator()(const pair<K, V>& kv)
	{
		return kv.first;
	}
};

//unordered_set
struct SetKeyOfT
{
	const K& operator()(const K& key)
	{
		return key;
	}
};

`2.2 哈希函数仿函数`

作用：将键（Key）映射为一个 size_t 类型的哈希值
（同时考虑到在unordered_map中有很多将string类型作为key的情况，我们可以为string类型做一个特化处理专门用来应对这种情况）

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& st)
	{
		size_t hashi = 0;
		for (auto e : st)
		{
			hashi += e;
		}
		return hashi;
	}
};

三、哈希表详细实现

1. 基础结构

template<class T>
struct HashNode
{
	T _data;
	HashNode* _next; //开链法解决冲突

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

template<class K, class T, class KeyOfT, class Hash >
class HashTable
{
private:
	vector<Node*> _tables; //桶数组
	size_t _n = 0; //插入元素计数
};

2. 迭代器系统实现

2.1 迭代器设计难点

跨桶遍历（核心：operator++实现）
结构设计：(当前节点指针, 哈希表指针)

2.2 关键代码

//迭代器
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> HT;
	typedef HTIterator<K, T, Ref, Ptr,KeyOfT, Hash> Self;

	//成员
	Node* _node;
	const HT* _ht;

	HTIterator(Node* node, const HT* ht)
		:_node(node)
		, _ht(ht)
	{}

	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 hashi = hs(kot(_node->_data)) % _ht->_tables.size();
			++hashi;

			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];
					break;
				}
				else
				{
					++hashi;
				}
			}
			if (hashi == _ht->_tables.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;
	}

};

2.3 容器迭代器封装

//unordered_map
typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;

//unordered_set
typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

3. 哈希表核心操作实现

Insert()：负载因子控制+扩容策略（素数表扩容）

pair<Iterator, bool> Insert(const T& data)
{
	Hash hs;
	KeyOfT kot;
	//若找得到，则已经插入过了，返回false
	//否则继续插入

	Iterator it = Find(data);
	if(it!=End())
		return {it,false};

	if (_n == _tables.size())
	{
		vector<Node*> newTables(__stl_next_prime(0), nullptr);
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = hs(kot(cur->_data)) % newTables.size();
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newTables);
	}

	size_t hashi = hs(kot(data)) % _tables.size();
	Node* newnode = new Node(data);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return { {newnode,this},true };
}

Find()：哈希定位+链表遍历

Iterator Find(const T& data)
{
	Hash hs;
	KeyOfT kot;
	size_t hashi = hs(kot(data)) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (hs(kot(cur->_data)) == hs(kot(data)))
		{
			return Iterator(cur,nullptr);
		}

		cur = cur->_next;
	}
	return End();
}

Erase()：链表节点删除

Iterator Erase(Iterator& it)
{
	if (it == End())
	{
		return End();
	}

	Hash hs;
	KeyOfT kot;

	Node* to_delete = it->_node;
	Node* prev = nullptr;
	size_t hashi = hs(kot(it->_data)) % _tables.size();
	Node* cur = _tables[hashi];

	//已经定位到目标哈希桶，找目标节点
	while (cur != to_delete && cur != nullptr)
	{
		prev = cur;
		cur = cur->_next;
	}
	
	//通常情况下不会发生
	if (cur == nullptr)
	{
		return End();
	}

	//删头节点
	if (prev == nullptr)
	{
		_tables[hashi] = cur->_next;
	}
	//正常情况
	else
	{
		prev->_next = cur->_next;
	}

	//保存下一个迭代器
	Node* next_node = cur->_next;
	Iterator next_it({ next_node,this });

	delete cur;
	--_n;

	if (next_node != nullptr)
	{
		return next_it;
	}
	else
	{
		++hashi;
		while (hashi < _tables.size() && _tables[hashi] != nullptr)
		{
			++hashi;
		}
		if (hashi < _tables.size())
		{
			return Iterator({ _tables[hashi],this });
		}
		else
		{
			return End();
		}
	}
}

4. 素数扩容机制

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;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

四、容器接口封装

1. unordered_set实现

template<class K,class Hash = Hash_Bucket::HashFunc<K>>
class  unordered_set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	//typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
	//typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

	//另一种用法，和上面的意思是一样的，但using有更多的一些用途
	using iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator;
	using const_iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator;

	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);
	}

	size_t count(const K& key)
	{
		return _ht.Count(key);
	}

	size_t size()
	{
		return _ht.Size();
	}

	bool empty()
	{
		return _ht.Empty();
	}

	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}

	iterator erase(const iterator& it)
	{
		return _ht.Erase(it);
	}

	size_t bucket_count()
	{
		return _ht.Bucket_Count();
	}

	size_t bucket_size(size_t i)
	{
		return _ht.Bucket_Size(i);
	}

private:
	Hash_Bucket::HashTable<K, const K,SetKeyOfT, Hash> _ht;
};

2. unordered_map实现

template<class K, class V, class Hash = Hash_Bucket::HashFunc<K>>
class  unordered_map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};

public:
	typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
	typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;

	iterator begin()
	{
		return _ht.Begin();
	}

	iterator end()
	{
		return _ht.End();
	}
	pair<iterator,bool> insert(const pair<K, V>& kv)
	{
		return _ht.Insert(kv);
	}

	V& operator[](const K& key)
	{
		//没有的话就创建，有的话就传迭代求所在位置
		pair<iterator, bool> ret = insert({ key,V() });
		return ret.first->second;  
	}

	iterator find(const K& key)
	{
		return _ht.Find(key);
	}

	const_iterator find(const K& key)const
	{
		return _ht.Find(key);
	}

	const V& operator[](const K& key) const
	{
		const_iterator it = _ht.Find({key,V()});
		if (it == _ht.End())
		{
			throw out_of_range("The key is out of range");
		}
		return it->second;
	}

	size_t count(const K& key)
	{
		return _ht.Count({key,V()});
	}

	size_t size()
	{
		return _ht.Size();
	}

	bool empty()
	{
		return _ht.Empty();
	}

	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}

	iterator erase(iterator& it)
	{
		return _ht.Erase(it);
	}

	size_t bucket_size(size_t i)
	{
		return _ht.Bucket_Size(i);
	}

	size_t bucket_count()
	{
		return _ht.Bucket_Count();
	}

private:
	Hash_Bucket::HashTable<K, pair<const K,V>,MapKeyOfT, Hash> _ht;
};

其中，operator[ ]为此容器的特殊支持

四、关键问题解决方案

1. 类型封装问题

通过KeyOfT仿函数屏蔽K/pair差异

2. 迭代器失效问题

扩容时整体迁移（不保留原指针，在Erase（）函数中尤为体现）

3. 哈希函数特化

满足字符串的哈希实现

五、总结

1. 设计亮点

单一哈希表支撑双容器
仿函数解决数据提取泛化

2. 性能分析

O(1)平均复杂度 vs 最差O(n)

3. 扩展方向

多线程安全支持
更优哈希冲突策略

附录

完整代码文件结构：

HashTable.h（哈希表/迭代器）
MyUnorderedSet.h
MyUnorderedMap.h

完整代码：

HashTable.h

#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace Hash_Bucket
{
	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;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	template<class T>
	struct HashNode
	{
		T _data;
		HashNode* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//特化
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& st)
		{
			size_t hashi = 0;
			for (auto e : st)
			{
				hashi += e;
			}
			return hashi;
		}
	};

	//前置声明
	template<class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >
	struct HTIterator;

	template<class K, class T, class KeyOfT, class Hash >
	class 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> ConstIterator;

		Iterator Begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return Iterator({_tables[i],this});
				}
			}
			return End();
		}

		Iterator End()
		{
			return Iterator({ nullptr,this });
		}

		//这里后面蓝色的const是修饰在_tables上的，但是这里的const _table传回给HashTable类的构造函数的时候，参数HT _ht会出现权限放大的问题
		//因此我们就在HashTable的第二个成员也就是HT _ht的类型前加上了个const，这样就避免了权限放大的问题
		ConstIterator Begin() const
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return ConstIterator({ _tables[i],this });
				}
			}
			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator({ nullptr,this });
		}

		HashTable(size_t size = __stl_next_prime(0))
			:_tables(size, nullptr)
		{}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		bool Empty()
		{
			if (Size() == 0)
			{
				return true;
			}
			return false;
		}

		size_t Size()
		{
			return _n;
		}

		pair<Iterator, bool> Insert(const T& data)
		{
			Hash hs;
			KeyOfT kot;
			//若找得到，则已经插入过了，返回false
			//否则继续插入

			Iterator it = Find(data);
			if(it!=End())
				return {it,false};

			if (_n == _tables.size())
			{
				vector<Node*> newTables(__stl_next_prime(0), nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = hs(kot(cur->_data)) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}

			size_t hashi = hs(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return { {newnode,this},true };
		}

		Iterator Find(const T& data)
		{
			Hash hs;
			KeyOfT kot;
			size_t hashi = hs(kot(data)) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (hs(kot(cur->_data)) == hs(kot(data)))
				{
					return Iterator(cur,nullptr);
				}

				cur = cur->_next;
			}
			return End();
		}

		ConstIterator Find(const T& data)const
		{
			Hash hs;
			KeyOfT kot;
			size_t hashi = hs(kot(data)) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (hs(kot(cur->_data)) == hs(kot(data)))
				{
					return ConstIterator(cur, nullptr);
				}

				cur = cur->_next;
			}
			return End();
		}

		size_t Count(const T& data)
		{
			Hash hs;
			KeyOfT kot;

			size_t hashi = hs(kot(data)) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (hs(kot(cur->_data)) == hs(kot(data)))
				{
					return 1;
				}
				cur = cur->_next;
			}
			return 0;
		}


		bool Erase(const K& key) {
			Hash hs;
			KeyOfT kot;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];

			while (cur) {
				if (kot(cur->_data) == key) {  // 仅比较键
					if (prev == nullptr) {
						_tables[hashi] = cur->_next;
					}
					else {
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		Iterator Erase(Iterator& it)
		{
			if (it == End())
			{
				return End();
			}

			Hash hs;
			KeyOfT kot;

			Node* to_delete = it->_node;
			Node* prev = nullptr;
			size_t hashi = hs(kot(it->_data)) % _tables.size();
			Node* cur = _tables[hashi];

			//已经定位到目标哈希桶，找目标节点
			while (cur != to_delete && cur != nullptr)
			{
				prev = cur;
				cur = cur->_next;
			}
			
			//通常情况下不会发生
			if (cur == nullptr)
			{
				return End();
			}

			//删头节点
			if (prev == nullptr)
			{
				_tables[hashi] = cur->_next;
			}
			//正常情况
			else
			{
				prev->_next = cur->_next;
			}

			//保存下一个迭代器
			Node* next_node = cur->_next;
			Iterator next_it({ next_node,this });

			delete cur;
			--_n;

			if (next_node != nullptr)
			{
				return next_it;
			}
			else
			{
				++hashi;
				while (hashi < _tables.size() && _tables[hashi] != nullptr)
				{
					++hashi;
				}
				if (hashi < _tables.size())
				{
					return Iterator({ _tables[hashi],this });
				}
				else
				{
					return End();
				}
			}
		}

		size_t Bucket_Count()
		{
			return _tables.size();
		}

		size_t Bucket_Size(size_t i)
		{
			if (_tables[i] == nullptr)
			{
				return 0;
			}
			else
			{
				Node* cur = _tables[i];
				size_t count = 0;
				while (cur)
				{
					++count;
					cur = cur->_next;
				}
				return count;
			}
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};

	/
	//迭代器
	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> HT;
		typedef HTIterator<K, T, Ref, Ptr,KeyOfT, Hash> Self;

		//成员
		Node* _node;
		const HT* _ht;

		HTIterator(Node* node, const HT* ht)
			:_node(node)
			, _ht(ht)
		{}

		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 hashi = hs(kot(_node->_data)) % _ht->_tables.size();
				++hashi;

				while (hashi < _ht->_tables.size())
				{
					if (_ht->_tables[hashi])
					{
						_node = _ht->_tables[hashi];
						break;
					}
					else
					{
						++hashi;
					}
				}
				if (hashi == _ht->_tables.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;
		}

	};

	
}

MyUnorderedSet.h

#pragma once
#include"HashTable.h"

namespace sp
{
	//注意这里在加上自己写的仿函数时，因为命名空间不同，需要在前面加上命名空间
	template<class K,class Hash = Hash_Bucket::HashFunc<K>>
	class  unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
		//typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

		//另一种用法，和上面的意思是一样的，但using有更多的一些用途
		using iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator;
		using const_iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator;

		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);
		}

		size_t count(const K& key)
		{
			return _ht.Count(key);
		}

		size_t size()
		{
			return _ht.Size();
		}

		bool empty()
		{
			return _ht.Empty();
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

		iterator erase(const iterator& it)
		{
			return _ht.Erase(it);
		}

		size_t bucket_count()
		{
			return _ht.Bucket_Count();
		}

		size_t bucket_size(size_t i)
		{
			return _ht.Bucket_Size(i);
		}

		void Print(const unordered_set<int>& s)
		{
			unordered_set<int>::const_iterator it = s.begin();
			while (it != s.end())
			{
				cout << *it << " ";
				++it;
			}cout << endl;
		}

	private:
		Hash_Bucket::HashTable<K, const K,SetKeyOfT, Hash> _ht;
	};
}

MyUnorderedMap.h

#pragma once
#include"HashTable.h"

namespace sp
{
	template<class K, class V, class Hash = Hash_Bucket::HashFunc<K>>
	class  unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
		typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;

		iterator begin()
		{
			return _ht.Begin();
		}

		iterator end()
		{
			return _ht.End();
		}
		pair<iterator,bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

		V& operator[](const K& key)
		{
			//没有的话就创建，有的话就传迭代求所在位置
			pair<iterator, bool> ret = insert({ key,V() });
			return ret.first->second;  
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		const_iterator find(const K& key)const
		{
			return _ht.Find(key);
		}

		const V& operator[](const K& key) const
		{
			const_iterator it = _ht.Find({key,V()});
			if (it == _ht.End())
			{
				throw out_of_range("The key is out of range");
			}
			return it->second;
		}

		size_t count(const K& key)
		{
			return _ht.Count({key,V()});
		}

		size_t size()
		{
			return _ht.Size();
		}

		bool empty()
		{
			return _ht.Empty();
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

		iterator erase(iterator& it)
		{
			return _ht.Erase(it);
		}

		size_t bucket_size(size_t i)
		{
			return _ht.Bucket_Size(i);
		}

		size_t bucket_count()
		{
			return _ht.Bucket_Count();
		}

	private:
		Hash_Bucket::HashTable<K, pair<const K,V>,MapKeyOfT, Hash> _ht;
	};
}

那么本次关于STL容器自主实现的知识分享就此结束了~

非常感谢你能够看到这里~

如果感觉对你有些许的帮助也请给我三连这会给予我莫大的鼓舞！

之后依旧会继续更新C++学习分享

那么就让我们

下次再见~

从零实现STL哈希容器：unordered_map/unordered_set封装详解

一、源码结构分析

1. SGISTL30实现剖析

2. HashTable关键设计

2.1 **桶结构：`vector<node*> buckets`**

2.2 节点结构 `_hashtable_node{ next; }`

2.3 模板参数

2.4 工作流程示例（插入操作）

2.5 设计优势

二、模拟实现核心架构

1. 容器-哈希表关系图

2. 关键仿函数设计：

2.1 统一键值提取接口

`2.2 哈希函数仿函数`

三、哈希表详细实现

1. 基础结构

2. 迭代器系统实现

2.1 迭代器设计难点

2.2 关键代码

2.3 容器迭代器封装

3. 哈希表核心操作实现

`Insert()`：负载因子控制+扩容策略（素数表扩容）

`Find()`：哈希定位+链表遍历

`Erase()`：链表节点删除

4. 素数扩容机制

四、容器接口封装

1. unordered_set实现

2. unordered_map实现

四、关键问题解决方案

1. 类型封装问题

2. 迭代器失效问题

3. 哈希函数特化

五、总结

1. 设计亮点

2. 性能分析

3. 扩展方向

网站公告

今日签到

热门文章

最新发布

从零实现STL哈希容器：unordered_map/unordered_set封装详解

一、源码结构分析

1. SGISTL30实现剖析

2. HashTable关键设计

2.1 桶结构：vector<node*> buckets

2.2 节点结构 _hashtable_node{ next; }

2.3 模板参数

2.4 工作流程示例（插入操作）

2.5 设计优势

二、模拟实现核心架构

1. 容器-哈希表关系图

2. 关键仿函数设计：

2.1 统一键值提取接口

2.2 哈希函数仿函数

三、哈希表详细实现

1. 基础结构

2. 迭代器系统实现

2.1 迭代器设计难点

2.2 关键代码

2.3 容器迭代器封装

3. 哈希表核心操作实现

Insert()：负载因子控制+扩容策略（素数表扩容）

Find()：哈希定位+链表遍历

Erase()：链表节点删除

4. 素数扩容机制

四、容器接口封装

1. unordered_set实现

2. unordered_map实现

四、关键问题解决方案

1. 类型封装问题

2. 迭代器失效问题

3. 哈希函数特化

五、总结

1. 设计亮点

2. 性能分析

3. 扩展方向

网站公告

今日签到

热门文章

最新发布

2.1 **桶结构：`vector<node*> buckets`**

2.2 节点结构 `_hashtable_node{ next; }`

`2.2 哈希函数仿函数`

`Insert()`：负载因子控制+扩容策略（素数表扩容）

`Find()`：哈希定位+链表遍历

`Erase()`：链表节点删除