C++ 数据结构之哈希表及其相关容器

发布于：2025-09-02 ⋅ 阅读:(22) ⋅ 点赞:(0)

一.unordered_map/map和unordered_set/set

1.unordered_set与set

unordered系列是原set/map的改良，它们在不同的场景有其不同的应用。接下来我们从底层实现，参数，使用等方面简述它们的异同。

1.底层实现

unordered_set与set最直接的区别，我们从名称上其实就看的出来——前者是无序的，而后者是有序的。这一点最直接的差异就来源于它们的底层实现是不同的：unordered_set底层由哈希表实现，增删查改效率为O(1)，但由于其哈希函数的特点所以会导致数据并不有序。而set底层是红黑树（一种二叉搜索树），迭代器中序遍历的结果是一个有序的序列。特别需要注意的是，set的迭代器是双向迭代器，而unordered系列的容器均是单向迭代器。

2.参数

对于unordered_set，它的参数明显比set更多。

• unordered_set的声明如下，Key就是unordered_set底层关键字的类型

• unordered_set默认要求Key⽀持转换为整形，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀

持将Key转成整形的仿函数传给第⼆个模板参数

• unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持

将Key⽐较相等的仿函数传给第三个模板参数

• unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给

第四个参数。

• ⼀般情况下，我们都不需要传后三个模板参数

template < class Key, //
unordered_set::key_type/value_type
class Hash = hash<Key>, // unordered_set::hasher
class Pred = equal_to<Key>, // unordered_set::key_equal
class Alloc = allocator<Key> // unordered_set::allocator_type
> class unordered_set;

3.使用

• 查看⽂档我们会发现unordered_set的⽀持增删查且跟set的使⽤⼀模⼀样，关于使⽤我们这⾥就不再赘述和演⽰了。

• unordered_set和set的第⼀个差异是对key的要求不同，set要求Key⽀持⼩于⽐较，⽽

unordered_set要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_set的这个两点要求得

后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

• unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set

是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代

器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。

具体的使用与性能差异可以用以下用例

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<set>
#include<unordered_set>

using namespace std;

