C++哈希+哈希改造

哈希是一种映射，他储存的值和储存的位置需要建立一种固定的映射关系，必须保证依靠这种关系每个key算出来的位置都是同一个

unodered关联式容器

1.几种查找方式的比较

暴力查找：-----O(N)
二分查找: ------O(logN) 缺点：必须有序，数组结构
搜索二叉树:-----O(N) 极端情况下退化成单支
AVLTree/RBTree：-----O(logN) 时间复杂度虽然还行，但是AVL树需要保持左右子树高度差不超过1，红黑树最长路径不超过最短路径的2倍，如果二叉是在查找一些静态的不会变化的数据还可以，但是二者维护较难。
unordered_xxx:查找元素时间复杂度：O（1）因为其在元素存储时就是按照某种特地的规则储存，查找时只要按照相应的规则去查找即可。

2.unordered_map/set

其大致与map/set相似从表面上看，底层实现不一样，最大的区别有三个:
1.无序
2.单向迭代器
3.查找的时候效率高一些
set/unoredred_set增删查效率比较

void Compare_time()
{
	const long N = 1000000;
	vector<int>v;
	v.reserve(N);
	srand((unsigned)time(0));
	for (int i = 0; i < N; ++i)
	{
		//v.push_back(rand()+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();
	cout << begin3 << endl;

	for (auto e : v)
	{
		s.find(e);
	}
	size_t end3 = clock();
	cout << end3 << endl;
	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

上面是debug模式下，下面是release模式下
从上述截图可以看出，插入相同的数据个数，数据重复元素少的话，set的效率比较高，数据重复元素较多的话，unordered_set效率比较高，这涉及到底层哈希表的重构，见下文。
此外，随机数重复的个数少，都是增删查改一千万次，这跟rand()函数有关

哈希

1.哈希概念

理想的搜索方法：不经过任何比较，一次直接从表中得到被搜索的元素，因此：如果能构造一种存储结构，通过某种函数使元素的储存位置与它的关键码之间能够建立——映射关系，那么便可以在O(1)的时间内找到该元素。
1、插入：根据插入元素关键码，通过某种函数计算得出该元素应该储存的位置
2.查找：取到关键码，对其进行同样的计算。把求得的函数当作元素的储存位置，在结构中按此位置取元素比较，若对应关键码相同，搜索成功、
此方法构造出的结构称为哈希表。

2.常见哈希函数

(1).直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
**缺点：**数据范围分布很广，不集中
该方法适合查找范围较小并且连续的情况

(2).除留余数法(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数（一般直接用表大小作除数），按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3.哈希冲突

上述两种方法时比较常见的哈希函数，其他的不做了解，但是有时不同关键字通过相同哈希函数计算出相同的哈希地址，即具有不同关键码而具有相同哈希地址的数据元素称为哈希冲突或者哈希碰撞
而引起哈希冲突一个原因可能是：哈希函数涉及不够合理
哈希函数设计原则：

哈希函数的定义域必须包括需要储存的全部关键码，如果散列表允许有m个地址时，值域必须在0-m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数不能太复杂

(1).哈希冲突解决——闭散列

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

(2).哈希冲突解决——开散列

开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每个子集合称为一个桶，每个桶中元素通过一个单链表连接起来，个链表的头结点储存在哈希表中。
数据不存在表中，表里面储存一个链表指针，冲突的数据以链表的形式挂起来

4.闭散列模拟实现

(1).开散列模拟实现

a.基本数据类型

枚举标记每个空间
RMPTY此位置为空
EXITS此位置已经有元素
DELETE元素已删除

enum State
	{
		EMPTY,
		EXITS,
		DELETE
	};
1
2
3
4
5
6

底层用vector实现，vector的元素类型是Data
其中Data

template<class K,class V>
	struct  HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};
	//_kv 表示元素
	//_state表示的是状态
	//每次插入或者删除必须调整该位置state的值
1
2
3
4
5
6
7
8
9

b.哈希表的扩容

思考：哈希表在什么情况下进行扩容？如何扩容？

即载荷因子过大时查表时，cpu缓存命中率低，我模拟实现的载荷因子取的是0.7
HashFunc表示仿函数

bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//负载因子达到0.7及以上，就扩容
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//扩容之后需要重新映射
				HashTable<K,V,HashFunc>newHT;
				newHT._tables.resize(newSize);
				//遍历旧表，插入newHT
				for (auto& e : _tables)
				{
					if (e._state == EXITS)
					{
						//因为扩容之后负载因子是不可能超过0.7
						//也就说明此时再调用Insert
						//不会进入if条件里面的语句。

						newHT.Insert(e._kv);
					}

				}
				newHT._tables.swap(_tables);
			}
			HashFunc hf;
			size_t starti = hf(kv.first);
			starti %= _tables.size();
			size_t hashi = starti;
			size_t i = 1;
			//线性探/二次探测
			while (_tables[hashi]._state == EXITS)
			{
				hashi = starti + i;
				++i;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXITS;
			_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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

在vector对象size()为0或者大于等于载荷因子时扩容，扩容的时候，重新定义一个哈希表，遍历原vector中元素插入到新的哈希表中，最后将新哈希表中的vector对象和原来vector对象交换即可

(2).开散列表的实现

a.基本数据类型

由于闭散列表的实现方式是链表，所以其节点的类型是元素+指针

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)
		{}

	};
