从哈希桶角度看 unordered_map 与 unordered_set 的实现

这篇具有很好参考价值的文章主要介绍了从哈希桶角度看 unordered_map 与 unordered_set 的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、引言

哈希函数与哈希桶是计算机科学中用于实现高效数据检索的重要工具。在之前的博客中，我们已经详细探讨了哈希的基本概念、哈希函数的构造方法以及哈希桶的工作原理等内容。在本篇博客中，我们将进一步深入探索C++中的unordered系列数据结构，并利用之前介绍的哈希桶原理进行模拟实现。

C++11提供的unordered系列数据结构，如unordered_map、unordered_set等，是STL（Standard Template Library）中提供的一组非常重要的容器。它们以哈希表为基础，通过哈希函数将键映射到存储位置，从而实现了快速的插入、删除和查找操作。这些数据结构在处理大规模数据时，能够展现出比有序容器（如map、set）更高的性能。在C++11中，提供了的4个unordered系列的关联式容器。这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

本文将使用哈希桶对C++ unordered系列数据结构进行模拟实现。文本前置内容，请点击此处：哈希技术解析：从哈希函数到哈希桶迭代器的全面指南

二、C++ unordered系列的无序关联式容器概览

1. unordered_map与unordered_multimap简介

数据结构特性：

unordered_map：C++ STL中的一个无序关联容器，它存储的元素是键值对，并且每个键在容器中唯一。其内部实现通常基于哈希表，通过哈希函数将键映射到存储位置，从而提供了常数时间复杂度的插入、删除和查找操作。
unordered_multimap：与unordered_map类似，但它允许键在容器中出现多次，即可以存储多个具有相同键的键值对。

应用场景：

unordered_map：当需要快速根据键查找对应的值时，或者当键的唯一性很重要时，unordered_map是一个很好的选择。例如，在缓存系统、词频统计等场景中，unordered_map可以高效地存储和检索键值对。
unordered_multimap：当需要存储多个具有相同键的键值对时，可以使用unordered_multimap。这在某些特定的应用场景中很有用，比如记录一个单词在文本中出现的所有位置。

2. unordered_set与unordered_multiset简介

数据结构特性：

unordered_set：是一个无序集合，它存储的元素是唯一的，不包含重复的元素。其内部实现也基于哈希表，通过哈希函数将元素映射到存储位置，从而实现了常数时间复杂度的插入、删除和查找操作。
unordered_multiset：与unordered_set类似，但它允许集合中包含重复的元素。

应用场景：

unordered_set：当需要快速检查一个元素是否存在于集合中，或者需要维护一个不包含重复元素的集合时，unordered_set是一个合适的选择。例如，在算法中去除重复元素、实现并集和交集运算等场景，unordered_set都能提供高效的解决方案。
unordered_multiset：当需要统计元素的出现次数或者需要维护一个包含重复元素的集合时，可以使用unordered_multiset。这在某些特定的数据处理和分析任务中可能会很有用。

总的来说，C++的unordered系列数据结构提供了高效的无序存储和检索机制，适用于各种需要快速处理大量数据的场景。通过合理地选择和使用这些数据结构，可以显著提高程序的性能和效率。

非unordered系列数据结构点击此处：深入解析C++树形关联式容器：map、set及其衍生容器的使用与原理-CSDN博客

三、基于哈希桶的C++ unordered系列数据结构模拟实现

1、unordered_map的模拟实现

使用自定义哈希桶存储键值对

unordered_map的简化模板类定义（注：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 hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
    
    // .... 