void test_set1()
{
	unordered_set<int> s = { 3,1,6,7,8,2,1,1,5,6,7,6 };
	unordered_set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

void test_set2()
{
	const size_t N = 10000000;
	unordered_set<int> us;
	set<int> s;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand()); // N比较大时，重复值比较多
		//v.push_back(rand() + i); // 重复值相对少
		v.push_back(i); // 没有重复，有序
	}

	
	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert:" << end1 - begin1 << endl;

	size_t begin2 = clock();
	us.reserve(N);
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl;

	cout << "插入数据个数：" << s.size() << endl;
	cout << "插入数据个数：" << us.size() << endl << endl;

	int m1 = 0;
	size_t begin3 = clock();
	for (auto e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << "->" << m1 << endl;

	int m2 = 0;
	size_t begin4 = clock();
	for (auto e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	size_t end4 = clock();
	cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;

	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase:" << end5 - begin5 << endl;
	size_t begin6 = clock();

	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
}

结果：

2.unordered_map与map

1.底层实现

map底层是红黑树实现，unordered_map是哈希表实现，他们带来的差异上面已经介绍过，这里不再赘述。

2.参数

• 查看⽂档我们会发现unordered_map的⽀持增删查改且跟map的使⽤⼀模⼀样，关于使⽤我们这

⾥就不再赘述和演⽰了。

• unordered_map和map的第⼀个差异是对key的要求不同，map要求Key⽀持⼩于⽐较，⽽

unordered_map要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_map的这个两点要求

得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求

• unordered_map和map的第⼆个差异是迭代器的差异，map的iterator是双向迭代器，

unordered_map是单向迭代器，其次map底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有

序的，所以map迭代器遍历是Key有序+去重。⽽unordered_map底层是哈希表，迭代器遍历是

Key⽆序+去重。

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

3.使用

可以用以下用例测试两者性能

pair<iterator,bool> insert ( const value_type& val );
size_type erase ( const key_type& k );
iterator find ( const key_type& k );
mapped_type& operator[] ( const key_type& k );

3.map/set与unordered_map/unordered_set总结

1.使用与特性 

基于底层实现的不同，它们在用法和特性上表现出巨大差异。

特性 set / map unordered_set / unordered_map
元素顺序 有序（按key排序） 无序（顺序不确定，取决于哈希函数）
操作时间复杂度 查找、插入、删除：O(log n) 平均 O(1)，最坏 O(n)
迭代器稳定性 迭代器始终有效（除非指向元素被删除） Rehash 后迭代器会失效
内存占用 通常较少（树节点开销） 通常较高（需要维护桶数组，可能存在空闲桶）
所需键类型要求 必须定义 < 操作符或提供自定义比较函数 必须定义 == 操作符和可计算哈希值（或提供自定义函数）
使用场景 需要元素有序；需要按顺序遍历；需要最小/最大元素 需要极快的查找速度，且不关心顺序

关键点详解：

  1. 有序 vs 无序:

    • 遍历一个 set<int> s{5, 1, 4, 2, 3}，输出顺序是 1, 2, 3, 4, 5。

    • 遍历一个 unordered_set<int> us{5, 1, 4, 2, 3}，输出顺序可能是任意顺序，例如 3, 5, 1, 4, 2，并且每次编译器的版本或者容器的状态不同都可能变化。

  2. 性能差异:

    • 在大多数情况下，unordered_* 的查找速度远快于 *。如果你的主要操作是查找，并且数据量很大（例如超过10万个元素），unordered_map 的性能优势会非常明显。

    • 但是，unordered_* 的 O(1) 是“平均常数时间”，其性能依赖于哈希函数的质量和负载因子（load factor）。如果哈希函数很差，导致冲突很多，性能会下降。而 map 的 O(log n) 是非常稳定的。

  3. 迭代器失效:

    • 对于 map，插入和删除操作通常不会使已有的迭代器失效（除了当前被删除元素的迭代器）。

    • 对于 unordered_map，插入操作可能导致 rehash（即扩容，重新分配桶数组并重新映射所有元素）。一旦发生 rehash，所有的迭代器都会失效。这是一个非常重要的区别，在遍历过程中插入元素的风险很高。

2.参数与使用选择

方面 set / map (红黑树) unordered_set / unordered_map (哈希表)
底层结构 红黑树 哈希表
排序性 有序 无序
查找效率 稳定，O(log n) 平均极快，O(1)，最坏O(n)
内存 通常更紧凑 通常有额外开销
迭代器失效 更安全（除非删除，否则不失效） 不安全（rehash 后全部失效）
关键要求 键必须可比较 (<) 键必须可哈希且可相等比较 (==)

如何选择：

  • 你需要元素的顺序吗？

    • 是 -> 选择 set 或 map。

    • 否 -> 优先考虑 unordered_set 或 unordered_map，尤其当查找性能是关键时。

  • 你更关心最坏情况下的性能还是平均性能？

    • 最坏情况（如实时系统）-> 稳定的 set 或 map 更可靠。

    • 平均情况 -> unordered_set 或 unordered_map 通常更快。

  • 你的键类型是什么？

    • 如果是自定义类型，你需要为 set/map 提供比较函数（重载 < 或自定义仿函数），或者为 unordered_set/unordered_map 提供哈希函数和相等比较函数（重载 == 或自定义仿函数）。后者通常更麻烦一些。

二.哈希与哈希表

从上面的介绍我们得知，unordered系列的容器底层由哈希表实现，于是我们就深入了解以下哈希与哈希表。

1.哈希的概念

哈希(Hash)即散列，它可以看作一种设计理念，后续我们讲到的布隆过滤器也是用哈希表实现的。它的核心思想就是将存储的数据Key以某种映射关系映射到空间上便于存储。查找时根据Key即可查到相应正确的位置。

2.哈希表

哈希表的概念比较零碎，不过我们大致可以分为以下几点：以何种规则进行映射(哈希函数的选取)，处理哈希冲突的方式(各显神通)。首先来讲一些专业术语吧。

1.直接定址法

当一些待处理的数据范围较为集中时，使用这种方法是最简单高效的。⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法就是用关键字Key计算出一个绝对位置或者相对位置来进行数据的存储，其实这样的思想我们早在计数排序中用到过。

class Solution {
public:
int firstUniqChar(string s) {
// 每个字⺟的ascii码-'a'的ascii码作为下标映射到count数组，数组中存储出现的次数
int count[26] = {0};
// 统计次数
for(auto ch : s)
{
count[ch-'a']++;
} 
for(size_t i = 0; i < s.size(); ++i)
{
if(count[s[i]-'a'] == 1)
return i;
} 
return -1;
}
}

2.哈希冲突

直接定址法的缺点也⾮常明显，当关键字的范围⽐较分散时，就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0, 9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M >= N)，那么就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计算出的值必须在[0, M)之间。

