2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

C++进阶哈希表封装unordered_map和unordered_set

作者：2023面试高手 | 2024-05-11 17:24:34

踩

作者：@小萌新
专栏：@C++进阶
作者简介：大二学生希望能和大家一起进步！
本篇博客简介：使用哈希表封装unordered_map和unordered_set

哈希表源代码

我们下面会对一个 K V 模型的哈希表进行封装

使用之来模拟实现STL库中的unordered_map和unordered_set

其中哈希表的源代码如下

//每个哈希桶中存储数据的结构
template<class K, class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	//构造函数
	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};

//哈希表
template<class K, class V>
class HashTable
{
	typedef HashNode<K, V> Node; //哈希结点类型
public:
	//获取本次增容后哈希表的大小
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		//素数序列
		const size_t primeList[PRIMECOUNT] =
		{
			53ul, 97ul, 193ul, 389ul, 769ul,
			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
			1610612741ul, 3221225473ul, 4294967291ul
		};
		size_t i = 0;
		for (i = 0; i < PRIMECOUNT; i++)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	//插入函数
	bool Insert(const pair<K, V>& kv)
	{
		//1、查看哈希表中是否存在该键值的键值对
		Node* ret = Find(kv.first);
		if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）
		{
			return false; //插入失败
		}

		//2、判断是否需要调整哈希表的大小
		if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1
		{
			//增容
			//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）
			vector<Node*> newtable;

			newtable.resize(GetNextPrime(_table.size()));
				
			//b、将原哈希表当中的结点插入到新哈希表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) //桶不为空
				{
					Node* cur = _table[i];
					while (cur) //将该桶的结点取完为止
					{
						Node* next = cur->_next; //记录cur的下一个结点
						size_t index = cur->_kv.first%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
						//将该结点头插到新哈希表中编号为index的哈希桶中
						cur->_next = newtable[index];
						newtable[index] = cur;

						cur = next; //取原哈希表中该桶的下一个结点
					}
					_table[i] = nullptr; //该桶取完后将该桶置空
				}
			}
			//c、交换这两个哈希表
			_table.swap(newtable);
		}

		//3、将键值对插入哈希表
		size_t index = kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		Node* newnode = new Node(kv); //根据所给数据创建一个待插入结点
		//将该结点头插到新哈希表中编号为index的哈希桶中
		newnode->_next = _table[index];
		_table[index] = newnode;

		//4、哈希表中的有效元素个数加一
		_n++;
		return true;
	}
	//查找函数
	HashNode<K, V>* Find(const K& key)
	{
		if (_table.size() == 0) //哈希表大小为0，查找失败
		{
			return nullptr;
		}

		size_t index = key % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		//遍历编号为index的哈希桶
		HashNode<K, V>* cur = _table[index];
		while (cur) //直到将该桶遍历完为止
		{
			if (cur->_kv.first == key) //key值匹配，则查找成功
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr; //直到该桶全部遍历完毕还没有找到目标元素，查找失败
	}
	//删除函数
	bool Erase(const K& key)
	{
		//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		size_t index = key % _table.size();
		//2、在编号为index的哈希桶中寻找待删除结点
		Node* prev = nullptr;
		Node* cur = _table[index];
		while (cur) //直到将该桶遍历完为止
		{
			if (cur->_kv.first == key) //key值匹配，则查找成功
			{
				//3、若找到了待删除结点，则删除该结点
				if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
				{
					_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
				}
				else //待删除结点不是哈希桶的第一个结点
				{
					prev->_next = cur->_next; //将该结点从哈希桶中移除
				}
				delete cur; //释放该结点
				//4、删除结点后，将哈希表中的有效元素个数减一
				_n--;
				return true; //删除成功
			}
			prev = cur;
			cur = cur->_next;
		}
		//假删除可能会导致迭代器失效
			
		return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

哈希模板参数的控制

我们都知道

unordered_map是KV模型的容器
unordered_set是K模型的容器

那么我们应该如何使用一份哈希表来封装它们呢？

这里就涉及到模板参数控制的一些技巧

我们这里可以将哈希模板的第二个参数改为T

template<class K ,class T>
class Hashtable
1
2

那么这样子的话假设上层使用的是unordered_map容器那么参数应该是这么传递的

template<class K, class V>
class unordered_map
{
public:
	//...
private:
	HashTable<K, pair<K, V>> _ht; //传入底层哈希表的是K以及K和V构成的键值对
};
1
2
3
4
5
6
7
8

假设上层使用的是unordered_set容器那么参数应该是这么传递的

template<class K>
class unordered_set
{
public:
	//...
private:
	HashTable<K, K> _ht; //传入底层哈希表的是K和K
};

1
2
3
4
5
6
7
8
9

我们可以发现通过这种方式就能很好的控制原来哈希表中的value值

上层容器是unordered_set时传入的T是键值哈希结点中存储的就是键值
上层容器是unordered_map时传入的T是键值对哈希结点中存储的就是键值对

当我们更改模板之后我们可以发现节点的代码会变成这样子

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

	
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12

模板参数仿函数的增加

在哈希映射中我们需要通过元素的key值来计算它的函数地址

可是经过我们上面的操作我们并不知道T是个什么东西它有可能是键值有可能是一个键值对

那么这里我们就需要想出一个方法来统一获取T的键值

这里使用到的方法就是仿函数

我们在使用unordered_map和unordered_set 再增加一个仿函数使用这个仿函数来获取它们的key值

代码表示如下

template<class K, class V>
class unordered_map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key
		{
			return kv.first;
		}
	};
public:
	//...
private:
	HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template<class K>
class unordered_set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //返回键值key
		{
			return key;
		}
	};
