C++哈希表(unordered_map和unordered_set)

以哈希表为底层的unordered1_map和unordered_set相对于以红黑树为底层的map和set而言，在数据无序时效率更高。unordered1_map和unordered_set遍历出来的数据是无序的。

开放地址法

思路：创建一个数组，每个位置只能存储一个值，当插入一个值时，通过一个映射函数映射到该数组上，如果当前映射到的位置有值存在，就再以某种函数放到其余位置。每个位置的状态有三种，存在，删除和为空，以此方便我们查找和删除。

闭散列哈希表

开放地址法实现的哈希表极容易出现哈希冲突的情况，因此我们可以通过闭散列实现哈希表来降低哈希冲突。
闭散列思路：仍是一个数组，但是该数组中存储的是一个指针，该指针指向一个链表或一棵树，链表或树中存储的是对应的数据，也就是将原本映射到同一位置的数据，以链表或树的方式组织起来，同时我们把这个指针指向的结构称为桶，也就是哈希桶。
下面我们以闭散列哈希表为底层封装容器unordered_map和unordered_set

节点

数组中存储的是桶节点指针，节点的结构如下

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

存储的数据分别是_data数据和指向下一个桶节点的_next指针

哈希表

哈希表中有两个成员变量分别是存储每个哈希桶节点指针的数组和哈希表中一共存储的数据个数

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
	typedef HashNode<T> Node;
private:
	vector<Node*> _table;//指针数组
	size_t _n = 0; //存储了多少个数据
};
1
2
3
4
5
6
7
8

为什么还要保存哈希表中存储的数据个数？
如果存储的数据个数过多，而数组的长度较小就会导致哈希表负载因子过高，当负载因子大于某一个值时，就需要我们对这个数组进行扩容，因此_n的作用是方便我们计算负载因子，从而判断是否需要扩容。

struct DefaultHashFunc

通过该仿函数将不同类型的key值都转换成整型，方便我们通过映射函数映射到哈希表的某一个哈希桶

template<class K>
struct DefaultHashFunc//此函数作用是什么 通过仿函数将key变成整型，从而可以进行取余，建立映射关系
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc<string>//特化，指定接受的参数类型为string
{
	size_t operator()(const string& str)
	{
		return str[0];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

对于string类型我们这里以取第一个字符转化为整型为例，你也可以取前n个字符并以某种的运算确定该类型的映射值

KeyOfMap

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

1
2
3
4
5
6
7
8

KeyOfSet

struct KeyOfSet
{
	const K& operator()(const K& key)
	{
		return key;
	}
};

1
2
3
4
5
6
7
8

Find

通过key值来查找当前值是否存在，思路：先判断出当前key值可能位于哪一个桶，然后再在桶中逐个查找数据，如果找到了返回当前节点的迭代器，如果没找到则返回迭代器end(）
但是当前有两个问题：
1.传过来的key值类型我们是不确定的，他可能不是整型不能放到映射函数中进行运算，因此我们需要一个函数将这个key值转换成整型，然后再通过函数映射到哈希表的某一个桶，再在这个同种查找该数据是否存在
2.对于unordered_map和unordered_set分别存储的是键值对和键值，因此我们需要把他们中的key值取出来，然后才能与要查找的key值判断是否相等，因此可以选择在unordered_map和unordered_set第一层封装那里，分别设计对应的仿函数，用于取出这两个容器的key值。

iterator Find(const K& key)
{
	HashFunc hf;
	KeyOfT kot;
	size_t hashi = hf(key) % _table.size();
	Node* cur = _table[hashi];
	while(cur)
	{
		if (kot(cur->_data) == key)
		{
			return iterator(cur, this);
		}
		cur = cur->_next;
	}
	return end();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Insert

数据的插入思路:
1.先判断当前值在哈希表中是否存在，如果存在就不用再插入了，并返回一个键值对，键值对中first存储指向该节点的迭代器，second为bool值false
2.其次判断该哈希表是否需要扩容，我们定义当负载因子值为1时就进行扩容，也就是_table.size() == _n就扩容
3.最后再插入

pair<iterator, bool> Insert(const T& data)
{
	KeyOfT kot;
	//如果已存在就返回false
	iterator it = Find(kot(data));
	if (it != end())
	{
		return make_pair(it, false);
	}

	HashFunc hf;
	size_t hashi = hf(kot(data)) / _table.size();
	//扩容
	if (_table.size() == _n)
	{
		size_t newsize = _table.size() * 2;
		vector<Node*> newtable;
		newtable.resize(newsize);
		//把原容器中的数据重新插入到新容器中
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				hashi = hf(kot(cur->_data)) % newtable.size();
				cur->_next = newtable[hashi];
				newtable[hashi] = cur;
				cur = next;
			}
			_table[i] = nullptr;//将原表置空
		}
		newtable.swap(_table);
	}

	//插入
	hashi = hf(kot(data)) % _table.size();
	Node* newnode = new Node(data);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	_n++;
	return make_pair(iterator(newnode, this), true);
}
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

迭代器

对于以往的容器，我们在实现迭代器时，它的构造函数只需要传过来一个节点指针过来即可，但是对于unordered_map和unordered_set，我们选择把哈希表指针也传过来，为什么？
因为我们在实现++操作时，不仅要去访问当前节点所在桶中的下一个节点，还可能要去访问下一个桶中的节点，因此我们把整个哈希表都传过来，以利于我们实现++操作。
两种情况
1.该节点的_next指针不为空
2.该节点的_next指针为空，就需要我们再去访问下一个桶了
为什么要在迭代器中实现一个构造函数只传Iterator的构造函数？
因为我们在第一层封装时Insert的返回值是一个普通迭代器，但是unordered_set中的迭代器都是const的，我们要返回的迭代器也需要是const的，因此我们设计出一个构造函数将普通迭代器构造**出一个const迭代器。不写这个构造函数不行吗？不是可以由普通迭代器通过权限缩小成const迭代器吗？**要注意一个误区这里的迭代器是类型定义为

typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
1
2

HTIterator是一个整体，这是两个不同的类型，没有权限放大与缩小这一说，不要把概念混淆了

template <class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
	typedef HashNode<T> Node;
	typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
	typedef const HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
	Node* _node;
	const HashTable<K, T, KeyOfT, HashFunc>* _pht;
	//HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)//把哈希表指针也传过来，便于我们使用
	//	:_node(node)
	//	, _pht(pht)
	//{

	//}

	HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
		:_node(node)
		, _pht(pht)
	{

	}

	HTIterator(const Iterator& it)
		:_node(it._node)
		, _pht(it._pht)
	{

	}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else//当前桶结束，找下一个节点不为空的桶
		{
			HashFunc hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
			++hashi;
			while (hashi < _pht->_table.size())
			{
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					return *this;
				}
				++hashi;
			}
			_node = nullptr;
		}
		
		return *this;
	}

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

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

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};
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