这里存在一个很明显的现象，两个不同的key可能会被映射到同一个地方，这种现象叫做哈希冲突。这是哈希表中无法避免的一个现象，但我们需要尽可能地减少哈希冲突地产生(通过控制较好的哈希函数)以及发生了哈希冲突合理的解决办法。

3.负载因子

若一个哈希表中存储了N个数据，而开了M个空间，那么可以定义负载因子(load factor)为\frac{N}{M}。从感觉上可以意识到，负载因子越大，空间地利用率越高，但却越容易发生哈希冲突。我们后续需要根据负载因子这个重要地性质处理哈希表。

4.将关键字转为整数

其实上面讲直接定址法会发现一个比较鸡肋的事情，那就是这种结构只能用来处理整型的数据。。。不过这也侧面让我们理解到，若想要处理不同类型的数据，就都需要将关键字转换为整数去处理。因此unordered_set/map中有Hash这样的模板参数。

template < class Key, //
unordered_set::key_type/value_type
class Hash = hash<Key>, // unordered_set::hasher
class Pred = equal_to<Key>, // unordered_set::key_equal
class Alloc = allocator<Key> // unordered_set::allocator_type
> class unordered_set;

5.哈希函数

一个好的哈希函数应该将N个数据均匀分散地分布映射在M个空间中，然而现实中却很难实现这个目的，我们需要尽量的将哈希函数向理想化靠近。

1.除留余数法/除法散列法

除法散列法也叫做除留余数法，顾名思义，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

在利用除法散列法进行处理时，应该尽量避免使用2的幂次方或者10的幂次方作为M。比如：

很显然这两个是不同的数，但他们的后16位是相同的。因此他们采用2^16及以下的M都会映射到同一个位置。。对于10的幂次方则更明显，11223和123%100均会得到23这个位置。因此建议在取M时取一个不太接近2的整数次幂的一个素数。

Java的HashMap其实底层采用的就是2的整数次幂，但它不会单单只做这一步操作。例如：M是2^16次⽅，本质是取后16位，那么⽤key’ =key>>16，然后把key和key' 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。

在计算hashi时这样处理：通过hash&(2^n-1)-1取到后n位，为了使更多位参与运算，令前32-n位异或。

size_t HashFunc(const K& key)
{
	size_t hash = key & (_tables.size() - 1);
	hash ^= (hash >> (32_m));
	return hash;
}
2.乘法散列法

 乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路第⼀步：⽤关键字 K 乘上常数 A (0<A<1)，并抽

取出 k*A 的⼩数部分。第⼆步：后再⽤M乘以k*A 的⼩数部分，再向下取整。

其中floor表⽰对表达式进⾏下取整，A∈(0,1)，这⾥最重要的是A的值应该如何设定，Knuth认为 (⻩⾦分割点])⽐较好。h(key) = floor(M × ((A × key)%1.0))A = ( 5 - 1)/2 = 0.6180339887....

乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A*key

= 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 =

669.6366651392，那么h(1234) = 669。

3.全域散列法

 如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集，⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决⽅法⾃然是⻅招拆招，给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列。

，P需要选⼀个⾜够⼤的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。

需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查

改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，

查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。

6.处理哈希冲突

在实践中一般还是选择除法散列法进行处理，但是无论选择什么哈希函数都无法完全根除冲突的问题，因此对哈希冲突采取合理的处理方式也十分重要。

1.开放地址法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。
线性探测

