详解c++---哈希桶

闭散列的回顾

在前面的学习中我们知道了闭散列的运算规则，当两个数据计算得到的位置发生冲突时，它会自动的往后寻找没有发生冲突的位置，比如说当前数据的内容如下：

当插入的数据为33时计算的位置为3，可是位置3已经被占领了并且4也被占领了，但是位置5没有被占领所以插入数据33就会占领位置5，那么这里的图片就如下：

这就是闭散列的插入原则，并且每个节点都有一个变量用来表示状态，这样在查找就不会出现漏查的情况，但是这样的实现会存在一个问题，扩容是根据有效数据的个数和vector容量来确定的，但是查找的时候是根据当前元素的状态是否为空来判断后面还有没有要查找的数据，如果为空的话则说明当前元素的后面没有我们要查找的元素，如果为存在或者被删除的话就说明当前元素的后面还有我们要查找的数据，如果我们不停的插入数据并且删除数据的话就会导致容器中的每个元素的状态都变成了被删除这样在查找一个不存的数据时，就会陷入死循环的状态那么这就是我们之前模拟实现的一个缺点，那么这里我们就来看看第二个解决数据不集中的方法：拉链法或者叫哈希桶法。

拉链法/哈希桶的原理

这个方法就是每个位置上都是一个链表，如果有多个位置发生冲突了，那么就挂在这个位置的链表上，这样就不会导致占领别人的位置，当我们要查找的时候就是先找到插入数据的位置，然后再通过这个位置的链表来按照顺序来进行查找，比如说下面的图片

当我们想要插入一个数据13时就会先计算13对应在哈希表上的位置，根据之前的计算原则这里得到的位置就是3，所以图片就变成了下面这样：

如果再插入数据23的话这里计算的位置依然是3，但是此时3上已经有元素了，所以这时就会使用链表的头插将数据23插入到13的前面，那么这里的图片就是下面这样：

如果再插入数据33的话计算的位置依然是3，所以就会把33放到3号位置对应的链表的头部，那么这里的图片就变成下面这样：

那么这就是哈希桶的插入规则，找到对应位置的链表将数据插入到头部即可，如果要查找的话也是相同的原理先找到数据对应的链表然后循环遍历这个链表找到出现的数据即可，删除也是相同的道理，先找到数据对应的下标然后根据下标找到对应的链表，最后遍历链表找到要删除的数据进行链表的删除即可，那么这就是哈希桶的实现思路接下来我们就来看看这种方法的准备工作。

准备工作

哈希的底层是一个vector的数组，数组中的每个节点都有一个pair类型的数据，其次还有一个指针指向当前链表节点的下一个节点，所以每个节点中有个一个pair类型的数据和一个指向节点的指针，所以这里得创建一个类来描述每个节点，并且类中有一个构造函数来初始化节点，这里的构造函数就需要一个pair类型的参数，在构造函数里面就将指针初始化为nullptr将pair类型的参数赋值为传递过来的参数，有因为这里的节点可能要存储各种各样的数据，所以这里得创建个模板来接收各种各样的参数，并且模板的参数得是两个，那么这里的代码就如下：

template<class K,class V>
struct HashNode
{
	HashNode(const pair<K,V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{}
	pair<K, V> _kv;
	HashNode* _next;
};
1
2
3
4
5
6
7
8
9
10

根据前面的学习我们知道要想计算数据对应在哈希表上的位置就得添加对应的仿函数，那么这里的代码就如下

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 res = 0;
		for (auto& ch : s)
		{
			res *= 131;
			res += ch;
		}
		return res;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最后就是哈希bucket类的准备工作，首先这个类有一个模板，模板中有三个参数，前两个表示存储数据的类型，最后一个表示的是仿函数，因为哈希的地城是vector数组，所以这里得添加一个vector容器用来存储数据和一个整型变量用来记录容器中有效字符的个数即可，并且vector中的每个元素都是节点类型，那么该类的构造函数就将vector容器的resize到10个元素即可，那么这里的代码就如下：

template<class K, class V, class Hash = HashFunc<K>>
class BucketTable
{
	typedef HashNode<K, V> Node;
public:
typedef HashNode<K, V> Node;
	BucketTable()
		:_n(0)
	{
		_tables.resize(10);
	}
private:
	vector<Node*> _tables;
	size_t _n;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

看到这里我们的准备工作就完成了接下来就要实现哈希的每个函数。

find函数

find函数就是先根据传递过来参数找到这个参数可能出现的位置，找到了位置就意味着找了一个链表的头节点，所以这个时候就可以通过循环遍历的方式来一一对比链表中是否含有想要查找的数据，如果存在的话就返回这个节点所在的地址，如果不存在的话就返回一个空指针，所以该函数的第一步就创建一个仿函数对象，并计算数据出现的位置：

Node* Find(const K& key)
{
	Hash hf;
	size_t pos = hf(key) % _tables.size();
	Node* cur=_tables[pos]
}
1
2
3
4
5
6

cur指向的是链表的第一个元素，所以接下来就可以使用while循环一个一个的遍历每个元素，每次循环都会改变cur的指向让其指向下一个元素，知道cur本身变为空就停止查找，在循环体的内部如果出现了跟查找变量一样的值就直接返回这个节点的地址，如果循环结束了也没有找到想要的值的话就返回一个空指针，那么这里的代码就如下：

Node* Find(const K& key)
{
	Hash hf;
	size_t pos = hf(key) % _tables.size();
	Node* cur = _tables[pos];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}
		else
		{
			cur = cur->_next;
		}
	}
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

插入函数

将数据插入的链表的时候得先判断一下要插入的元素当前是否已经存在，所以这里可以使用find函数来进行查找，根据find函数的返回值来判断是否存在，那么这里的代码就如下：

bool insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
	{
		return false;
	}
}
1
2
3
4
5
6
7