前置声明

因为我们不仅要在哈希表类中访问迭代器，还要在迭代器中访问哈希表类对象，这就会导致哪个类放在前面会报错，因为程序编译是自上而下进行查找的，因此我们要把放在后面的类在另一个类之前进行类声明，表明这个类是存在的

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

哈希表的友元类

因为迭代器要访问哈希表类private私密成员指针数组和_n，因此我们选择把迭代器类声明为哈希表类的友元类

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
//友元声明,要加上模版
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc> friend struct HTIterator;
}
1
2
3
4
5
6

begin()和end()

哈希表类中定义普通迭代器和const 迭代器

		typedef HashNode<T> Node;
		
	public:
		typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
		typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
		
	HashTable()
	{
		_table.resize(10);
	}
	
	iterator begin()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			if (cur)
			{
				return iterator(cur, this);
			}
		}
		return iterator(nullptr, this);
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}

	const_iterator begin() const
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			if (cur)
			{
				return const_iterator(cur, this);
			}
		}
		return const_iterator(nullptr, this);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr, 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

unordered_map类

#pragma once
#include "HashTable.h"

namespace sw
{
	template <class K, class V>
	class UnorderedMap
	{
		struct KeyOfMap
		{
			const	K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		

	public:
		//为什么要加typename？
		typedef typename sw::HashTable<K, pair<const K, V>, KeyOfMap>::iterator iterator;
		typedef typename sw::HashTable<K, pair<const K, V>, KeyOfMap>::const_iterator const_iterator;
		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return hash_bucket.Insert(kv);
		}

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

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

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

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

		const_iterator begin() const
		{
			return hash_bucket.begin();
		}

		const_iterator end() const
		{
			return hash_bucket.end();
		}
	private:
		HashTable<K, pair<const K, V>, KeyOfMap> hash_bucket;
	};
}
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

unordered_set类

#pragma once
#include "HashTable.h"

namespace sw
{
	template <class K>
	class UnorderedSet
	{
		struct KeyOfSet
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		
	public:
		typedef typename sw::HashTable<K, K, KeyOfSet>::const_iterator iterator;
		typedef typename sw::HashTable<K, K, KeyOfSet>::const_iterator const_iterator;
		pair<iterator, bool> insert(const K& key)
		{
			return hash_bucket.Insert(key);
		}

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

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

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

		const_iterator begin()const 
		{
			return hash_bucket.begin();
		}

		const_iterator end()const 
		{
			return hash_bucket.end();
		}
	private:
		HashTable<K, K, KeyOfSet> hash_bucket;
	};
}
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

