[数据结构与算法]C++哈希(无序容器，哈希表)

1.unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可以达到log2N，即最差的情况下需要比较红黑树的高度次，当树中的节点非常多的时候，查询的效率也不理想。最好的查询时，进行很少次数的比较可以找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树的结构的关联式容器使用的方式类似，只是其底层的结构不同，本文中只对unordered_map和unordered_set进行介绍，unordered_map和unordered_set可以查看文档介绍，与mutimap和mutiset是一样的。
set和map的底层结构是红黑树，而unordered_map和unordered_set底层的结构是哈希表。不是树结构。

2.unordered_set与unordered_multiset

插入的节点是一个pair类型，它的函数与map几乎是一模一样的，unordered的意思是混序的。

	unordered_set<int> us;
	us.insert(5);
	us.insert(1);
	us.insert(5);
	us.insert(3);
	us.insert(7);
	us.insert(4);
	unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	for (auto& r : us)
	{
		cout << r << " ";
	}

我们发现打印的顺序其实就是我们插入的顺序：

当使用unordered_mutimap进行插入的时候，我们发现遍历的结果将相同的数据放在了一起：

erase等函数也是同理的。
而unordered_map的每一个结构依然是pair结构，详见map和set，这里不多赘述了。

3.unordered系列的效率比较

	int n = 10000000;
	vector<int> v;
	srand(time(0));
	v.reserve(n);
	for (int i = 0; i < n; i++)
	{
		v.push_back(rand());
	}
	set<int> s;
	size_t begin1 = clock();
	for (auto& e : v)
	{
		s.insert(e);
	}
	size_t begin2 = clock();
	unordered_set<int> ss;
	size_t begin3 = clock();
	for (auto& e : v)
	{
		ss.insert(e);
	}
	size_t begin4 = clock();
	cout << "set：" << begin2 - begin1 << endl;
	cout << "unordered_set：" << begin4 - begin3 << endl;
	return 0;

通过比较unordered_set和set的插入效率，我们发现当数据越多的时候，unordered_set的插入效率更高；

同时我们也可以比较它们的删除效率和查找效率，发现都是unordered_set更胜一筹。

4.哈希表

4.1 哈希概念

下面介绍unordered的底层原理：哈希
哈希的本质其实就是一种映射，我们学习排序的时候有一个计数排序，就是类似于哈希实现的。
顺序结构以及平衡树中，元素关键码存储与其存储位置之间没有对应的关系，因此在查找一个元素时，必须经过关键码的多次比较。顺序查找时间复杂度为O(n)，平衡树中为树的高度，即O(log2n)，搜索的效率取决于比较的次数。
理想的搜索方法：不经过任何比较，一次直接从表中得到要搜索的元素，如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间建立一一映射的关系，那么查找时可以通过该函数查找到该元素。

4.2 哈希函数

哈希函数：hash(key)=key%size
即用要插入的函数的值对数组的size取模，得到的值为该值要被存入的数组的下标。该方法称为除留余数法，也是最常用的方法。

用该方法进行搜索时不必进行多次的关键码比较，因此搜索的速度比较快。

4.3负载因子

哈希表的负载因子决定了哈希表什么时候发生扩容，负载因子定义为：
α=填入表中的元素个数/散列表长度
α是散列表装满程度的标志因子。由于表长是定值，α与填入表中的个数成正比。所以α越大，表明表中的元素越多，产生冲突的可能性就越大；反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。
当负载因子越小的时候，发生冲突的可能性越小，效率越高，但是资源浪费也越多；当负载因子较大的时候，资源利用率高，但是发生冲突的可能性大，效率低。

4.4 哈希冲突

在进行插入的时候，可能存在多个值映射到相同的地址的情况，比如13和23都要映射到3这个位置，此时就发生了哈希冲突。
因此在处理哈希冲突的时候有引入了两种方法：闭散列和开散列。两种方法对插入函数的定义也不同。

4.5 闭散列实现哈希

在闭散列的方法中，又分为两种方法：线性探测和二次探测。
线性探测：当发生哈希冲突时，会继续向下遍历数组，直到找到空位置为止。
但是这种方法并不常用，因为如果数组中元素是紧紧挨在一起，遍历的次数过多会降低效率，因此我们引入了二次探测。
二次探测：即发生哈希冲突时，寻找原位置+i^2(i∈0,1,2,3…)的位置，如果发现该位置还存在哈希冲突则i++，然后继续加按原规则加。

