【C++】哈希（散列）表

一、哈希表的基本概念
- 1.哈希的概念
- 2.哈希冲突
- - 2.1 哈希函数
  - 2.2 哈希冲突的解决办法
  - - 2.2.1 闭散列
    - 2.2.2 开散列
二、哈希表的实现
- 1.闭散列的实现
- - 1.1 闭散列的结构
  - 1.2 闭散列的插入
  - 1.3 闭散列的删除
  - 1.4 闭散列的查找
- 2.开散列的实现
- - 2.1 key值不能取模的情况
  - 2.2 开散列的结构
  - 2.3 开散列的插入
  - 2.4 开散列的删除
  - 2.5 开散列的查找
- 3.完整代码
三、影响哈希表查找效率的因素

一、哈希表的基本概念

1.哈希的概念

在顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次对比。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( $log_2 N$ )，搜索的效率取决于搜索过程中元素的比较次数。
有一种理想的搜索方法是：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：

插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

该方法即为哈希方法，散列方法中使用的转换函数称为哈希函数，构造出来的结构称为哈希表（Hash Table）。

2.哈希冲突

哈希函数可能会把两个或两个以上的不同关键字映射到同一位置，这种情况称为哈希冲突或哈希碰撞，这些冲突的不同关键字称为同义词。
为了尽量减少哈希冲突，一方面要设计更好的哈希函数，另一方面，由于这样的冲突总是不可避免地，所以还要设计好处理冲突的方法。

2.1 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。
哈希函数计算出来的地址能均匀分布在整个空间中。
哈希函数应该比较简单。

常见哈希函数

直接定址法（常用）
取关键字的某个线性函数为散列地址：Hash(Key) = A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法（常用）
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(Key) = Key%p(p<=m)，将关键码转换成哈希地址。
平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址再比如关键字4321，对它平方就是18671041，抽取中间的3位671或710作为哈希地址。
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按散列表表长，取最后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
随机数法
选择一个随机函数，去关键字的随机函数值为它的哈希地址，即H(key) = random(key)，其中random为随机数函数。
通常应用于关键字长度不等时。
数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
假设要存储某家公司的员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转（如1234改成4321）、右环位移（如1234改成4123），左环位移、前两位与后两位数叠加（如1234改成12+34=46等方法）
数学分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

2.2 哈希冲突的解决办法

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

2.2.1 闭散列

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

线性探测法
又称线性探测再散列法， $d_i=1,2,...,m-1$ 。它的特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个地址的元素就会争夺第i+2个地址的元素的地址……从而造成大量元素在相邻的散列地址上**聚集（或堆积）**起来，大大降低了查找效率。
平方探测法
又称二次探测法。 $d_i = 1^2, -1^2, 2^2, -2^2, ..., k^2, -k^2$ ，其中k<=m/2，哈希表长度m必须是一个可以表示成4k+3的素数（为了能够探测到所有空位）。
平方探测法是一种处理冲突的较好方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
双散列法
$d_i = i*Hash_2(key)$ 。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数 $Hash_2(key)$ 计算该关键字的地址增量。它的具体散列函数形式如下： $H_i = (H(key) + i*Hash_2(key)) \% m$
初始探测位置 $H_0=H(key)\%m$ 。i时冲突的次数，初始为0.
伪随机序列法。 $d_i =$ 伪随机数序列。

2.2.2 开散列

开散列：又称拉链法（链地址法、开链法），首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。在这里插入图片描述
从上图可以看出，开散列的每个桶中放的都是发生哈希冲突的元素。

二、哈希表的实现

1.闭散列的实现

在实现时选用了除留余数法和线性探测法。
插入：1.通过哈希函数获取待插入元素在哈希表中的位置。2.如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
在这里插入图片描述
删除：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

1.1 闭散列的结构

为了配合上述伪删除法，可以给哈希表中的元素定义三种状态，EMPTY，EXIST，DELETE，用来代表空、存在和被删除。

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
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
{
	typedef HashData<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{...}
}
private:
	vector<Node> _tables;	
	size_t _n = 0;
};

1.2 闭散列的插入

bool Insert(const pair<K, V>& kv)
{
	// 如果已经存在返回false
	if (Find(kv.first))
	{
		return false;
	}
	// 如果长度为0或者大于负载因子0.7则扩容，降低哈希冲突的概率
	if (_tables.size() == 0 || _n * 10 / _tables.size() > 7)
	{
		size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		HashTable<K, V> newht;
		newht._tables.resize(newsize);
		for (auto& data : _tables)
		{
			if (data._state == EXIST)
			{
				// 这里并不是递归，只是代码复用
				newht.Insert(data._kv);
			}
		}
		_tables.swap(newht._tables);
	}
	size_t hashi = kv.first % _tables.size();
	// 线性探测
	size_t i = 1;
	size_t index = hashi;
	while (_tables[index]._state == EXIST)
	{
		index = hashi + i;
		index %= _tables.size();
		++i;
	}
	_tables[index]._kv = kv;
	_tables[index]._state = EXIST;
	++_n;
	return true;
}

