C++知识点 – 哈希表

---

一、unordered系列关联式容器

unordered_map和unordered_set都是unordered系列关联式容器，它们与map和set用法大部分类似，不同点在于：
1.map和set遍历是有序的，unordered系列的遍历是无序的；
2.map和set是双向迭代器，unordered系列是单向迭代器；
unordered系列容器的优势在于：增删查改的效率更优；

二、哈希概念

哈希/散列：值跟存储位置建立映射关联关系；

1.哈希函数

将插入的数据的key值代入哈希函数，得到数据在散列中的存储位置，建立值跟存储位置的映射关系；
常见的哈希函数有：
除留余数法：设散列表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p (p < m)，将关键码转换为哈希地址；

2.哈希冲突

不同哈希函数通过相同的哈希函数计算出了相同的哈希地址，这种现象就叫做哈希冲突；

解决哈希冲突的办法有：

（1）闭散列
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，可以把key存放到冲突位置的下一个空位置中；
<1>线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止；
哈希删除时，不能随便删除哈希表中已有的元素，若直接删除元素，将会影响其他元素的搜索，因此线性探测采用标记的伪删除法来删除一个元素；

<2>二次探测
线性探测在某个位置冲突很多的情况下，会出现效率低下的情况，此时可以使用二次探测，当发生哈希冲突时，并不是从冲突位置依次向后探测，而是每次向后探测 i ^ 2个位置，每次发生哈希冲突时，都++i；

（2）开散列/拉链法
再用哈希函数计算出散列地址后，具有相同地址的关键码归于同一子集，每一个子集合称为一个桶，各个桶中的元素通过单链表连接起来，各链表的头节点存储在哈希表中；

3.负载因子

散列表的负载因子定义为 α = 填入表中的元素个数 / 散列表的长度；
负载因子越大，冲突的概率就越大；
负载因子应该严格限制在0.7 - 0.8以下，在负载因子达到了一个基准值后，哈希表就应该扩容了；
基准值越大，冲突越多，效率越低，空间利用率越高；

三、闭散列的实现

1.结构

namespace CloseHash
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

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

	template<class K, class V>
	class HashTable
	{
	public:

	private:
		vector<HashData<K, V>> _table;
		size_t _size = 0; // 存储多少个有效数据
	};
}

其中，State是用来表明每个哈希单元的状态的，EMPTY表示该单元是空的，EXIST表示该单元已存储了数据，DELETE表示该单元的数据已经被删除；
哈希表的私有成员包括数据类型是HashData的vector外，还有表明当前已存储多少个有效数据的size；

2.Insert

使用除留余数法作为哈希函数，闭散列的方法来解决哈希冲突，在此基础上设计Insert；
某些数据类型（如string）是不能直接进行取余运算的，这时就需要借助仿函数，将该数据类型转化为无符号整型，使其能够进行取余运算；
为防止不同字符串有相同的ASCII码的和，所以引入字符串的哈希函数，每次加一个字母的ASCII码后，都×131

	template<class K>
	struct HashFunc
	{
		//普通仿函数，能直接转换的类型就会调用这个仿函数
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct HashFunc<string>
	{
		// string的特化版本，string类型的数据会调用这个仿函数
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (auto ch : key)
			{
				val *= 131;
				val += ch;
			}
			return val;
		}
	};

在扩容时，可以定义一个新的哈希表，复用Insert将旧表的数据插入到新表中；

		bool Insert(const pair<K, V>& kv)
		{
			//负载因子到了就扩容
			if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
			{
				size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;				
				HashTable<K, V>* newHT = new HashTable;
				newHT->_table.resize(newSize);
				//旧表的数据映射到新表
				for (auto e : _table)
				{
					if (e._state == EXIST)
					{
						newHT->Insert(e._kv);
					}
				}
				_table.swap(newHT->_table);
			}

			Hash hash;
			size_t hashi = hash(kv.first) % _table.size();//哈希函数
			//线性探测
			while (_table[hashi]._state == EXIST)
			{
				hashi++;
				hashi %= _table.size();//防止hashi超过table的大小，超过了就返回最前面
			}

			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_size;

			return true;
		}

3.Find

		HashData<K, V>* Find(const K& key)
		{
			if (_table.size() == 0)
			{
				return nullptr;
			}

			Hash hash;
			size_t start = hash(key) % _table.size();
			size_t hashi = start;
			
			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
				{
					return &_table[hashi];
				}

				hashi++;
				hashi %= _table.size();

				if (hashi == start)//又找回起始位置了，就是没找到
				{
					break;
				}
			}

			return nullptr;
		}

4.Erase

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				_size--;
				return true;
			}
			else
			{
				return false;
			}
		}

5.Print

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]._state == EXIST)
				{
					printf("[%d:%d] ", i, _tables[i]._kv.first);
				}
				else
				{
					printf("[%d:*] ", i);
				}
			}
			cout << endl;
		}

四、开散列实现

1.结构

开散列使用哈希桶的结构，产生冲突的节点使用链表连接在同一个散列的节点上；

namespace Bucket
{
	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:

	private:
		vector<Node*> _tables;
		size_t size = 0;
	};
}

2.Insert

（1）开散列的Insert使用哈希函数得到key的地址，将节点挂载到哈希表上，若出现哈希冲突，则使用头插法将节点插入到哈希桶中；
（2）扩容时，不光要移动哈希表中的元素，也要将哈希桶中的元素依次连接到新表上；
（3）哈希表的大小为素数时，发生冲突的概率会减小，因此可以创建一个素数表，每次扩容时从中取一个素数作为新表的大小；

		inline size_t __stl_next_prime(size_t n)
		{
			static const size_t __stl_num_primes = 28;
			static const size_t __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (size_t i = 0; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > n)
				{
					return __stl_prime_list[i];
				}
			}

			return -1;
		}

		bool Insert(const pair<K, V>& kv)
		{
			//去重
			if (Find(kv.first))
			{
				return false;
			}

			Hash hash;
			//负载因子到1就扩容
			if (_size / _tables.size() == 1)
			{
				vector<Node*> newTables;
				newTables.resize(__stl_next_prime(_tables.size()), nullptr);
				//将旧表中的节点映射到新表

				for (int i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)//cur不为空时，就是挂载了节点
					{
						Node* next = cur->_next;
						size_t hashi = hash(cur->_kv.first) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newTables);//交换新旧哈希表
			}

			//插入新节点
			size_t hashi = hash(kv.first) % _tables.size();
			//头插
			Node* newNode = new Node(kv);
			newNode->_next = _tables[hashi];
			_tables[hashi] = newNode;
			++_size;

			return true;
		}

3.Find

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

4.析构函数

由于在vector调用默认析构释放后，其节点下挂载的哈希桶没有被释放，所以需要自己写析构函数，完成哈希桶的释放；

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

5.Erase

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)//找到
				{
					//头删
					if (prev == nullptr)
					{
						cur = cur->_next;
					}
					//中间删
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_size;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}
			//没找到
			return false;
		}

6.Size等

		//哈希表中的数据个数
		size_t Size()
		{
			return _size;
		}

		//使用的桶的个数
		size_t BucketNum()
		{
			size_t num = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					num++;
				}
			}
			return num;
		}

		//表的长度
		size_t TableSize()
		{
			return _tables.size();
		}

7.MaxBucketLenth

最长的哈希桶的长度

		size_t MaxBucketLenth()
		{
			size_t maxLen = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				size_t len = 0;
				Node* cur = _tables[i];
				while (cur)
				{
					++len;
					cur = cur->_next;
				}

				if (len > maxLen)
				{
					maxLen = len;
				}
			}
			return maxLen;
		}