从发生冲突的位置开始依次向后寻找，直到找到有空位的空间。若设初始映射的空间为hash0，则hash0=key%M，依次寻找的空间即为hashi=(hash0+i)%M(i=1,2,3...)。因为负载因子小于1，所以至多经过M-1次探测一定可以找到空闲位置。

线性探测的⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，

hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位

置，这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。

下面是一个序列为{19,30,5,36,13,20,21,12}，M=11的例子。

线性探测的实现

首先我们来定义数据类型。每个空间应该存储一个pair类型的数据，并且整体的哈希表用vector来表示就十分方便。

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

但是这里选择引入一个枚举类型State，并且给出了三种状态：EXIST，EMPTY，DELETE。这又是什么用意呢？假设我们不设置这个State值：

如果此时将下标为9处的30删除，那么这个位置就为空。但是20这个值是产生了哈希冲突之后被挤到下标为10的位置的(它原本应该在9这个位置，但被30霸占了)，此时再去查询20这个数其实是查不到的，因为查找的结束条件肯定为遇到空结束否则会一直死循环。因此State状态值的作用就体现出来了：在遇到因DELETE当前位置为空时会继续查找，但是遇到EMPTY就不会再查找了。这样就解决了这个问题。

接着我们再来看插入，查找和删除的逻辑。最重要的其实是插入的逻辑：线性探测的过程不必多说，最需要注意的是这里的扩容问题。什么情况下需要扩容？由大佬们的研究发现当负载因子超过0.7的时候就极容易发生大量的哈希冲突。因此我们需要在负载因子=0.7左右进行扩容。需要注意的是，这里的newht是一个临时变量，为了防止出作用域销毁，我们使用swap函数交换资源。

template<class K, class V>
class HashTable
{
public:
	HashTable()
		:_tables(__stl_next_prime(0))
		,_n(0)
	{}
    //这一坨数据是为了扩容时找到一个最符合需求的数并且是素数
    //因为上面的讲解提到了，用除法散列法最好模一个离2的幂次方较远的素数
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		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
		};
		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;
	}

	bool Insert(const pair<K, V>& kv)
	{    
        //这里的哈希表是不支持重复数据的
		if (Find(kv.first))
			return false;

		// 负载因子 >= 0.7扩容
		if (_n*10 / _tables.size() >= 7)
		{

			HashTable<K, V> newht;
			//newht._tables.resize(_tables.size() * 2);
            //先预留空间
			newht._tables.resize(__stl_next_prime(_tables.size()+1));
             //遍历旧表，相当于做了一个深拷贝的工作
            //值得注意的是这里的逻辑复用了insert，为的是后续其他探测方法的实现   
			for (auto& data : _tables)
			{
				// 旧表的数据映射到新表
				if (data._state == EXIST)
				{
					newht.Insert(data._kv);
				}
			}
            //交换
			_tables.swap(newht._tables);
		}
        //先找到当前key的原始位置hash0
		size_t hash0 = kv.first % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		int flag = 1;
        //这里就是哈希冲突的过程
		while (_tables[hashi]._state == EXIST)
		{
			// 线性探测，取模是解决回绕问题
			hashi = (hash0 + i) % _tables.size();
			++i;

		}
        //插入数据
		_tables[hashi]._kv = kv;
        //修改状态
		_tables[hashi]._state = EXIST;
        //修改数据个数
		++_n;

		return true;
	}
    
    //查找的逻辑是返回结点信息，包括pair类型和状态值State
	HashData<K, V>* Find(const K& key)
	{
		size_t hash0 = key % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._state == EXIST 
				&& _tables[hashi]._kv.first == key)
			{
				return &_tables[hashi];
			}

			// 线性探测
			hashi = (hash0 + i) % _tables.size();
			++i;
		}

		return nullptr;
	}

	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			return true;
		}
		else
		{
			return false;
		}
	}

private:
	vector<HashData<K, V>> _tables;
	size_t _n;  // 记录数据个数
};

二次探测

上面的线性探测很容易会出现堆积/群集的现象，原因就出在每次在进行探测是都查找相邻的位置，如果采用二次的探测方式，散列程度会越来越大，比起线性探测的争抢位置现象稍微有所缓解。因此我们需要修改的只有线性探测的部分，其他部分可以直接复用。