1.3 闭散列的删除

删除操作实现十分简单，只要先通过查找函数找到要删除的结点，再将该结点的状态改为DELETE即可

bool Erase(const K& key)
{
	Node* ret = Find(key);
	if (ret)
	{
		ret->_state = DELETE;
		return true;
	}
	return false;
}

1.4 闭散列的查找

Node* Find(const K& key)
{
	if (_tables.size() == 0)
	{
		return nullptr;
	}
	size_t hashi = key % _tables.size();
	size_t i = 1;
	size_t index = hashi;
	while (_tables[index]._state != EMPTY)
	{
		if (_tables[index]._state != EMPTY
			&& _tables[index]._kv.first == key)
		{
			return &_tables[index];
		}
		index = hashi + i;
		index %= _tables.size();
		++i;
		// 如果已经查找了一圈，说明表中全是删除或存在
		if (index == hashi)
		{
			break;
		}
	}
	return nullptr;
}

2.开散列的实现

2.1 key值不能取模的情况

前面所述的情况都是以整型作为key值，但如果是自定义类型呢？比如string类型，它无法进行取模，此时就需要用到仿函数以及模板特化来解决。
当key为一般类型时就直接返回，当key为string类型时，则采用一种特殊方法将string类型转换成size_t。

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 31;
		}
		return hash;
	}
};

2.2 开散列的结构

开散列的哈希表是最常用的方式，在STL库中，unordered_map和unordered_set也是使用哈希桶的方式实现的。
每一个哈希结点要存储数据和指向下一个同义词的指针。
对于哈希桶，一定要写析构函数，因为开散列会每一个结点可以看作一个链表，默认生成的析构函数只会析构vector自己的空间，这是不够的，还需要删除链表中申请的结点。

template<class T>
struct HashNode
{
	HashNode<T>* _next;
	T _data;

	HashNode(const T& data)
		:_next(nullptr)
		,_data(data)
	{}
};

template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
public:
	typedef HashNode<T> Node;
public:
	~HashTable()
	{
		for (auto& cur : _tables)
		{
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			cur = nullptr;
		}
	}
private:
	vector<Node*> _tables;
	size_t _n = 0;
};

2.3 开散列的插入

开散列的插入其实就是找到要插入的位置之后进行链表的头插。

// 除留余数法最好选取一个素数，这会大大降低哈希冲突的概率。所以下面使用了stl库中的素数表，作为扩容的大小。
size_t GetNextPrime(size_t prime)
{
	static const int __stl_num_prime = 28;
	static const unsigned long __stl_prime_list[__stl_num_prime] =
	{
		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
	};
	size_t i = 0;
	for (; i < __stl_num_prime; ++i)
	{
		if (__stl_prime_list[i] > prime)
		{
			return __stl_prime_list[i];
		}
	}
	return __stl_prime_list[i];
}

pair<iterator, bool> Insert(const T& data)
{
	Hash hash;
	KeyOfT kot;	// 如果是pair类型的元素，将其中的key取出来
	iterator it = Find(kot(data));
	if (it != end())
	{
		return make_pair(it, false);
	}
	// 检查是否需要扩容
	if (_n == _tables.size())
	{
		size_t newsize = GetNextPrime(_tables.size());
		vector<Node*> newtables(newsize, nullptr);
		for (auto& cur : _tables)
		{
			while (cur)
			{
				// 链表头插
				Node* next = cur->_next;
				size_t hashi = hash(kot(cur->_data)) % newtables.size();
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
				cur = next;
			}
		}
		_tables.swap(newtables);
	}
	size_t hashi = hash(kot(data)) % _tables.size();
	// 链表头插
	Node* newnode = new Node(data);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return make_pair(iterator(newnode, this), true);
}

2.4 开散列的删除

开散列的删除就是单链表的删除，如果是头删则让下一个指针做头，如果是在中间删除，则记录前一个结点位置，让前一个结点的next指向删除结点的next。

bool Erase(const K& key)
{
	Hash hash;
	size_t hashi = hash(key) % _tables.size();
	Node* prev = nullptr;
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			if (prev == nullptr)	// 头删
			{
				_tables[hashi] = cur->_next;
			}
			else 	// 中间删除
			{
				prev->_next = cur->_next;
			}
			delete cur;
			return true;
		}
		else
		{
			prev = cur;
			cur = cur->_next;
		}
	}
	return false;
}

2.5 开散列的查找

哈希桶的查找只需要先通过key找到映射的哈希桶，然后去对应的哈希桶中查找结点即可。

