【C++】【哈希表】【哈希函数】实现自己的哈希表，解决哈希冲突；动态哈希表；_c++哈希表函数

---

前言

1、哈希表与哈希函数的引入

就像这道题来说，用一个26个的int 型数组，就可以实现对每个字符进行哈希映射。

其中哈希函数为：f(char) = char -‘a’ ;哈希表就是那个int [26]；

这种简单的哈希函数就处理了从键到索引的转换，同时也是简单的一一对应的。

而更复杂的问题，通常会使得不同的键映射成为同样的索引，这就是哈希冲突。

而我们所需要处理的就是解决哈希冲突。

2、哈希表

哈希表的实现，体现了算法设计领域的经典思想：空间换时间。

哈希表就是在时间和空间之间的平衡

因为哈希表的两个极端就是

无限的空间：对应O(1) 的查找复杂度；

O(1）的空间：对应O(n)的查找复杂度；

所以哈希函数的设计很重要。希望哈希函数能将“键”映射成的“索引”分布的越均匀越好。

3、哈希表优劣

哈希表的均摊复杂度为O(1)；

时间复杂度比平衡树(O(logn))更低，但是失去了顺序性。

对于平衡树来说，更容易获取最值、topK值、某值排名、排名第几的值、前驱后继。

一、设计

1、一般、通用哈希函数的设计

常用的哈希函数：转成整形处理

遵循：

• 一致性：一样的键对应一样的哈希映射
• 高效性：计算高效便捷
• 均匀性：哈希值均匀分布(取模）

一般性：

1. 小范围的正整数直接使用
2. 小范围的负整数进行偏移（偏移到正整数）
3. 大整数：取模
4. 浮点数：转换成整数。
5. 字符串：转换成整数。
6. 对于复合类型(如日期)：转换成为字符串处理

其中大整数的取模：

简单的模造成：分布不均、没有利用所有信息。而通常模一个素数，不是合数。且根据数据规模的大小，素数的选取也是有人在研究的。即不同的素数模造成的哈希冲突的概率问题。

其中浮点数：

计算机中都是用32位、64位二进制存储，然后重新解析成为的浮点数。那我们直接用这个二进制当作整数来映射是一样的。同样套用大整数来取模即可。

其中字符串：

字符串如果表示的十进制：就转换成十进制整数来做
字符串表示的是字母，就按照26进制（或者更大进制）转换为整数来做。
如下图：M代表的就是素数模，同时也是哈希表的大小。B代表的就是根据字符串来定的进制数。
其中hash函数向下优化分别：简化了运算、利用多次取模避免溢出(同时结果不会有影响,即，多次取模和最后取模结果一样，但是避免了中间溢出）

2、默认哈希函数

C++中有默认哈希函数对象类。在“functional”中。

我们可以使用其哈希函数，打印出来对应的映射。

#include <functional>
#include <string>
int main() {
    std::hash<int> hash_int;
    std::hash<double> hash_double;
    std::hash<std::string> hash_string;
    int a = 42;
    std::cout << hash_int(a) << std::endl;

    int b = -42;
    std::cout << hash_int(b) << std::endl;

    double c = 3.1415926;
    std::cout << hash_double(c) << std::endl;

    std::string d = "temp";
    std::cout << hash_string(d) << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二、哈希冲突

1、链地址法。(seperate chaining )

java哈希表解决哈希冲突就是用的链地址法。

哈希表就是一个M大小的数组(M为取模值）。

对应位置存储链表，将其冲突value 挂在链表上。

当然也有使用tree map 实现的。即每个位置存的都是一个红黑树。(tree map一般都是红黑树实现)

时间复杂度：哈希表M大，数据N个。及，每个地址存的数据为n/m个。得出：

如果用链表存储：O(n/m）//遍历链表
如果用平衡树存储：O(log(n/m)）//遍历tree

但是极端情况（哈希函数设置不恰当）使得所有数据都哈希冲突，所有的n都存在一个位置。那么时间复杂度变成O(n）和O(log(n)）；

信息安全中有种攻击方法就是利用这种机制：哈希碰撞攻击：通过了解哈希值的计算方法，设计一套数据，以实现所有数据产生哈希冲突，使得其哈希表时间复杂度变坏，拖慢系统运行速度。

1.1、实现

重点：

1. 申请的是map的数组；即底层用的是平衡树，而不是链表。要求key可比较。
2. 通过位与将hash计算出来的数修改成正数，能作为索引使用
3. 构造函数可以互相调用
4. 得到map用指针操作，以减少多次hash计算的消耗。同样用引用也可以。

template<typename Key, typename Value>
class HashTable {
private:
	int M;
	int size;
	map<Key, Value> *hashTable; //map 的数组

	int hash(Key key) {
		return (hashCode(key) & 0x7fffffff) % M; //负数转正数
	}

	int hashCode(Key key) { //用C++ 的hash函数
		std::hash<Key> key_hash;
		return key_hash(key);
	}

public:

	HashTable(int M) {
		this->M = M;
		size = 0;
		hashTable = new map<Key, Value>[M];
	}

	HashTable() {
		this->M = 97;
		new(this)HashTable(M); //调用构造函数
	}

	int getSize() {
		return size;
	}

	void add(Key key, Value value) {
		map<Key, Value> *my_map = &hashTable[hash(key)]; //指针，使得只hash运算一次。
		if (my_map->count(key)) {
			my_map->find(key)->second= value;
		}
		else {
			my_map->insert(make_pair(key, value));
			size++;
		}
	}

	Value *remove(Key key) {
		Value temp;
		map<Key, Value> *my_map = &hashTable[hash(key)];
		if (my_map->count(key))
		{
			temp = my_map->find(key)->second;
			my_map->erase(key);
			size--;
		}

		return &temp; //注意这里有问题
		//最好改成new出来，使用完了delete掉。尽量不用值传递，和传局部变量指针。
		//或者在调用他的地方创建一个value，然后改造函数成传入value指针，直接把数据复制到那里去即可。就不用返回值了
	}

	bool contains(Key key) {
		return hashTable[hash(key)].count(key);
	}

	Value *get(Key key) {
		return &(hashTable[hash(key)])[key]; //传地址。以防value 是大型数据结构
	}

	void set(Key key, Value value) {
		map<Key, Value> &my_map = hashTable[hash(key)]; //引用， 使得只hash运算一次。
		if (!my_map.count(key)) {
			throw to_string(key) + " doesn't exist";
		}
		//assert(my_map.count(key)!=0);
		my_map.find(key)->second = value;
	}
};
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

1.2、测试

void main()
{
	HashTable<int, int> temp;

	temp.add(1, 2);
	cout << *(temp.get(1)) << endl;
	temp.add(1, 3);
	cout << *(temp.get(1)) << endl;
	temp.set(1, 5);
	cout << *(temp.get(1)) << endl;

	cout << boolalpha << temp.contains(1) << endl;
	cout << boolalpha << temp.contains(2) << endl;
	try { 
		temp.set(2, 5); }
	catch (const string msg){ 
		cerr << msg << endl; }

	//int *mm = (temp.remove(1));
	//cout<< (void*)mm << endl;
	cout << *(temp.remove(1)) << endl;
	cout << boolalpha << temp.contains(1) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.3、哈希表的动态空间优化

上述哈希表实现的时间复杂度强相关于哈希表大小M，那么就可以通过改造哈希表容量，来真正实现哈希表0(1)的时间复杂度。

即设定上下边界，当N/M>= upperTol，即数据量与哈希表大小的比值超过上界，就扩容。
当N/M< lowerTol，即数据量与哈希表大小的比值少于下界，就缩容。

时间复杂度分析：

实际上均摊复杂度还是O(1)；

因为查询的时候每个map存的个数是lowerTol~upperTol之间个数。而这两个数是常数，与数据量无关，所以各种操作的时间复杂度为O(1)；再加上扩容与缩容均摊还是O(1)；

1.4、实现

重点：

1. add 的时候 size >=upperTol * M 的时候，扩容到两倍。
2. remove的时候 size <lowerTol *M 的时候 ，缩容到一半。
3. resize 的时候申请一块区域，然后一个一个重新用新的M rehash出新的index 来存储。

当前实现的扩容与缩容都是二倍关系，但是前面讲了这个模最好是素数才能使得哈希表均匀。（有论文得出某些固定的素数更优）。

如果要改进，只需要在扩容的时候选择下一个合适的素数，缩容的时候同样如此。

template<typename Key, typename Value>
class HashTable {
private:
	static const int upperTol = 10;
	static const int lowerTol = 2;
	static const int initCapacity = 7;
	int M;
	int size;
	map<Key, Value> *hashTable; //map 的数组

	int hash(Key key) {
		return (hashCode(key) & 0x7fffffff) % M; //负数转正数
	}

	int hashCode(Key key) { //用C++ 的hash函数
		std::hash<Key> key_hash;
		return key_hash(key);
	}	
	void resize(int new_M)
	{
		map < Key, Value> *newhashTable = new map<Key, Value>[new_M];

		int oldM = M;
		this->M = new_M;
		for (int i = 0; i < oldM; i++)
		{
			map<Key, Value> &my_map = hashTable[i];
			for (auto[ind, val] : my_map)
			{
				newhashTable[hash(ind)].insert(make_pair(ind, val));
			}
			
		}
		delete[]hashTable;
		hashTable = nullptr;
		this->hashTable = newhashTable;
	}

public:

	HashTable(int M) {
		this->M = M;
		size = 0;
		hashTable = new map<Key, Value>[M];
	}

	HashTable() {
		this->M = initCapacity;
		new(this)HashTable(M); //调用构造函数
	}

	int getSize() {
		return size;
	}

	void add(Key key, Value value) {
		map<Key, Value> *my_map = &hashTable[hash(key)]; //指针，使得只hash运算一次。
		if (my_map->count(key)) {
			my_map->find(key)->second= value;
		}
		else {
			my_map->insert(make_pair(key, value));
			size++;

			if (size >= upperTol * M)
				resize(2 * M);
		}
	}

	Value remove(Key key) {
		Value temp;
		map<Key, Value> *my_map = &hashTable[hash(key)];
		if (my_map->count(key))
		{
			temp = my_map->find(key)->second;
			my_map->erase(key);
			size--;

			if (size < lowerTol * M && M / 2 >= initCapacity)
				resize(M / 2);
		}
		return temp; 

	}



	bool contains(Key key) {
		return hashTable[hash(key)].count(key);
	}

	Value *get(Key key) {
		return &(hashTable[hash(key)])[key]; //传地址。以防value 是大型数据结构
	}

	void set(Key key, Value value) {
		map<Key, Value> &my_map = hashTable[hash(key)]; //引用， 使得只hash运算一次。
		if (!my_map.count(key)) {
			throw to_string(key) + " doesn't exist";
		}
		//assert(my_map.count(key)!=0);
		my_map.find(key)->second = value;
	}
};
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

1.5、测试

void main()
{
		HashTable<int, int> temp;

	temp.add(1, 2);
	cout << *(temp.get(1)) << endl;
	temp.add(1, 3);
	cout << "size = " << temp.getSize() << endl;
	for(int i =1;i<1000000;i++)
		temp.add(i, 2*i);

	cout <<"size = " <<temp.getSize() << endl;
	cout << *(temp.get(1)) << endl;
	temp.set(1, 5);
	cout << *(temp.get(1)) << endl;

	cout << boolalpha << temp.contains(1) << endl;
	cout << boolalpha << temp.contains(2) << endl;
	try { 
		temp.set(2, 5); }
	catch (const string msg){ 
		cerr << msg << endl; }


	cout << temp.remove(1) << endl;
	cout << boolalpha << temp.contains(1) << endl;
}
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

2、其他哈希冲突解决办法

2.1、开放地址法

哈希冲突了，就像下探测，找到空的来存。使得每个空间只存一个数据。

向下探测分为了线性探测、平方探测、二次哈希。线性探测较平方探测消耗较大。

扩容机制：其包含一个负载率，当负载率超过一定值，就扩容。

2.1、more

再哈希法(rehashing)、coalesced hashing

---

参考

模板类、模板函数设计

bobo老师github