4.5.1 实现思路

1.当我们要插入的数据已经存在的时候，不进行插入。
2.当数据个数*10/size>=7的时候，或者没有数据的时候需要进行扩容。
3.依次比对要插入的位置，如果有数据则比对下一个位置，如果没有数据，则插入。
4.删除时，需要将状态置为Delete。

4.5.2 具体实现

namespace close_hash
{
	enum status
	{
		EXITS,
		EMPTY,
		DELETE
	};
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		status _status = EMPTY;
	};
	template<class K, class V>
	class HashTable
	{
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;
	public:
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				--_n;
				ret->_status = DELETE;
				return true;
			}
		}
		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			size_t start = key % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status != EMPTY)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXITS)
					return &_tables[index];
				++i;
				index = start + i * i;
				index %= _tables.size();
			}
			return nullptr;
		}
		bool Insert(const pair<K, V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
			if (_tables.size() == 0 || (_n * 10) / _tables.size() >= 7)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;//判断是否为0，如果为0则扩容为10，如果不为0，则将其置为原来长度的两倍
				//扩容之后容量大小变了，所有元素的位置也变了，需要重新进行插入
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXITS)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			size_t start = kv.first % _tables.size();//注意是size不是capacity，因为访问的时候要掉[i]=kv，[]需要该位置合法才可以
			size_t i = 0;
			size_t index = start + i * i;
			//判断该位置是否存在，这就是引入状态的原因，如果删除一个元素不能将该位置置为空，但是置为任何值都不合适，因此设定一个状态
			while (_tables[index]._status == EXITS)
			{
				i++;
				index = start + i * i;
				index %= _tables.size();//如果发生越界，则向前插入
			}
			_tables[index]._kv = kv;
			_tables[index]._status = EXITS;
			++_n;
			return true;
		}                                           1
	};
}

当希望插入不止是整数的时候，我们可以使用模板的特化，并引入仿函数。

4.6 开散列实现哈希

一次探测和二次探测都不是最好的方法，因为冲突会导致后序的节点互相影响，因此我们引入开散列的概念，开散列又称为哈希桶。
其本质就是让数组的每一个节点是一个链表，当经过哈希函数分析出来的地址和该地址相同的时候，就将节点插入到该链表中。
开散列又称为链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一个子集和，每一个子集合称为一个桶，各个桶中中的元素通过一个单链表链接起来，各链表的头节点存储在哈希表中。

这种方式就是最好的吗，也不是，因为有两种极端的情况:

第一种情况，假设有100个数组空间，如果来了50个值，但是有40个值是发生冲突的，此时就会造成其他空间的浪费。
第二种情况，假设有1000个值，平均每一个桶100个，此时有些桶可能就有上千个值。

解决这一问题的关键和解决闭散列的方式相同，即引入负载因子这一概念，其本质就是通过扩容的方式，将数据分散开。
当一个桶中的数据足够多之后，还可以将它转化成红黑树，这样就可以大大提高查找的效率，比如在java中当桶中的数据达到8的时候，就会将其转换成红黑树，但是在C++中没有进行这样的操作，因为实际上极端的情况并不常见。

4.6.1 实现思路

1.采用头插的方法
2.引入平衡因子进行扩容

4.6.2 具体实现

namespace LinkedHash
{
	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;
		HashNode<K,V>(const pair<K,V>&kv):_kv(kv),_next(nullptr)
		{}
	};
	template<class K,class V>
	class HashTable
	{
		typedef HashNode<K,V> Node;
	private:
		vector<Node*> _tables; 
		size_t _n = 0;
	public:
		bool Erase(const K& key)
		{
			if (_tables.empty())
			{
				return false;
			}
			size_t index = key % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while(cur)
			{
				if (cur->_kv.first == key)//找到了
				{
					if (prev == nullptr)//头删
					{
						_tables[index] = cur->_next;
					}
					else//中间删除
					{
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
		Node* Find(const K& key)
		{
			if (_tables.empty())
			{
				return nullptr;
			}
			size_t index = key % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;
		}
		bool Insert(const pair<K, V>& kv)
		{
			Node* ret = Find(kv.first);
			if (ret)
				return false;
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t index = (cur->_kv.first) % newTables.size();
						cur->_next = newTables[index];
						newTables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}
			size_t index = (kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[index];
			_tables[index] = newnode;
			++_n;
			return true;
		}

	};
}