迭代器类

template <class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
	typedef HashNode<T> Node;
	typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
	typedef const HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
	Node* _node;
	const HashTable<K, T, KeyOfT, HashFunc>* _pht;
	//HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)//把哈希表指针也传过来，便于我们使用9.18 18:52
	//	:_node(node)
	//	, _pht(pht)
	//{

	//}

	HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
		:_node(node)
		, _pht(pht)
	{

	}

	HTIterator(const Iterator& it)
		:_node(it._node)
		, _pht(it._pht)
	{

	}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else//当前桶结束，找下一个节点不为空的桶
		{
			HashFunc hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
			++hashi;
			while (hashi < _pht->_table.size())
			{
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					return *this;
				}
				++hashi;
			}
			_node = nullptr;
		}
		
		return *this;
	}

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

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

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};
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

哈希表类

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
	template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
	friend struct HTIterator;

	typedef HashNode<T> Node;
	
	//友元声明,要加上模版
public:
	typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
	typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
	HashTable()
	{
		_table.resize(10);
	}
	
	iterator begin()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			if (cur)
			{
				return iterator(cur, this);
			}
		}
		return iterator(nullptr, this);
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}

	const_iterator begin() const
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			if (cur)
			{
				return const_iterator(cur, this);
			}
		}
		return const_iterator(nullptr, this);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr, this);
	}

	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		//如果已存在就返回false
		iterator it = Find(kot(data));
		if (it != end())
		{
			return make_pair(it, false);
		}

		HashFunc hf;
		size_t hashi = hf(kot(data)) / _table.size();
		//扩容
		if (_table.size() == _n)
		{
			size_t newsize = _table.size() * 2;
			vector<Node*> newtable;
			newtable.resize(newsize);
			//把原容器中的数据重新插入到新容器中
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					hashi = hf(kot(cur->_data)) % newtable.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
				_table[i] = nullptr;//将原表置空
			}
			newtable.swap(_table);
		}

		//插入
		hashi = hf(kot(data)) % _table.size();
		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		_n++;
		return make_pair(iterator(newnode, this), true);
	}

	iterator Find(const K& key)
	{
		HashFunc hf;
		KeyOfT kot;
		size_t hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];
		while(cur)
		{
			if (kot(cur->_data) == key)
			{
				return iterator(cur, this);
			}
			cur = cur->_next;
		}
		return end();
	}

	bool Erase(const K& key)
	{
		HashFunc hf;
		size_t hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];
		//当存在时，分两种情况
		//1.key节点在当前桶的第一个位置，_table[hashi]就指向key节点2.key节点在当前桶的后面位置
		KeyOfT kot;
		if (kot(cur->_data) == key)
		{
			_table[hashi] = cur->_next;
			delete cur;
			--_n;
			return true;
		}
		else
		{
			Node* prev = cur;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					prev->_next = cur->_next;
					delete cur;
					--_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

桶节点和类的前置声明

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 HashFunc = DefaultHashFunc<K>> class HashTable;

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

key值转size_t类型

template<class K>
struct DefaultHashFunc//此函数作用是什么9.16 11:26 通过仿函数将key变成整型，从而可以进行取余，建立映射关系
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc<string>//特化，指定接受的参数类型为string
{
	size_t operator()(const string& str)
	{
		return str[0];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

哈希表封装unordered_map和unordered_set具体步骤
一、哈希表类
1.定义桶节点，桶节点中包含存储的值和指向下一个桶节点的指针
2.定义哈希表类，类中成员变量分别为一个数组，数组中的值指向一个桶的节点指针
3.各类成员函数实现，通过两个DefaultHashFunc函数来获取key值所对应的整型值
二、迭代器
1.迭代器类需要两个成员变量分别为哈希表指针和桶节点指针
2.实现迭代器的++，==和!=,指针,引用等操作
3.实现一个构造函数，把普通迭代器转换成const迭代器，如果传过来的是普通迭代器那么这个构造函数就为构造函数，如果传过来的是const迭代器那么这个函数就为拷贝构造
4.哈希表类中typedef迭代器，分别为const迭代器和普通迭代器
三、封装unordered_map和unordered_set
1.类中成员变量都为哈希表，当上层调用unordered_map和unordered_set类成员函数时，我们都通过该成员去调用底层哈希表类所对应的函数
2.unordered_set中的key不允许被修改，因此我们把它的迭代器都定义为const迭代器即可
3.对于unordered_map而言它的key也不允许被修改，但是value可以被修改，因此我们就不能让它像unordered_set一样将迭代器都定义为const的，而是它该封装类中的成员变量中的K声明为const的 HashTable<K, pair<const K, V>, KeyOfMap> hash_bucket;
4.在这两个类中分别实现仿函数，用于返回该类的key值