iterator Find(const K& key)
{
	Hash hash;
	KeyOfT kot;
	if (_tables.size() == 0)
	{
		return end();
	}
	size_t hashi = hash(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (key == kot(cur->_data))
		{
			return iterator(cur, this);
		}
		cur = cur->_next;
	}
	return end();
}

3.完整代码

其中为哈希桶进行了封装实现unordered_map。
HashTable.h

namespace HashBucket
{
	template<class T>
	struct HashNode
	{
		HashNode<T>* _next;
		T _data;

		HashNode(const T& data)
			:_next(nullptr)
			,_data(data)
		{}
	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	struct __HashIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
		typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
		typedef __HashIterator<K, T, T*, T&, KeyOfT, Hash> iterator;

		Node* _node;
		const HT* _ht;

		__HashIterator(Node* node, const HT* ht)
			:_node(node)
			,_ht(ht)
		{}

		__HashIterator(const iterator& it)
			:_node(it._node)
			, _ht(it._ht)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return s._node != _node;
		}

		Self& operator++()
		{
			if (_node->_next != nullptr)
			{
				_node = _node->_next;
			}
			else
			{
				Hash hash;
				KeyOfT kot;
				size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
				++hashi;
				while (hashi < _ht->_tables.size())
				{
					if (_ht->_tables[hashi])
					{
						_node = _ht->_tables[hashi];
						break;
					}
					else
					{
						++hashi;
					}
				}
				if (hashi == _ht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct __HashIterator;
	public:
		typedef HashNode<T> Node;
		typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
	public:
		~HashTable()
		{
			for (auto& cur : _tables)
			{
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				cur = nullptr;
			}
		}

		iterator begin()
		{
			Node* cur = nullptr;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				cur = _tables[i];
				if (cur)
				{
					break;
				}
			}
			return iterator(cur, this);
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin() const
		{
			Node* cur = nullptr;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				cur = _tables[i];
				if (cur)
				{
					break;
				}
			}
			return const_iterator(cur, this);
		}

		const_iterator end() const
		{
			return const_iterator(nullptr, this);
		}

		size_t GetNextPrime(size_t prime)
		{
			static const int __stl_num_prime = 28;
			static const unsigned long __stl_prime_list[__stl_num_prime] =
			{
				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
			};
			size_t i = 0;
			for (; i < __stl_num_prime; ++i)
			{
				if (__stl_prime_list[i] > prime)
				{
					return __stl_prime_list[i];
				}
			}
			return __stl_prime_list[i];
		}
		
		pair<iterator, bool> Insert(const T& data)
		{
			Hash hash;
			KeyOfT kot;
			iterator it = Find(kot(data));
			if (it != end())
			{
				return make_pair(it, false);
			}
			// 检查是否需要扩容
			if (_n == _tables.size())
			{
				size_t newsize = GetNextPrime(_tables.size());
				vector<Node*> newtables(newsize, nullptr);
				for (auto& cur : _tables)
				{
					while (cur)
					{
						// 链表头插
						Node* next = cur->_next;
						size_t hashi = hash(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
				}
				_tables.swap(newtables);
			}
			size_t hashi = hash(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode, this), true);
		}

		iterator Find(const K& key)
		{
			Hash hash;
			KeyOfT kot;
			if (_tables.size() == 0)
			{
				return end();
			}
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (key == kot(cur->_data))
				{
					return iterator(cur, this);
				}
				cur = cur->_next;
			}
			return end();
		}

		bool Erase(const K& key)
		{
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

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

UnorderedMap.h

#include "HashTable.h"

namespace lgr
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashBucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash>::iterator iterator;
		typedef typename HashBucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		const_iterator begin() const
		{
			return _ht.begin();
		}
		const_iterator end() const
		{
			return _ht.end();
		}
		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		HashBucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
	};

	void test_unordered_map()
	{
		/*unordered_map<int, int> m;
		m.insert(make_pair(1, 1));
		m.insert(make_pair(2, 2));
		m.insert(make_pair(3, 3));
		unordered_map<int, int>::iterator it = m.begin();
		while (it != m.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}*/

		string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };
		unordered_map<string, int> countMap;
		for (auto& e : arr)
		{
			countMap[e]++;
		}

		for (auto& kv : countMap)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
	}
}

三、影响哈希表查找效率的因素

哈希表的查找效率取决于三个因素：哈希函数、处理冲突的方法和负载因子。
负载因子：哈希表的负载因子一般记为α，定义为一个表的装满程度，即 $α = 表中记录数 n / 哈希表长度 m$ 哈希表的平均查找长度依赖于散列表的装填因子α，而不直接依赖于n或m。直观地看，α越大，表示装填的记录越“满”，发生冲突的可能性越大；反之发生冲突的可能性越小。