1
2
3
4
5
6
7
8
9
10
11

b.哈希表的扩容

闭散列中负载因子不能太大，否则会造成cpu缓存率降低，而在拉链法（开散列）中，如果负载因子过大，则容易造成冲突，这点与上述闭散列一致，但是如果负载因子过小，会造成空间的消耗高一些。
所以我们的负载因子取1，也就是平均下来每个桶挂一个，这样的话综合效率还是不错的。
Insert不加仿函数版本

bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//负载因子==1 扩容
			if (_tables.size() == _n)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

				vector<Node*>newTable;
				newTable.resize(newSize, nullptr);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = cur->_kv.first % newSize;
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;
						cur = next;
						//这样原链表的节点可以直接运用
						//不用再new新的节点

					}

				}
				newTable.swap(_tables);

			}
			size_t hashi = kv.first;
			hashi %= _tables.size();
			//此时头插到对应的桶即可
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = 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
30
31
32
33
34
35
36
37
38
39
40
41

按照上述写法，原链表结点可以直接运用，不用再new新的结点，这是一种结点转移。

析构函数 拉链发的析构函数还是要我们自己完成的，因为默认的析构函数只会析构vector，但是不会析构vector中的指针，如果不自觉实现析构函数，会出现内存泄露.
拷贝构造也同理

c.开散列与闭散列的比较

应用链地址法处理溢出，需要增设链表指针，似乎是增加了储存开销，事实上，由于开地址法必须保持大量的空闲空间以保证搜索效率，如二次探查法要求载荷因子<=0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省储存空间。

5.为什么模拟实现仿函数

思考：上述key元素类型都是整数，其他类型该如何解决？
可以模仿之前map/set中key的提取方式。
可以利用仿函数来达到目的，哈希表的底层默认是整形，但是unordered_set/map传进来的自定义的类型，必须实现相应的仿函数，仿函数的作用是将自定义类型转换为整形。
具体用法如下：模拟实现unordered_map/set

哈希表的改造

根据上述的比较可以了解到，开散列相比于闭散列而言优势要大一点，则哈希表实现unordered_set/map用开散列实现。

1.函数特化

在上述方法中，我们最终都是要将key转变成整数，否则不能取模，所以当我们的key是自定义类型的时候这个时候就需要仿函数，仿函数的作用是将自定义类型对象转变成整数。又因为在日常中用到string的次数太多，所以直接将string这个类特化
字符串哈希算法
根据前人的实验数据，我模拟实现了一个string的特化。

template<class K>
	struct DefaultHash//默认仿函数实现的是整形
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//特化,因为string类型实在是太多了，所以直接特化
	template<>
	struct DefaultHash<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash = hash * 131 + e;
			}
			return hash;
		}

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

**小结：**仿函数的作用是将自定义类型转变成size_t，同时仿函数的定义我们要尽量避免产生相同的整数，数字相同越多，冲突越多，约不利于查找。

2.哈希迭代器

template<class K,class T,class KeyOfT,class HashFunc>
    class __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;
	public:
		Node* _node;
		HashTable<K, T, KeyOfT, HashFunc>* _pht;//为了重新构开散列
1
2
3
4
5
6
7
8

K,T,与之前的map/set实现中一样
KeyOfT：去类中的key，且这个仿函数是unordered_map/set中的一个内部类
_pht:因为迭代器在++的时候，当一个链表走到结尾，需要找另一个桶时，此时需要哈希指针完成。

3.哈希表

template<class K, class T,class KeyOfT,class HashFunc>
	class HashTable
	{
		template<class K, class T, class KeyOfT, class HashFunc>
		friend class __HTIterator;
		typedef HashNode<T>Node;
	public:
		typedef __HTIterator<K, T, KeyOfT, HashFunc>iterator;
1
2
3
4
5
6
7
8

在哈希表中，一定要写__HTIterator是右元类，因为在迭代器的实现中会用到哈希表的私有变量vector_tables;
其他的其实与上述开散列的实现差不多。
哈希表完整代码实现

4.提示

(1).typename

typedef typename Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc>::iterator iterator;
1

无论是在map还是在set中，只要是调用类的内嵌类型就必须加typename，如果不加，无法区分类域中的iterator是静态成员变量还是内嵌类型。

(2).最前面声明哈希类

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

在迭代器类定义之前必须要有一个声明，因为此时涉及到你调用我我调用你的问题，编译器编译的时候只会向上寻找，不会向下寻找，而此时无论是迭代器还是HashTable都会调用彼此，此时的解决办法是在最前面声明HashTable,告诉编译器这是一个类，因此编译器在迭代器编译的时候即使找不到定义，但是却可以找到声明，这也是可以编译通过的。

(3).为什么函数模板可以自动推导类型但类模板却不能

因为函数可以传参数，可以根据传的参数类型根据函数模板实例化出函数，但是类模板没有机会传参数，eg:
vector d1,此时如果不显示传参写成vector的话，就无法得到模板类型,当然函数模板显示实例化其实也没错，只是没必要罢了。