如果当前的元素不存在的话就开始插入数据，这种实现方法也得根据传递过来的元素找到应该插入的位置，所以该函数的第一步就是创建一个仿函数对象然后根据传递过来的参数计算得出应该插入的位置，找到插入位置之后就使用头插来插入对应的数据，这里的头插就是先让newnode的_next指向当前位置的链表，然后修改vector中当前位置的指向使其指向newnode，那么这里的代码就如下：

bool insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
	{
		return false;
	}
	Hash hf;
	size_t pos = hf(kv.first) % _tables.size();
	Node* newnode = new HashNode<K,V>(kv);
	newnode->_next = _tables[pos];
	_tables[pos] = newnode;
	++_n;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里依然得添加负载因子，官方库中可以通过一些函数来得到当前容器的负载因子和最大的负载因子，如果负载因子等于1了我们就扩容，将其容量变为之前的两倍，但是扩容不能直接把链表对应的移动到新的容器上去因为这里的映射关系已经改变了比如说当前容器的容量为10则数据18对应的位置就是8上面的链表，如果容器发生了扩容使得容量变成了20的话18就对应的不再是8而是18上面的链表，所以我们这里解决的方法就是创建一个新的哈希表，然后遍历容器中的每个位置，如果当前位置不为空就往这个位置里面进行遍历对每个元素都进行插入操作，如果当前位置为空的话就跳转到下一个元素，那么这里的代码就如下：

bool insert(const pair<K, V>& kv)
{
	if (!Find(kv.first))
	{
		return false;
	}
	if (_n / _tables.size() == 1)//平衡因子为1就更新
	{
		vector<Node*> newBH;
		newBH._tables.resize(_n * 2);
		for (auto& cur : _tables)
		{
			while (cur)
			{
				newBH.insert(cur->_kv);
				cur = cur->_next;
			}
		}
		_tables.swap(newBH._tables);

	}
	Hash hf;
	size_t pos = hf(kv.first) % _tables.size();
	Node* newnode = new HashNode<K,V>(kv);
	newnode->_next = _tables[pos];
	_tables[pos] = newnode;
	++_n;
	return 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

erase函数

erase函数也是分为三步来完成，首先找到节点对应的链表，然后再找链表中是否存在该元素，如果不存在的话就返回false，如果存在的话就对该链表的该节点进行删除，因为这里删除的时候得保证链表之间的上下链接，所以这里创建一个指向指向被删除节点的前一个节点，以此来保证删除前后的链接，这里大家要注意的一点就是当删除的节点是头节点时，得改变vector容器中的指针的指向，那么这里的代码就如下：

bool erase(const K& key)
{
	HashFunc<K> HF;
	size_t pos = HF(key) % _tables.size();
	Node* cur = _tables[pos];
	Node* prev = cur;
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			if (cur == _tables[pos])
			{
				_tables[pos] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}
			delete cur;
			_n--;
			return true;
		}
		else
		{
			prev = cur;
			cur = cur->_next;
		}
	}
	return false;
}
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

析构函数

之前的写法当中不需要添加析构函数是因为vector中本身就含有析构函数，所以编译器自己生成的析构函数能够自动的调用vector的析构函数来释放空间，但是这里不一样这里得写析构函数，因为vector释放之后不会释放里面的节点所申请的空间，所以这里的析构函数要干的事情就是虚幻遍历每个节点并且一个一个的释放每个节点申请的空间，那么这里的代码就如下：