private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
```
模板参数：K：键（Key）的类型。V：值（Value）的类型。Hash：哈希函数（Hash Function）的类型，默认为HashFunc<K>，即默认以K来计算哈希位置。该参数也在哈希桶部分有介绍。

内部结构体 MapKeyOfT：这个结构体定义了一个调用运算符，用于从pair<K, V>中提取键。这是哈希表内部可能需要的，以便能够根据键来定位存储的元素。

迭代器类型定义：typedef语句定义了一个迭代器类型，表示指向hash_bucket::HashTable中元素的迭代器。这个迭代器类型用于公开unordered_map的接口，以便用户可以遍历集合中的元素。

私有成员：_ht是unordered_map的私有成员，其类型为hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> 。这个哈希表用于存储键值对，并根据键的哈希值来定位元素。
实现插入、查找、删除等基本操作

operator[]用于访问或插入一个键值对。如果键k已经存在于unordered_map中，则该函数返回该键对应的值的引用；如果键k不存在，则该函数插入一个新的键值对（键为k，值为V()的默认构造实例），并返回新插入值的引用：
```
V& operator[](const K& k) {
    pair<iterator, bool> it = insert({ k,V() });
    return (*it.first).second;
    //return (*((this->insert(make_pair(k, V()))).first)).second;
}
```
在这段代码中，insert成员函数被调用，它尝试插入一个键值对到unordered_map中。insert返回一个pair<iterator, bool>，其中迭代器指向新插入的元素（或已存在的元素），布尔值表示是否实际插入了新元素。由于unordered_map不允许重复的键，所以对于operator[]来说，这个布尔值总是true，除非在插入过程中发生了异常。然后，通过解引用迭代器it.first来获取键值对的引用，并返回其second成员（即值）的引用。
```
pair<iterator,bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }  
bool erase(const K& k) { return _ht.Erase(k); }  
iterator find(const K& k) { return _ht.Find(k); }
```
- insert函数接收一个pair<K, V>类型的参数，并调用_ht.Insert方法尝试将其插入哈希表中。它返回一个pair<iterator, bool>，其中迭代器指向新插入的元素（或已存在的元素），布尔值表示是否成功插入了新元素。
- erase函数接收一个键类型的参数，并调用_ht.Erase方法尝试从哈希表中删除具有该键的键值对。它返回一个布尔值，表示删除操作是否成功。
- find函数接收一个键类型的参数，并调用_ht.Find方法查找具有该键的键值对。如果找到，它返回一个指向该键值对的迭代器；否则，返回end()迭代器。

封装哈希桶迭代器

我们的哈希桶已实现了绝大部分的功能，因此我们此处仅仅调用其函数即可。

typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;	
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }

2、unordered_set的模拟实现

利用哈希桶存储唯一元素

unordered_set的简化模板类定义（注：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 hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
	//...
private:
    hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
```
模板参数：unordered_set模板接受两个类型参数，K和Hash。K是集合中元素的键类型，Hash是哈希函数类型，用于计算键的哈希值。默认情况下，如果没有提供Hash，它将使用HashFunc<K>作为哈希函数。

内部结构体SetKeyOfT：这是一个简单的函数对象（或称为仿函数），它重载了operator()以返回其输入的引用。在unordered_set的上下文中，它用于从键中提取键本身（在这种情况下，键就是元素本身）。这是为了与hash_bucket::HashTable的接口保持一致，该接口可能期望一个可以从某种类型中提取键的函数对象。

迭代器类型定义：使用typedef语句定义了一个名为iterator的类型别名，它表示指向hash_bucket::HashTable中元素的迭代器。这个迭代器类型用于公开unordered_set的接口，以便用户可以遍历集合中的元素。

私有成员变量：_ht是unordered_set的一个私有成员变量，其类型为hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>。这表示它是一个哈希表，用于存储unordered_set中的元素。键类型是const K，因为集合中的元素不应被修改（在unordered_set中，元素是唯一的，并且一旦插入就不能被修改）。SetKeyOfT用于从键中提取键，而Hash是用于计算哈希值的函数。
实现集合的基本操作
```
pair<iterator,bool> insert(const K& k) { return _ht.Insert(k); }
bool erase(const K& k) { return _ht.Erase(k); }
iterator find(const K& k) { return _ht.Find(k); }
```
- insert函数尝试在集合中插入一个元素，并返回一个pair<iterator, bool>，其中迭代器指向新插入的元素（或已存在的元素），布尔值表示是否实际插入了新元素。由于unordered_set不允许重复元素，所以如果尝试插入一个已经存在的元素，该函数不会插入新元素，而是返回指向已存在元素的迭代器，并将布尔值设置为false。

封装哈希桶迭代器

此处与unordered_map相同。

typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }

3、哈希桶及其迭代器实现的代码

该文已详细叙述哈希桶相关内容 ->深入解析C++树形关联式容器：map、set及其衍生容器的使用与原理-CSDN博客

template<class K>
struct HashFunc {
	size_t operator()(const K& key) { return (size_t)key; }
};
template<>
struct HashFunc<string> {
	size_t operator()(const string& s) {
		size_t hashi = 0;
		for (auto& e : s) {
			hashi += e;
			hashi *= 31;
		}
		return hashi;
	}
};
namespace hash_bucket
{
	template<class T>
	struct HashNode {
		HashNode<T>* _next;
		T _data;
		HashNode(const T& data) :_next(nullptr), _data(data) {}
	};

	template<class K, class T, class KeyOfT, class Hash >
	class HashTable;


	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* _ht;
		__HTIterator(Node* node, HT* ht) :_node(node), _ht(ht) {}

