一、泛型哈希表(开散列)结构

在上一章中简单介绍了一下unordered_map和unordered_set两个类，它们都是底层为哈希表结构的关联式容器。并且详细解释了闭散列和开散列的两种哈希表结构，得出的结论就是开散列的哈希表结构能够让有哈希冲突的元素都存放在一起，且比起闭散列的哈希结构来说，开散列的哈希结构更节省空间；所以本章我们就来封装一下unordered系列的map和set两个关联式容器。与红黑树的map和set类的封装类似，我们还是要把开散列的哈希表结构封装成一个泛型的类模版，这样就可以在这个类模版的基础上封装出unordered_map类和unordered_set类：

//节点的结构
template<class T>
struct HashNode
{
	HashNode<T>* _next;
	T _data;

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

二、unordered系列的map和set的迭代器

对于unordered_map和unordered_set的迭代器也是通过封装哈希表的迭代器来实现，则哈希表的迭代器也要实现成一个泛型的类模板，以便能封装出普通的和const版本的迭代器，但实现起来有点麻烦！

🥑🥑首先就是要去看当前节点的_next指针是否为空，如果不为空，则说明链表里还有元素，则迭代器中的节点指针改为下一个节点的指针；如果当前节点的_next指针为空，说明该桶已经遍历完，需要去数组里找下一个桶进行遍历：每当遇到一个数组元素的值不为空时，就说明该桶里就有元素，就要从这个桶的第一个元素开始往下遍历。

通过上面的分析可知，迭代器里需要有节点的指针(_node)、哈希表里的数组(_tables)、该元素所在的桶号(_hashi)。所以迭代器的实现逻辑如下：

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct __HTIterator
{
	typedef HashNode<T> Node;
	Node* _node;
	typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
	const HashTable<K, T, KeyOfT, Hash>* _pht;
	size_t _hashi;

	__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
		:_node(node)
		,_pht(pht)
		,_hashi(hashi)
	{ }

	//与上面的构造函数构成函数重载
	__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
		:_node(node)
		, _pht(pht)
		, _hashi(hashi)
	{ }

	Self& operator++()
	{
		if (_node->_next)
		{
			//如果当前节点的下一个节点存在,则移动到下一个节点
			_node = _node->_next;
		}
		else
		{
			//如果下一个节点不存在,则当前桶已经遍历完毕,要去找下一个为不空的桶的开头节点
			++_hashi;
			while (_hashi < _pht->_tables.size())
			{
				if (_pht->_tables[_hashi])
				{
					_node = _pht->_tables[_hashi];
					break;
				}
				++_hashi;
			}

			//如果遍历完所有的桶都没有元素,则节点的指针给空
			if (_hashi == _pht->_tables.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s) 
	{
		return _node != s._node;
	}
};

🍑注意：这里迭代器的实现中，operator++就是核心函数了，也是iterator的所有接口中最难的一个。其实理解了的话，就很简单。我们还要思考的一个问题就是：在哈希表中实现迭代器的话，哈希表本身的指针要怎么传给迭代器呢？其实可以通过传哈希表的this指针即可解决。或者在设计迭代器时不给哈希表的指针，而是给哈希表里的数组也可以。因为我们本来就是需要哈希表里的数组(_tables)。

2.1 哈希表与迭代器相互依赖的问题

如果迭代器是设计成给哈希表的指针这种形式，则会遇到一个问题：即等下哈希表里也会用到迭代器，那就会出现: 迭代器需要哈希表，且哈希表也需要迭代器的这种相互依赖的情况。

当一个类里面要使用到另一个类时，则编译器会往上找，如果你把HashTable定义在__HTIterator的下面时，那编译器就找不到了。那要怎么解决这里的问题呢？答案是用：前置声明。如果这里的迭代器设计成了给哈希表指针的这种形式，那就要用前置声明：

//前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;

即将上面这段代码写在__HTIterator类的前面，这样编译器就会知道你定义了HashTable这个类。

🍑上面的__HTIterator类的构造函数实现了重载，是因为如果this指针或HashTable类的对象是用const修饰的话，则在函数参数的传递过程中，要保证权限不能放大，只能平移或者缩小！所以就干脆直接将成员_pht定义成cosnt修饰的。

2.2 迭代器访问哈希表的私有成员问题

对于上面设计的迭代器，还有一个问题就是_pht要如何访问哈希表里的成员_tables呢？这时友元类就可以上场了：

//友元类(即__HTIterator是HashTable的友元类)
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct __HTIterator;

即在HashTable类里面，将__HTIterator声明为HashTable的友元类，就类似于__HTIterator是HashTable的朋友了，那__HTIterator就可以访问HashTable类里的私有成员啦！

🍎ps：如果你设计的迭代器是直接给哈希表的数组(_tables)，那就没有上面的两个问题了，因为哈希表里使用迭代器时，可以直接传递_tables成员。

三、unordered系列的map和set类的插入

对于unordered_map和unordered_set类的插入函数insert，直接通过封装哈希表的插入即可。但有一点需要注意：与以红黑树为底层结构的map和set类似，以哈希结构为底层的map和set类的插入函数的返回值也要设计成一个pair<iterator,bool>的键值对，Insert的返回值设计成pair<iterator,bool>的类型，目的是为了unordered_map类中的[ ]重载做准备的！

pair<iterator, bool> Insert(const T& data)
{
	Hash hf;
	KeyOfT kot;
	iterator it = Find(kot(data));
	if (it != end())
		return make_pair(it, false);

	//负载因子为1时,进行扩容
	if (_n == _tables.size())
	{
		vector<Node*> newTables;

		////1.二倍扩容
		//newTables.resize(_tables.size() * 2, nullptr);
		//2.按素数表里的值进行扩容
		newTables.resize(__stl_next_prime(_tables.size()));

		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				//提前记录cur的下一个节点
				Node* next = cur->_next;

				//将旧表里的元素头插到新表中
				size_t hashi = hf(kot(cur->_data)) % newTables.size();
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;

				//让cur成为下一个节点
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newTables);
	}

	size_t hashi = hf(kot(data)) % _tables.size();
	Node* newnode = new Node(data);
	//头插
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return make_pair(iterator(newnode, this, hashi), true);
}

🥦代码中的Hash和KeyOfT是两个仿函数，Hash是将关键字key进行哈希映射的仿函数；而KeyOfT是用来获取K的：即如果是unordered_set的话，KeyOfT获取到的就是K，如果是unordered_map的话，获取到的就是pair<K,V>中的K。

3.1 unordered_set类的insert

由于unordered_set类里的元素，是通过哈希函数映射存储的，所以对于unordered_set类里的元素是不能修改的！否则在查找时，通过哈希函数就找不到对应的元素了！那我们应该将unordered_set类的迭代器都设计成const版本的。这样不管是普通迭代器还是const迭代器，都不能修改其中的key值：

typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;

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

iterator end()
{
	return _ht.cend();
}

const_iterator cbegin() const
{
	return _ht.cbegin();
}

const_iterator cend() const
{
	return _ht.cend();
}

由于unordered_set类的迭代器都设计成了const版本的，则其insert接口的设计就会出问题。这跟红黑树封装set类时insert所遇到的问题是一样的。即哈希表的插入接口Insert的返回值是pair<iterator,bool>，且其中的iterator是普通迭代器；而unordered_set类中的迭代器都是const版本的，则在封装哈希表的Insert时：unordered_set类的insert用来接收哈希表Insert的返回值，由于两个pair的迭代器是不同类型，且在迭代器中没有实现迭代器构造迭代器的构造函数，这时就会报错。解决这里的方法：要么在迭代器中实现有迭代器构造迭代器的构造函数。还有一个方法如下：

pair<const_iterator, bool> insert(const K& key)
{
	auto ret = _ht.Insert(key);
	return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
}

auto是一个能自动推导变量或对象类型的关键字。则上面的ret就可以用来接收哈希表Insert的返回值。在返回时，返回值是通过构造一个pair<const_iterator,bool>类型的匿名对象来返回。

🍅注意：因为在我设计的迭代器中，所有的成员都是内置类型的，所以即使没有在迭代器中实现有(拷贝)构造函数，编译器也会生成默认的，会进行内置类型的值拷贝

3.2 unordered_map类的insert

对于unordered_map类的insert接口就没有上面的问题啦，因为其普通迭代器与const迭代器是分开的。

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>::const_iterator const_iterator;

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

iterator end()
{
	return _ht.end();
}

const_iterator cbegin() const
{
	return _ht.cbegin();
}

const_iterator end() const
{
	return _ht.cend();
}

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

但是在unordered_map类中，节点里存储的关键字是一个pair<K,V>的键值对，那其中的K就是要用来哈希映射的关键字，则K就不能修改了。所以unordered_map类里的K都要设计成不能修改的：

四、unordered_map类的[ ]重载

在unordered_map类中，节点里存储是pair<const K,V>的键值对，对于K是不能修改，但对于V来说是可以修改的，那我们就可以实现一个[ ]重载，这样能通过对象便捷的修改key对应的V：

V& operator[](const K& key)
{
	pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
	return ret.first->second;
}

const V& operator[](const K& key) const
{
	pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
	return ret.first->second;
}

🍐注意🍐：
[ ]的重载是通过unordered_map类的insert接口来实现的，因为insert的返回值是一个pair<iterator,bool>类型的键值对：当key没有在哈希表中时，则将<key, V()>这个键值对插入到哈希表中，插入成功后返回<key, V()>所在节点的迭代器及true；如果key已经在哈希表中存在，则返回表中的<key, value>构成的键值对所在节点的迭代器及false。ret.first就是找到pair<iterator,bool>中迭代器，然后再对迭代器进行解引用ret.first->second找到V。

五、unordered系列的map和set的查找

unordered_map和unordered_set类的查找，非常的简单，由于键值key都是通过哈希函数映射到存储位置的，所以查找也是通过hash(key)出来的值去对应的存储位置上进行查找，即查找也是通过封装哈希表的查找实现：

//unordered_map类的查找接口
iterator find(const K& key)
{
	return _ht.Find(key);
}

//unordered_set类的查找
const_iterator find(const K& key)
{
	auto ret =  _ht.Find(key);
	return const_iterator(ret._node, ret._pht, ret._hashi);
}

🔥需要注意：哈希表的查找接口Find的返回值是设计成迭代器的，所以unordered_set类的查找通过封装哈希表的查找接口，还是会遇到返回值类型不同，而无法构造同类型对象的情况；解决方法还是跟上面解决unordered_set类的insert接口的返回值情况类似。

六、unordered系列的map和set的删除

删除不用特别注意什么，直接封装哈希表的删除即可：

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

七、哈希表的扩容(补充)

我们在实现哈希表的底层结构时，用的是二倍扩容，其实还有一种扩容方法：素数扩容，即哈希表扩容以后的容量是素数。哈希表采用素数扩容的本质是通过数学特性优化数据分布，以减少冲突概率，从而提升查询的效率。这一设计在动态扩容时尤为重要，需通过算法维持素数容量以延续哈希表的性能优势‌。

● 数学规律‌：当哈希表容量为合数时，若待存储数据的间隔恰好是该容量的因数(或有公因数)，取模运算会呈现周期性重复，导致冲突概率显著增加。例如，容量为12时(因数为2、3、4、6)，间隔为2或3的数据会频繁映射到相同位置‌
● 素数特性‌：素数只有1和自身两个因数，能有效打破这种周期性规律，使取模结果更分散。例如，容量为11时(素数)，不同间隔的数据映射结果更随机，冲突概率更低‌

//通过素数表中的值进行扩容
inline unsigned long __stl_next_prime(unsigned long n)
{
	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,
	};

	for (size_t i = 0; i < __stl_num_primes; i++)
	{
		if (__stl_prime_list[i] > n)
			return __stl_prime_list[i];
	}
	return __stl_prime_list[__stl_num_primes - 1];
}

//哈希表的构造函数
HashTable()
{
	////方式1:开始先开十个Node类型的空间
	//_tables.resize(10);

	//方式2:以素数表中的值进行扩容
	_tables.resize(__stl_next_prime(0));
}

当然只要在扩容的地方，你可以采用二倍扩容，也可以采用上面的素数扩容都可以，素数扩容并没有很大的性能改进，只是好一点点。在闭散列或开散列中应用素数扩容都可以提升一点点哈希表的性能。

🍗🍗需要注意在Linux下哈希表应该是采用的素数扩容，但是在很多的vs编译器下，哈希表采用的应该是8倍扩容。大家可以自行下去验证。

void test_stdset()
{
	//VS下C++标准库中unordered_set是按8倍形式扩容
	unordered_set<int> s;
	size_t old = s.bucket_count();
	cout << old << endl;
	for (size_t i = 0; i < 500; i++)
	{
		s.insert(i);

		if (s.bucket_count() != old)
		{
			old = s.bucket_count();
			cout << old << endl;
		}
	}
}

程序运行结果：

🍋注意：上面的bucket_count函数是用来获取当前哈希表中所有桶的个数的。

八、自主实现的哈希表与std中的区别

上一章中，我们自己实现了哈希表的数据结构，但我们自己实现的哈希表，与标准库中的可能有所不同，哪里不同呢？看下面的代码：

void test_HTStdcomMy()
{
	int a[] = { 4,14,34,99,3,7,1,23 };

	unordered_map<int,int> um;
	for (auto& e : a)
	{
		um.insert(make_pair(e,e));
	}
	cout << "std::unordered_map的打印:";
	for (auto& kv : um)
	{
		cout << kv.first << " ";
	}
	cout << endl << endl;

	MyHashCon::unordered_map<int,int> myum;
	for (auto& e : a)
	{
		myum.insert(make_pair(e,e));
	}
	cout << "my unordered_map的打印:";
	for (auto& kv : myum)
	{
		cout << kv.first << " ";
	}
	cout << endl;
}

程序运行结果：

可以看到我们自己实现的哈希表的遍历顺序就是表中从左到右、从上到下的顺序，而标准库中的遍历顺序跟我们上面的不一样；早些的vs编译器下unordered系列的map和set会按照插入数据的顺序进行元素的遍历，这是因为他们在节点中还增加了另一个指针，用来记录插入顺序的下一个节点，相当于下面的样子：

但这种会降低哈希表的性能，因为节点中还要维护一个遍历顺序的指针，删除查找的效率就可能比我们自己实现的哈希表要慢一点点。所以现在的vs版本下unordered_map和unordered_set的遍历顺序与插入顺序‌完全无关‌了，其遍历顺序是由哈希函数和内部桶的分布来决定。
😎代码仓库：Unordered_Map&Set