【C++ 哈希】

哈希

C++STL中提供的底层为红黑树结构的map/set，查找时间复杂度为$O(lo{g}_{2}N)$，最差情况下要比较树高度次，当树中节点很多时，查找效率也不理想。所以C++11新增了底层为哈希结构的关联式容器。
哈希本质是一种映射，通过这种映射关系，可以把一个值放在属于它的位置，同时查找时只需到这个位置上查找即可，这样查找时间复杂度平均为O(1)，哈希方法中使用的转换函数称为哈希函数，构造出来的结构称为哈希表。
但如果有两个值映射到同一个位置上，就会产生冲突。不同关键字通过相同哈希映射出相同的地址，该种现象称为哈希冲突或哈希碰撞。

闭散列—线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入：通过哈希函数转换出地址，从这个位置开始往后遍历，直到找到一个空位置插入数据
查找：通过哈希函数转换出地址，从这个位置往后遍历直到为空
删除：通过哈希函数转换出地址，从这个位置往后遍历直到为空，如果找到就将这个位置的状态设置为”删除“

	enum Stat
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Stat _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		HashTable(size_t size = 10)
		{
			_tables.resize(size);
			_n = 0;
		}

		Data* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._kv.first == key
					&& _tables[hashi]._state == EXIST)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n * 10 / _tables.size() >= 7)
			{
				HashTable<K, V> newTables(_tables.size() * 2);
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXIST)
						newTables.Insert(_tables[i]._kv);
				}
				_tables.swap(newTables._tables);
			}
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		bool Erase(const K& key)
		{
			auto ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		vector<Data> _tables;
		size_t _n;
	};

开散列—哈希桶

开散列法又叫链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

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

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable(size_t size = 10)
		{
			_tables.resize(10, nullptr);
			_n = 0;
		}
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					Node* curr = _tables[i];
					while (curr)
					{
						Node* next = curr->_next;
						delete curr;
						curr = next;
					}
				}
				_tables[i] = nullptr;
			}
		}
		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			if (_tables[hashi])
			{
				Node* curr = _tables[hashi];
				while (curr)
				{
					if (curr->_kv.first == key)
						return curr;
					curr = curr->_next;
				}
			}
			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			Hash hs;
			if (_n == _tables.size())
			{
				vector<Node*> newTables(_tables.size() * 2, nullptr);
				for (auto e : _tables)
				{
					if (e)
					{
						Node* curr = e;
						while (curr)
						{
							Node* next = curr->_next;
							size_t hashi = hs(curr->_kv.first) % newTables.size();

							curr->_next = newTables[hashi];
							newTables[hashi] = curr;

							curr = next;
						}
						e = nullptr;
					}
				}
				_tables.swap(newTables);
			}

			size_t hashi = hs(kv.first) % _tables.size();
			Node* newnode = new Node(kv);

			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			auto ret = Find(key);
			if (ret)
			{
				Node* curr = _tables[hashi];
				if (curr->_kv.first == key)
				{
					_tables[hashi] = curr->_next;
					delete curr;
				}
				else
				{
					while (curr->_next->_kv.first != key)
						curr = curr->_next;
					Node* del = curr->_next;
					curr->_next = del->_next;
					delete del;
				}
				return  true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<Node*> _tables;
		size_t _n;
	};