unordered_set和unordered_map的使用和哈希表的实现_unordered_map 字符串哈希

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到logN，即最差情况下需要比较红黑树的高度次。最好的查询是：进行很少的比较次数就能够将元素找到。因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

1.1 unordered_set

unordered_set的文档介绍

1.2 unordered_set的使用

从结果可以看出，里面的数据是无序的。

1.3 unordered_set和set的区别

区别：1. 无序。2. 单向迭代器。3. 查找的效率高，时间复杂度为O(1)。

我们可以验证一下unordered_set的效率：

void test_op()
{
	int n = 10000000;
	vector<int> v;
	v.reserve(n);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		v.push_back(rand());  // 重复多
	}

	size_t begin1 = clock();
	set<int> s;
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();

	size_t begin2 = clock();
	unordered_set<int> us;
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();

	cout << s.size() << endl;

	cout << "set insert:" << end1 - begin1 << endl;
	cout << "unordered_set insert:" << end2 - begin2 << endl;


	size_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	size_t end3 = clock();

	size_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	size_t end4 = clock();
	cout << "set find:" << end3 - begin3 << endl;
	cout << "unordered_set find:" << end4 - begin4 << endl;


	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();

	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "set erase:" << end5 - begin5 << endl;
	cout << "unordered_set erase:" << end6 - begin6 << 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
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

代码的意思是：看两者，插入，查找，删除的运行时间差别。

运行结果如下：

因为rand函数是有最大值的，所以会出现一些重复的值。如果我们想重复少，我们可以这样：

v.push_back(rand()+i);  // 重复少
1

从这两者情况，我们可以看出，不论重复少还是重复多，unordered_set查找的效率都高，插入和删除情况不定。当我们学会底层时，就会明白为什么了吗？

1.4 unordered_map

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过key快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部，unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器。

这个也是同样的道理，大家会一个其它的都类似。

2. 底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.1 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity。capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。
按照上述哈希方式，向集合中插入元素44，会出现问题？
44%10=4，所以和4发生了冲突。这时候我们该怎么办呢？

2.2 哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？

2.3 哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列。

2.4.1 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

那如何寻找下一个空位置呢？
这里有两种方法：
1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。哈希函数：Hash(key)%N+i，i=1，2，3…

假设我们现在想在插入50，50%10=0，但0的位置有数据了，继续往后面找，1的位置也有了，继续往后找，2的位置是空，可以插入。这就是线性探测。但是这样存在一些问题：如果我们想插入1，但是1的位置给占据了，所以这个问题是你占我的，我占它的，造成拥堵的情况。

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题。
2. 二次探测：哈希函数：Hash(key)%N+i^2，i=1，2，3…

此时，我们想插入50就不在2的位置上了，而是在50%10+2*2=4的位置上。
这样做的原因是不会太拥堵。

2.4.2 代码实现闭散列

首先，我们知道底层应该是vector了，但是vector里面放什么呢？

我们这里实现的是kv模型，难道里面存放的就是pair类型的数据吗？

现在我们要查找50，从0的位置开始查找，0位置已经被占据了，再从下一位开始查找，一直往后，找到3的位置。如果我们想要查找60，也是如此，但是到3的位置还没找到，下一位就是空，遇到空就说明不在哈希表里。

如果我们先删除一个数据，然后再查找呢？
比如说：我们先删除30，然后再去查找50。

我们在查找的过程中，遇到2的时候是空，难度我们就说50不在哈希表里面了吗？那么我们该如何去判断，一个空间里是删除还是空呢？我们可以加一个状态。

代表是空，存在，删除。这里我们给一个默认初始化。

这样我们哈希表里面存的就是这个HashData。

2.4.3 插入函数实现

如果要插入一个数据，我们要%一下：

这里我们使用无符号整数，可以解决负数问题。

注意：这里我们%的是size而不是capacity，因为在后面我们需要用[ ]将数据插入进去，[ ]会检查你的下标是否小于size。如果我们要%capacity，可能超过size，这样[ ]就会出错。

如果此时位置的状态为存在，说明有数据，我们需要往后探测。
这里为什么要%一下呢？

如果我们现在想要插入88，88%10=8，所以从下标为8的位置开始探测，9的位置也被占了，再下一步就是10，但是表没有10下标，我们需要再从0开始。所以需要%一下。

当为删除和空时，我们就可以插入了。

插入完成后，我们需要将此位置的状态改成存在。

哈希表什么情况下进行扩容？如何扩容？

所以，载荷因子是非常重要的，我们需要控制一下。当载荷因子为0.7的时候，我们就扩容。那么我们还需要记录一下表里的数据个数。


这里我们不能直接扩容。因为扩容会导致映射关系发生变化，需要重新映射。

这里的思想是：我们定义一个新的哈希表，然后将老的表里数据插入到新的哈希表里，然后再交换。

但是这里我们还没有处理数据重复的情况，我们还要写一个find。

2.4.4 查找和删除函数实现

如果此空间的状态不为空，我们就一直按照之前的的方式来寻找。当为空时，还没找到，就返回空指针。这里不用引用，因为如果我们没有找到，我们可以返回空指针，但是不能返回空引用。如果捕异常，可以用引用。

这里还存在一个问题：如果我们删除了一个数据，还去查找也是能够找的到的。

这样find就写好了，find写好，earse也就差不多了。

找到之后，将数据的状态改成DELETE。

现在还存在一个问题：如果我们传的key不能直接转成无符号整型，我们该怎么办呢？
答案是：我们要利用仿函数来做。

如果可以直接转成无符号整型的类型，我们直接返回就行。这个可以做缺省值。

如果是字符串，我们可以将字符串中字符的ASCII码给加起来。

如果是自定义类型，我们可以将自定义里面的多项拼接。

我们在使用库里面的unordered_set和unordered_map的时候，是不需要传string类型的仿函数的。如果我们也想让它默认，我们可以特化一下。

其余的地方也要修改一下：

线性探测大致都完成了，而构造函数，析构函数，拷贝函数，赋值函数这些都会被vector自动构造，我们不需要自己去写。

2.4.5 二次探测