• 从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置；

• , hash0位置冲突了，则⼆次探测公式为：

• ⼆次探测当 hashi = (hash0 - i2)%M 时，当hashi<0时，需要hashi += M

• 下⾯演⽰ {19,30,52,63,11,22} 等这⼀组值映射到M=11的表中。

二次探测的实现

size_t hash0 = kv.first % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag = 1;
while (_tables[hashi]._state == EXIST)
{
    //这里的flag用于控制正负
	hashi = (hash0 + (i*i*flag)) % _tables.size();
    //因为flag会让hashi变负，变负会回绕
     //为了正确地回绕，加上当前地数据个数即可
	if (hashi < _tables.size())
		hashi += _tables.size();

	if (flag == 1)
	{
		flag = -1;
	}
	else
	{
		++i;
		flag = 1;
	}
}
2.处理key不为整数的情况

由上面可知，不管是取模运算也好，右移操作也罢，这都是基于处理的key是一个整数的基础。但现实中我们需要处理很多key不为整数的情况，例如double，string甚至自定义类型，这时候又怎么办呢？现在再回看unordered系列容器的定义又会有新发现——使用仿函数。

template < class Key, //
unordered_set::key_type/value_type
class Hash = hash<Key>, // 将不为整数的key转为key
class Pred = equal_to<Key>, // unordered_set::key_equal
class Alloc = allocator<Key> // unordered_set::allocator_type
> class unordered_set;

既然要用仿函数处理，HashTable内部我们要做一些修改。也就是涉及到取模运算的位置(线性探测等操作)需要修改。例如这里kv.first用仿函数hash去处理。

Hash hash;
size_t hash0 = hash(kv.first) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag = 1;

接着我们修改HashTable的参数，需要把hash这个仿函数传进来

template<class K, class V, class Hash = HashFunc<K>>
class HashTable{
.....
};

然后我们来写这个仿函数。在使用时我们可以自己显式传仿函数，但我们不妨用一下前面学到的知识——模板特化，这样针对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& s)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : s)
		{    
            //这里不难看出我们是把string每一个字符的ascii码相加
            //但这样很容易发生冲突，比如abcd和aadd得到的哈希值相同
            //于是采用大佬的处理方法，每相加一个字符，就乘一个数(这里选了131)
            //这样即使是相同字符不同顺序得到的哈希值也不同，很好的避免了冲突
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};

不难看出，我们这里的HashTable参数中的Hash做了一个第一层映射的工作，第二层工作才是把key映射到存储空间中。

3.处理值相等的问题

因为unordered系列的容器需要实现Find函数，因此我们可能需要去对相等逻辑进行复写。但是这个工作不方便直接对源代码进行修改，所以也跟上面处理key不为整数一样使用仿函数处理即可。于是就有了unordered系列中的模板参数。

template < class Key, //
unordered_set::key_type/value_type
class Hash = hash<Key>, // 将不为整数的key转为key
class Pred = equal_to<Key>, // 处理相等逻辑
class Alloc = allocator<Key> // unordered_set::allocator_type
> class unordered_set;

就拿Date类做例子

template<class K>
struct DateEqual {
    bool operator()(const K& rhs)
    {
        return _year == rhs.year && _month == rhs.month && _day == rhs.day;
    }
};
4.开放地址的完整实现
#pragma once
#include<vector>

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

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)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	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
	};
	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;
}

namespace open_address
{
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
			:_tables(__stl_next_prime(0))
			, _n(0)
		{}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			// 负载因子 >= 0.7扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				//vector<HashData<K, V>> newtables(_tables.size()*2);
				//for (auto& data : _tables)
				//{
				//	// 旧表的数据映射到新表
				//	if (data._state == EXIST)
				//	{
				//		size_t hash0 = data._kv.first % newtables.size();
				//		// ...
				//	}
				//}

				//_tables.swap(newtables);

				HashTable<K, V, Hash> newht;
				//newht._tables.resize(_tables.size() * 2);
				newht._tables.resize(__stl_next_prime(_tables.size() + 1));

				for (auto& data : _tables)
				{
					// 旧表的数据映射到新表
					if (data._state == EXIST)
					{
						newht.Insert(data._kv);
					}
				}