public:
	//...
private:
	HashTable<K, K, SetKeyOfT> _ht;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

当然最后我们的哈希表代码也需要修改增加一个参数来接受上层容器传递过来的仿函数

template<class K, class T, class KeyOfT>
class HashTable
1
2

String对象无法取模问题

我们在哈希表中使用的是除留余数法那么对于整数或者说可以隐式类型转化成无符号数的类型来说我们只需要强制类型转换一下即可

但是对于字符串类型来说呢？

字符串并不是整型不可以直接强制类型转换我们不可以使用除留余数法

于是我们必须自己实现一种方法来使得字符串数据可以转化为整型数据

但是我们要明白的是字符组合式无穷无尽的但是在计算机中无符号数确实有穷尽的

所以说我们不可能实现一种算法使得字符串和无符号数一一对应所以说哈希冲突在所难免

经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法

于是我们可以在哈希的模板参数中加上一个仿函数

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
1
2

如果上层没有传入仿函数我们就使用该默认仿函数将key强制类型转化成无符号数

如果式字符串则就使用仿函数的特化版本使用BKDRHash算法返回一个无符号数

代码表示如下

template<class K>
struct Hash
{
	size_t operator()(const K& key) //返回键值key
	{
		return key;
	}
};
//string类型的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

哈希表类的实现

构造函数

我们可以看到哈希表的代码中有两个成员变量

vector<Node*> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数
1
2

vector会调用自己的默认构造函数来进行初始化
元素个数_n已经被我们初始化为0了

所以说实际上我们不需要写构造函数构造函数直接让它默认生成就可以

这里使用default关键字来让他默认生成构造函数

//构造函数
HashTable() = default; //显示指定生成默认构造函数
1
2

这里解释下为什么使用default关键字

在我们前面讲类和对象的时候就说过拷贝构造函数就是一种特殊的构造函数

而我们如果写了构造函数就不会生成默认构造函数了

结合这两点由于我们下面既需要写拷贝构造函数又需要默认构造函数

所以必须要写defalut关键字让他生成默认构造函数

拷贝构造函数

哈希表在拷贝的时候需要进行深拷贝否则拷贝出来的节点就会和原来的节点相同

所以说哈希表拷贝构造的实现逻辑如下

将哈希表的大小调整为ht._table的大小
将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中
更改哈希表当中的有效数据个数

代码表示如下