		T& operator*() { return _node->_data; }
		T* operator->() { return &_node->_data; }
		bool operator!=(const Self& s)const { return _node != s._node; }
		bool operator==(const Self& s) const { return _node == s._node; }

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

					hashi++;
				}
				if (hashi == _ht->_tables.size()) {
					_node = nullptr;
				}
			}
			return *this;
		}
	};


	template<class K, class T, class KeyOfT, class Hash >
	class HashTable {
		typedef HashNode<T> Node;

		template<class K, class T, class KeyOfT, class Hash>
		friend struct __HTIterator;

	public:
		typedef __HTIterator<K, T, KeyOfT, Hash> iterator;
		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); }
	

		HashTable()
		//:kot(KeyOfT()),hs(Hash())
		{
			_tables.resize(10, nullptr);
			_n = 0;
			kot = KeyOfT();
			hs = Hash();
		} 
		~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;
			}
		}
		pair<iterator,bool> Insert(const T& data) {
	
			iterator it = Find(kot(data));
			if (it != end())
				return { it,false};

			
			if (_n == _tables.size()) {
				vector<Node*> newTables(_tables.size() * 2, 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 { iterator(newnode, this),true };
		}
		bool Erase(const K& key) {
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];

			while (cur) {
				if (kot(cur->_data) == key) {
					// 删除
					if (prev)
						prev->_next = cur->_next;
					else
						_tables[hashi] = cur->_next;

					delete cur;

					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		iterator Find(const K& key) {
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur) {
				if (kot(cur->_data) == key)
					return iterator(cur, this);

				cur = cur->_next;
			}
			return iterator(nullptr, this);
		}
	private:
		vector<Node*> _tables;
		size_t _n;
		KeyOfT kot; 
		Hash hs;
	};
}

四、扩展与应用

1. 自定义哈希函数

在C++中，当使用std::unordered_set、std::unordered_map等无序容器时，哈希函数起着至关重要的作用。默认的哈希函数对于许多类型都工作得很好，但有时对于自定义类型或特殊需求，默认的哈希函数可能不是最优的，甚至可能导致性能下降或哈希冲突过多。

为特定类型设计哈希函数

对于自定义类型，需要提供一个哈希函数，该函数接受自定义类型的对象作为参数，并返回一个足够大的整数值。设计哈希函数时，需要确保：

不同的对象尽可能映射到不同的哈希值。
相同的对象总是映射到相同的哈希值。
哈希函数的计算应该尽可能快。

例如，对于一个包含字符串和整数的自定义类型，可以使用字符串的哈希值和整数的哈希值的组合作为整体的哈希值。

2. 其他unordered数据结构

除了unordered_set和unordered_map之外，标准库还提供了unordered_multimap和unordered_multiset。这两个数据结构分别允许存储具有相同键的多个值对和多个值。

unordered_multimap与unordered_map

unordered_multixxx与unordered_xxx的主要区别在于前者允许键重复，而后者不允许。具体来说：

键的重复性：unordered_map中的每个键都是唯一的，每个键只能映射到一个值。而unordered_multimap允许键的重复，这意味着同一个键可以映射到多个值。
使用场景：当你需要存储键值对，并且每个键只对应一个值时，unordered_map是合适的选择。而如果你需要存储的键值对中有多个键是相同的，并且每个键对应多个值，那么unordered_multimap更为合适。
内部实现：两者都使用哈希表作为底层数据结构，以实现快速的插入、删除和查找操作。但由于unordered_multimap允许键重复，因此在处理冲突和存储键值对时可能需要更复杂的逻辑。

unordered_multiset与unordered_set

元素的重复性：unordered_set中的每个元素都是唯一的，不允许有重复元素。而unordered_multiset则允许元素重复，即集合中可以包含多个相同的元素。
使用场景：当你需要存储一个不包含重复元素的集合时，unordered_set是合适的选择。而如果你需要存储的集合中可能包含重复的元素，那么unordered_multiset更为合适。
内部实现：两者都使用哈希表作为底层数据结构，以实现快速的插入、删除和查找操作。但由于unordered_multiset允许元素重复，因此在处理冲突和存储元素时可能需要更复杂的逻辑。

在实际应用中，根据具体的需求和数据特性选择合适的数据结构是非常重要的。例如，在需要统计词频的场景中，由于一个单词可能在文本中出现多次，因此使用unordered_multiset来存储单词和它们的出现次数会更合适。而在某些需要唯一标识的场景中，如用户ID的存储，使用unordered_set来确保ID的唯一性则更为合适。