				_tables.swap(newht._tables);
			}

			Hash hash;
			size_t hash0 = hash(kv.first) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;
			int flag = 1;
			while (_tables[hashi]._state == EXIST)
			{
				// 线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;

				/*hashi = (hash0 + (i*i*flag)) % _tables.size();
				if (hashi < _tables.size())
					hashi += _tables.size();

				if (flag == 1)
				{
					flag = -1;
				}
				else
				{
					++i;
					flag = 1;
				}*/
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				// 线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n;  // 记录数据个数
	};
}

3.哈希桶及其实现

哈希桶(HashBucket)又称链地址法，它与开放地址法最大的区别就在于他们处理哈希冲突的方式。不同于开放地址法的各种探测解决冲突，哈希桶更像"摆烂"一样，如果遇到key处理后发生冲突，直接链接在当前vector下。换句话说，这里哈希桶的哈希表是一个指针数组，它的下面链接一个个的链表。需要注意的是，库中实现的哈希桶会在链表过长时转换为红黑树，这里不做过多的解释，仅实现链表形式。

1.哈希桶的细节

1.哈希桶的哈希表是一个vector<Node*>类型，表中直接存储的是它下面挂着的链表的头结点地址。这里不采用vector<list<>>类型是考虑到上面说的转换为红黑树的情况，并且迭代器也不好处理，把代码写死是不太好的。

2.哈希桶在发生冲突时进行结点链接，头插法是个非常好的办法，效率是非常高的(O(1))。但需要注意的是，这里的链表实际上使用的是单链表，这也导致了unordered系列容器的迭代器是单向迭代器。

3.哈希桶的扩容也是个有趣的现象，我们会发现上面的开放地址法，数据会直接向表中存储，负载  因子的概念控制着的它的表长；而对于哈希桶，就算发生冲突也可以一直链接到当前位置，但是一条链太长会导致Find的效率极差(实际上这时就会转为红黑树)，因此这里控制的负载因子=1时才需要扩容。

4.有一个实际写插入和扩容逻辑时才能说清楚，我们先基本实现一下哈希桶的框架。

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

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

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;

    pair<Iterator, bool> Insert(const T& data)
{
	KeyOfT kot;
	Iterator it = Find(kot(data));
	if (it != End())
		return { it, false};

	Hash hash;

	// 负载因子 == 1时扩容
	if (_n == _tables.size())
	{
		/*HashTable<K, V> newht;
		newht._tables.resize(__stl_next_prime(_tables.size() + 1));
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				newht.Insert(cur->_kv);
				cur = cur->_next;
			}
		}

		_tables.swap(newht._tables);*/
		vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				// 头插到新表
				size_t hashi = hash(kot(cur->_data)) % newTable.size();
				cur->_next = newTable[hashi];
				newTable[hashi] = cur;

				cur = next;
			}

			_tables[i] = nullptr;

		}

		_tables.swap(newTable);
	}

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

	return { Iterator(newnode, this), false };
}
};

5.在写扩容时我们需要考虑：是否应该和开放地址法的扩容逻辑复用Insert一样？实际上可以是可以，但是并不好用。因为对于vector这个表来说它会调用自己的析构函数，但这里的Node*是一个自定义类型，析构了vector之后会剩下一堆没有析构的原链表结点，这反而更麻烦。于是这里扩容时，我们可以先新建一个表，然后把旧表的结点重新计算后链接在新表下即可。

扩容及插入详细逻辑：

a.创建新表

新表的大小是利用素数表确定的，便于key的处理

vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));

b.遍历旧表的每一个桶

for (size_t i = 0; i < _tables.size(); i++)
{
    Node* cur = _tables[i];
    // ...
}

c.单个处理桶里的每一个结点

注意这里要存每个结点的下个结点地址，因为当前结点会被移动到新表中，不存next会导致找不到下一个的位置

while (cur)
{
    Node* next = cur->_next;  // 保存下一个结点的地址
    size_t hashi = hash(kot(cur->_data)) % newTable.size();  // 重新计算哈希位置
    // 头插到新表的对应桶中
    cur->_next = newTable[hashi];
    newTable[hashi] = cur;
    cur = next;  // 移动到下一个结点
}