//拷贝构造函数
HashTable(const HashTable& ht)
{
	//1、将哈希表的大小调整为ht._table的大小
	_table.resize(ht._table.size());
	//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）
	for (size_t i = 0; i < ht._table.size(); i++)
	{
		if (ht._table[i]) //桶不为空
		{
			Node* cur = ht._table[i];
			while (cur) //将该桶的结点取完为止
			{
				Node* copy = new Node(cur->_data); //创建拷贝结点
				//将拷贝结点头插到当前桶
				copy->_next = _table[i];
				_table[i] = copy;
				cur = cur->_next; //取下一个待拷贝结点
			}
		}
	}
	//3、更改哈希表当中的有效数据个数
	_n = ht._n;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

赋值运算符重载

在实现赋值运算符重载的时候我们可以通过参数来间接调用拷贝构造函数

因为我们前面说过 形参本质上是实参的一份临时拷贝且会在出作用域后自动销毁

所以我们拷贝构造后只需要交换两个对象的成员变量甚至都不用自己去释放空间

形参走出作用域之后会自动帮我们销毁

代码表示如下

//赋值运算符重载函数
HashTable& operator=(HashTable ht)
{
	//交换哈希表中两个成员变量的数据
	_table.swap(ht._table);
	swap(_n, ht._n);

	return *this; //支持连续赋值
}

1
2
3
4
5
6
7
8
9
10

析构函数

因为哈希表中储存的节点全部都是new出来的所以说结束的时候我们必须全部delete掉来避免内存泄漏

这个时候我们只需要一个个遍历一个个delete就好了

//析构函数
~HashTable()
{
	//将哈希表当中的结点一个个释放
	for (size_t i = 0; i < _table.size(); i++)
	{
		if (_table[i]) //桶不为空
		{
			Node* cur = _table[i];
			while (cur) //将该桶的结点取完为止
			{
				Node* next = cur->_next; //记录下一个结点
				delete cur; //释放结点
				cur = next;
			}
			_table[i] = nullptr; //将该哈希桶置空
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

哈希表的正向迭代器的实现

哈希表的迭代器实际上就是对其指针进行了封装因为我们在实现++运算符重载的时候

要在哈希表中寻找下一个非空哈希桶所以说我们的迭代器中需要存储哈希表的地址

//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
	typedef HashNode<T> Node; //哈希结点的类型
	typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表的类型
	typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的类型

	Node* _node; //结点指针
	HT* _pht; //哈希表的地址
};

1
2
3
4
5
6
7
8
9
10
11
12

构造函数

我们在构造正向迭代器的时候不仅需要节点的指针还需要其在哈希表中的地址

所以说构造函数应该这么写

//构造函数
__HTIterator(Node* node, HT* pht)
	:_node(node) //结点指针
	, _pht(pht) //哈希表地址
{}

1
2
3
4
5
6

解引用操作

我们使用解引用操作的时候我们想要的是返回是节点的数据

代码表示如下

T& operator*()
{
	return _node->_data; //返回哈希结点中数据的引用
}

1
2
3
4
5

–>操作

当我们使用–>操作的时候我们想要获得的是数据的地址

T* operator->()
{
	return &_node->_data; //返回哈希结点中数据的地址
}
1
2
3
4

相等和不相等

等我们判断两个迭代器是否相等的时候我们只需要判断被封装的节点是否相同即可代码如下

bool operator!=(const Self& s) const
{
	return _node != s._node; //判断两个结点的地址是否不同
}

bool operator==(const Self& s) const
{
	return _node == s._node; //判断两个结点的地址是否相同
}
1
2
3
4
5
6
7
8
9

前置++

++运算符实际上就是从哈希表中找到下一个节点的位置

逻辑上没有什么难点

如果当前节点不是哈希桶中的最后一个节点那么返回下一个节点即可
如果当前节点是哈希桶中的最后一个节点那么往后找到下一个非空桶返回第一个节点即可

代码表示如下

//前置++
Self& operator++()
{
	if (_node->_next) //该结点不是当前哈希桶中的最后一个结点
	{
		_node = _node->_next; //++后变为当前哈希桶中的下一个结点
	}
	else //该结点是当前哈希桶中的最后一个结点
	{
		KeyOfT kot;
		HashFunc hf;
		size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通过哈希函数计算出当前所处哈希桶编号index（除数不能是capacity）
		index++; //从下一个位置开始找一个非空的哈希桶
		while (index < _pht->_table.size()) //直到将整个哈希表找完
		{
			if (_pht->_table[index]) //当前哈希桶非空
			{
				_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点
				return *this;
			}
			index++; //当前哈希桶为空桶，找下一个哈希桶
		}
		_node = nullptr; //哈希表中已经没有空桶了，++后变为nullptr
	}
	return *this;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

我们实现了正向迭代器之后还需要在哈希表中实现这样子的几个操作

进行正向迭代器类型的typedef 因为我们外部需要使用迭代器所以说要在public区域封装
因为++操作符会访问哈希表的内部元素所以说我们要在哈希表中声明友元
将哈希表查找函数的返回值改为由节点指针和哈希表地址构成的正向迭代器
将插入函数的返回值改为由迭代器和bool类型组成的键值对

哈希表的begin和end

对于begin来说我们只需要返回第一个非桶中的第一个节点就可以
对于end来说直接返回一个空节点构造的正向迭代器

//哈希表的实现
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{
	//将正向迭代器类声明为哈希表类的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend struct __HTIterator;

	typedef HashNode<T> Node; //哈希结点类型
public:
	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器的类型

	iterator begin()
	{
		size_t i = 0;
		while (i < _table.size()) //找到第一个非空哈希桶
		{
			if (_table[i]) //该哈希桶非空
			{
				return iterator(_table[i], this); //返回该哈希桶中的第一个结点的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中无数据，返回end()
	}
	iterator end()
	{
		return iterator(nullptr, this); //返回nullptr的正向迭代器
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

源代码

哈希表

//哈希结点的定义
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	//构造函数
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};
template<class K>
struct Hash
{
	size_t operator()(const K& key) //返回键值key
	{
		return key;
	}
};
//string类型的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};
//哈希表的实现
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{
	//将正向迭代器类声明为哈希表类的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend struct __HTIterator;
	//friend struct __HTIterator<K, T,KeyOfT, HashFunc>;
	typedef HashNode<T> Node; //哈希结点类型
public:
	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器的类型

	iterator begin()
	{
		size_t i = 0;
		while (i < _table.size()) //找到第一个非空哈希桶
		{
			if (_table[i]) //该哈希桶非空
			{
				return iterator(_table[i], this); //返回该哈希桶中的第一个结点的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中无数据，返回end()
	}
	iterator end()
	{
		return iterator(nullptr, this); //返回nullptr的正向迭代器
	}

	//构造函数
	HashTable() = default; //显示指定生成默认构造

	//拷贝构造函数
	HashTable(const HashTable& ht)
	{
		//1、将哈希表的大小调整为ht._table的大小
		_table.resize(ht._table.size());
		//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）
		for (size_t i = 0; i < ht._table.size(); i++)
		{
			if (ht._table[i]) //桶不为空
			{
				Node* cur = ht._table[i];
				while (cur) //将该桶的结点取完为止
				{
					Node* copy = new Node(cur->_data); //创建拷贝结点
					//将拷贝结点头插到当前桶
					copy->_next = _table[i];
					_table[i] = copy;
					cur = cur->_next; //取下一个待拷贝结点
				}
			}
		}
		//3、更改哈希表当中的有效数据个数
		_n = ht._n;
	}
	//赋值运算符重载函数
	HashTable& operator=(HashTable ht)
	{
		//交换哈希表中两个成员变量的数据
		_table.swap(ht._table);
		swap(_n, ht._n);

		return *this; //支持连续赋值
	}
	//析构函数
	~HashTable()
	{
		//将哈希表当中的结点一个个释放
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i]) //桶不为空
			{
				Node* cur = _table[i];
				while (cur) //将该桶的结点取完为止
				{
					Node* next = cur->_next; //记录下一个结点
					delete cur; //释放结点
					cur = next;
				}
				_table[i] = nullptr; //将该哈希桶置空
			}
		}
	}
	//获取本次增容后哈希表的大小
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		//素数序列
		const size_t primeList[PRIMECOUNT] =
		{
			53ul, 97ul, 193ul, 389ul, 769ul,
			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
			1610612741ul, 3221225473ul, 4294967291ul
		};
		size_t i = 0;
		for (i = 0; i < PRIMECOUNT; i++)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	//插入函数
	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		//1、查看哈希表中是否存在该键值的键值对
		iterator ret = Find(kot(data));
		if (ret != end()) //哈希表中已经存在该键值的键值对（不允许数据冗余）
		{
			return make_pair(ret, false); //插入失败
		}

		//2、判断是否需要调整哈希表的大小
		if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1
		{
			//增容
			//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）
			HashFunc hf;
			vector<Node*> newtable;
			//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
			//newtable.resize(newsize);

			newtable.resize(GetNextPrime(_table.size()));
				
			//b、将原哈希表当中的结点插入到新哈希表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) //桶不为空
				{
					Node* cur = _table[i];
					while (cur) //将该桶的结点取完为止
					{
						Node* next = cur->_next; //记录cur的下一个结点
						size_t index = hf(kot(cur->_data))%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
						//将该结点头插到新哈希表中编号为index的哈希桶中
						cur->_next = newtable[index];
						newtable[index] = cur;

						cur = next; //取原哈希表中该桶的下一个结点
					}
					_table[i] = nullptr; //该桶取完后将该桶置空
				}
			}
			//c、交换这两个哈希表
			_table.swap(newtable);
		}

		//3、将键值对插入哈希表
		HashFunc hf;
		size_t index = hf(kot(data)) % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		Node* newnode = new Node(data); //根据所给数据创建一个待插入结点
		//将该结点头插到新哈希表中编号为index的哈希桶中
		newnode->_next = _table[index];
		_table[index] = newnode;

		//4、哈希表中的有效元素个数加一
		_n++;
		return make_pair(iterator(newnode, this), true);
	}
	//查找函数
	iterator Find(const K& key)
	{
		if (_table.size() == 0) //哈希表大小为0，查找失败
		{
			return end();
		}

		KeyOfT kot;
		HashFunc hf;
		size_t index = hf(key) % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		//遍历编号为index的哈希桶
		HashNode<T>* cur = _table[index];
		while (cur) //直到将该桶遍历完为止
		{
			if (kot(cur->_data) == key) //key值匹配，则查找成功
			{
				return iterator(cur, this);
			}
			cur = cur->_next;
		}
		return end(); //直到该桶全部遍历完毕还没有找到目标元素，查找失败
	}
	//删除函数
	bool Erase(const K& key)
	{
		KeyOfT kot;
		HashFunc hf;
		//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		size_t index = hf(key) % _table.size();
		//2、在编号为index的哈希桶中寻找待删除结点
		Node* prev = nullptr;
		Node* cur = _table[index];
		while (cur) //直到将该桶遍历完为止
		{
			if (kot(cur->_data) == key) //key值匹配，则查找成功
			{
				//3、若找到了待删除结点，则删除该结点
				if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
				{
					_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
				}
				else //待删除结点不是哈希桶的第一个结点
				{
					prev->_next = cur->_next; //将该结点从哈希桶中移除
				}
				delete cur; //释放该结点
				//4、删除结点后，将哈希表中的有效元素个数减一
				_n--;
				return true; //删除成功
			}
			prev = cur;
			cur = cur->_next;
		}
		//假删除可能会导致迭代器失效
			
		return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

unordered_map

	template<class K, class V>
	class unordered_map
	{
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<K, V>, MapKeyOfT>::iterator 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(make_pair(key, V()));
			iterator it = ret.first;
			return it->second;
		}
		//删除函数
		void erase(const K& key)
		{
			_ht.Erase(key);
		}
		//查找函数
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
	private:
		HashTable<K, pair<K, V>, MapKeyOfT> _ht;
	};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

unordered_set


	template<class K>
	class unordered_set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key) //返回键值key
			{
				return key;
			}
		};
	public:
		//现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取
		typedef typename HashTable<K, K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		//插入函数
		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
		//删除函数
		void erase(const K& key)
		{
			_ht.Erase(key);
		}
		//查找函数
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
	private:
		HashTable<K, K, SetKeyOfT> _ht;
	};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

正向迭代器

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

//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
	typedef HashNode<T> Node; //哈希结点的类型
	typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表的类型
	typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的类型

	Node* _node; //结点指针
	HT* _pht; //哈希表的地址

	//构造函数
	__HTIterator(Node* node, HT* pht)
		:_node(node) //结点指针
		, _pht(pht) //哈希表地址
	{}

	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;
			HashFunc hf;
			size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通过哈希函数计算出当前所处哈希桶编号index（除数不能是capacity）
			index++; //从下一个位置开始找一个非空的哈希桶
			while (index < _pht->_table.size()) //直到将整个哈希表找完
			{
				if (_pht->_table[index]) //当前哈希桶非空
				{
					_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点
					return *this;
				}
				index++; //当前哈希桶为空桶，找下一个哈希桶
			}
			_node = nullptr; //哈希表中已经没有空桶了，++后变为nullptr
		}
		return *this;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/555621

C++进阶 哈希表封装unordered_map和unordered_set

哈希表封装

哈希表源代码

哈希模板参数的控制

模板参数仿函数的增加

String对象无法取模问题

哈希表类的实现

构造函数

拷贝构造函数

赋值运算符重载

析构函数

哈希表的正向迭代器的实现

构造函数

解引用操作

–>操作

相等和不相等

前置++

哈希表的begin和end

源代码

哈希表

unordered_map

unordered_set

正向迭代器

C++进阶哈希表封装unordered_map和unordered_set