~BucketTable()
{
	for (int i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_tables[i] = nullptr;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码测试

可以通过下面的代码来进行相应的测试看看我们上面写的代码是否是正确的：

void TestHT1()
{
	BucketTable<int, int> ht;
	int a[] = { 18, 8, 7, 27, 57, 3, 38, 18 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}
	ht.insert(make_pair(17, 17));
	ht.insert(make_pair(5, 5));
	if (ht.Find(7)) { cout << "存在" << endl; }
	else { cout << "不存在" << endl; }
	ht.erase(7);
	if (ht.Find(7)) { cout << "存在" << endl; }
	else { cout << "不存在" << endl; }
}
int main()
{
	TestHT1();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码的运行结果如下：

我们可以再用下面的代码来进行一下测试：

void TestHT2()
{
	string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	//HashTable<string, int, HashFuncString> countHT; 
	BucketTable<string, int> countHT;
	for (auto& e : arr)
	{
		HashNode<string, int>* ret = countHT.Find(e);
		if (ret)
		{
			ret->_kv.second++;
		}
		else
		{
			countHT.insert(make_pair(e, 1));
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这段代码的运行结果如下：

符合我们的预期说明我们上面的代码实现的是正确的。

insert函数的改进

我们上面实现的insert函数在扩容的时候都是采用的从10开始每次都扩容2倍的方法来进行扩容，可是哈希表这里有一个性质就是当容器的大小为素数的时候可以在一定的程度上降低哈希冲突的可能性使得数据分布的更加的均匀，所以在扩容的时候和在规定起始空间的时候最好选择将容器的大小扩容为素数，依然每次扩容成为两倍但是最终的容量为两倍数据的附近的一个素数，那我们如何来找到这个数呢？如果我们真的想实现这个功能的话得需要写一个算法来找到这个数，并且这个算法还很麻烦，所以我们采用的解决方法就是用空间来换取时间，我们之间将所有范围内的素数列举出来不就可以吗？比如说下面的数组：

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
};
1
2
3
4
5
6
7
8
9
10

然后我们就可以用这个数组封装成为一个函数，这个函数的功能就是找到一个数据附件的素数，这里就可以通过循环遍历的方式来进行查找，那么这里的代码如下：

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 (int 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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

有了这个游戏之后就可以对insert函数进行改进，但是这里先不要急还有一个地方需要我们改进的就是插入数据的时候，上面扩容在插入数据的时候是创建一个哈希桶然后再调用哈希桶来插入原来哈希桶的每个数据，如果这么做的话，在新的哈希桶里面又会不断地创建地节点，并且在函数结束地时候又会删除节点，如果节点的个数非常多的话这就会导致效率低下，所以我们这里就有一个改进思路就是能不能用已有的节点来插入到新创建的哈希表呢？答案是可以的，我们依然是创建一个新的哈希表然后改变其内部的大小，然后遍历之前的老哈希表找到里面的元素并计算他在新表上的位置，然后修改其节点内部指针的指向，那么这里的代码如下：

if (_n / _tables.size() == 1)//平衡因子为1就更新
{
	/*vector<Node*> newBH;;
	newBH.resize(_n * 2);
	for (auto& cur : _tables)
	{
		while (cur)
		{
			newBH.insert(cur->_kv);
			cur = cur->_next;
		}
	}
	_tables.swap(newBH._tables);*/
	vector<Node*> newBH;
	newBH._tables.resize(__stl_next_prime(_tables.size()));
	for (int i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;
			size_t pos = Hash()(cur->_kv.first);
			cur->_next = newBH[pos];
			newBH[pos] = cur;
			cur = next;
		}
		_tables[i] = nullptr;
	}
}
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

那么这就是本篇文章的全部内容，这里完整的代码就如下：

#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class K,class V>
struct HashNode
{
	HashNode(const pair<K,V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{}
	pair<K, V> _kv;
	HashNode* _next;
};
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 res = 0;
		for (auto& ch : s)
		{
			res *= 131;
			res += ch;
		}
		return res;
	}
};
template<class K, class V, class Hash = HashFunc<K>>
class BucketTable
{
	typedef HashNode<K, V> Node;
public:
	BucketTable()
		:_n(0)
	{
		_tables.resize(__stl_next_prime(_tables.size()));
	}
	Node* Find(const K& key)
	{
		Hash hf;
		size_t pos = hf(key) % _tables.size();
		Node* cur = _tables[pos];
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				return cur;
			}
			else
			{
				cur = cur->_next;
			}
		}
		return nullptr;
	}
	bool insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
		{
			return false;
		}
		if (_n / _tables.size() == 1)//平衡因子为1就更新
		{
			/*vector<Node*> newBH;
			newBH._tables.resize(_n * 2);
			for (auto& cur : _tables)
			{
				while (cur)
				{
					newBH.insert(cur->_kv);
					cur = cur->_next;
				}
			}
			_tables.swap(newBH._tables);*/
			vector<Node*> newBH;
			newBH.resize(__stl_next_prime(_tables.size()));
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					size_t pos = Hash()(cur->_kv.first);
					cur->_next = newBH[pos];
					newBH[pos] = cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
		Hash hf;
		size_t pos = hf(kv.first) % _tables.size();
		Node* newnode = new HashNode<K,V>(kv);
		newnode->_next = _tables[pos];
		_tables[pos] = newnode;
		++_n;
		return true;
	}
	bool erase(const K& key)
	{
		HashFunc<K> HF;
		size_t pos = HF(key) % _tables.size();
		Node* cur = _tables[pos];
		Node* prev = cur;
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				if (cur == _tables[pos])
				{
					_tables[pos] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				_n--;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}
	~BucketTable()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}
	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 (int 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];
	}


private:
	vector<Node*> _tables;
	size_t _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
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