d.清空旧表的桶

_tables[i] = nullptr;

e.交换新旧表资源，防止临时变量出作用域销毁

_tables.swap(newTable);

2.哈希桶的完整实现

#pragma once
#include<vector>

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

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)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	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
	};
	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;
}

namespace open_address
{
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
			:_tables(__stl_next_prime(0))
			, _n(0)
		{}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			// 负载因子 >= 0.7扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				//vector<HashData<K, V>> newtables(_tables.size()*2);
				//for (auto& data : _tables)
				//{
				//	// 旧表的数据映射到新表
				//	if (data._state == EXIST)
				//	{
				//		size_t hash0 = data._kv.first % newtables.size();
				//		// ...
				//	}
				//}

				//_tables.swap(newtables);

				HashTable<K, V, Hash> newht;
				//newht._tables.resize(_tables.size() * 2);
				newht._tables.resize(__stl_next_prime(_tables.size() + 1));

				for (auto& data : _tables)
				{
					// 旧表的数据映射到新表
					if (data._state == EXIST)
					{
						newht.Insert(data._kv);
					}
				}

				_tables.swap(newht._tables);
			}

			Hash hash;
			size_t hash0 = hash(kv.first) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;
			int flag = 1;
			while (_tables[hashi]._state == EXIST)
			{
				// 线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;

				/*hashi = (hash0 + (i*i*flag)) % _tables.size();
				if (hashi < _tables.size())
					hashi += _tables.size();

				if (flag == 1)
				{
					flag = -1;
				}
				else
				{
					++i;
					flag = 1;
				}*/
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				// 线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n;  // 记录数据个数
	};
}

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

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

	// 前置声明
	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> 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;
		}

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

		// 16:46
		Self& operator++()
		{
			if (_node->_next)
			{
				// 当前桶还有数据，走到当前桶下一个节点
				_node = _node->_next;
			}
			else
			{
				// 当前桶走完了，找下一个不为空的桶
				KeyOfT kot;
				Hash hash;
				size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
				++hashi;
				while (hashi < _ht->_tables.size())
				{
					_node = _ht->_tables[hashi];

					if (_node)
						break;
					else
						++hashi;
				}

				// 所有桶都走完了，end()给的空标识的_node
				if (hashi == _ht->_tables.size())
				{
					_node = nullptr;
				}
			}

			return *this;
		}

	};

	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()
		{
			if (_n == 0)
				return End();

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

			return End();
		}

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


		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}

			return End();
		}

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

		HashTable()
			:_tables(__stl_next_prime(0))
			, _n(0)
		{}

		// 拷贝构造和赋值重载也需要

		~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)
		{
			KeyOfT kot;
			Iterator it = Find(kot(data));
			if (it != End())
				return { it, false};

			Hash hash;

			// 负载因子 == 1时扩容
			if (_n == _tables.size())
			{
				/*HashTable<K, V> newht;
				newht._tables.resize(__stl_next_prime(_tables.size() + 1));
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newht.Insert(cur->_kv);
						cur = cur->_next;
					}
				}

				_tables.swap(newht._tables);*/
				vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						// 头插到新表
						size_t hashi = hash(kot(cur->_data)) % newTable.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;

				}

				_tables.swap(newTable);
			}

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

			return { Iterator(newnode, this), false };
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur, this);
				}

				cur = cur->_next;
			}

			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			size_t hashi = 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;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}
	private:
		vector<Node*> _tables; // 指针数组
		size_t _n = 0;		   // 表中存储数据个数

		//struct Data
		//{
		//	ListNode* _head;
		//	RBTreeNode* _root;
		//	size_t _len;  // <= 8 存链表，>8 存红黑树 
		//};

		//vector<Data> _tables;
		//size_t _n = 0;		   // 表中存储数据个数
        
		//struct Data
		//{
		//	list<pair<K, V>> _list;
		//	map<K, V> _map;
		//	size_t _len;  // <= 8 存链表，>8 存红黑树 
		//};

		//vector<Data> _tables;
		//size_t _n = 0;		   // 表中存储数据个数
	};
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布