哈希表相关概念

• 哈希函数：直接定址法的缺点也十分明显，当key值的分布范围比较分散时，会导致开的内存空间极大，甚至有很多浪费。假设，我们的数据范围是0~9999的N个值，我们一开始开一块大小为M的空间，我们需要构造一个哈希函数（hash function）hf，关键字key的数据被放在hf(key)的位置上，hf(key)的值必须在[0, M)之间。
• 哈希冲突：还有一个问题，两个不同的key可能会映射到同一个位置上，这种情况叫哈希冲突，或哈希碰撞。最理想的情况是，设计出一种好的哈希函数避免冲突。但是实际应用中，冲突是不可避免的，我们只能尽可能设计出尽可能优秀的哈希函数，尽可能减少冲突。
• 负载因子：假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子 = N/M。负载因子越大，哈希冲突的概率越高，空间利用率也高；负载因子越小，哈希冲突的概率越低，空间利用率也越低。

2. 除法散列法

除了直接定址法，常用的哈希映射方法还有除法散列法，下面我们也使用这种方法实现哈希函数。 除法散列法，也叫除留余数法。假设哈希表的大小为M，那么key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。 使用除法散列法时，要尽量避免使用2的幂次、10的幂次之类的值。因为key%2x相当于留下key的二进制的后x位，key%10x相当于留下key的十进制的后x位，就更容易导致哈希冲突。根据前人的总结，M最好取不接近2的整数次幂的质数。

3. 将关键字转为整数

除留余数法最重要的要求是，key能够取模，因此key的类型必须是整数或能转换为整数。

代码语言：javascript

AI代码解释

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

key是无法直接强制转换为整型的类型时，如string，就可以对hashFunc进行模板特化，单独写一个方法：字符串转换为整型，可以选择直接把字符的ASCII值相加，但是这样计算类似“abcd”和“acdb”结果是一样的。前人总结出的一个绝佳方法是，上一次计算的结果乘以一个质数，一般是31或131：

代码语言：javascript

AI代码解释

// string特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key) const
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};

4. 处理哈希冲突

哈希冲突是避免不了的，所以需要学会处理哈希冲突。处理方式一般有开放定址法、链地址法。 例如，将一组数据30、19、5、36、13、20、21、12映射到大小为11的表中，则h(key) = key % 11。h(30) = 8，h(19) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1。哈希函数算出的值即为存储它们的数组下标，注意到h(30) = h(19)，两个数据的存储位置冲突了。

4.1 开放定址法

开放定址法是，当一个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的空位置进行存储，开放定址法中负载因子一定是小于1的。寻找空位置的规则有三种：线性探测、二次探测、双重探测。

• 线性探测：从发生冲突的位置开始，依次线性向后探测，直到找到下一个没有存储数据的位置为止，如果找到哈希表尾，则回到哈希表头的位置。因为负载因子小于1，所以最多探测M-1次，一定能找到一个存储key的位置。 h(key) = hashi = (hash0+i) % M， i = {1, 2, 3, …, M-1} 线性探测比较简单而且容易实现，但缺点是如果出现位置的连续冲突，多个数据按照插入顺序的不同可能造成位置混乱，争夺同一个位置，这种现象叫做群集（堆积）。
• 二次探测：从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。hash0位置冲突了，则二次探测公式为： h(key) = hash0 = key % M hc(key, i) = hashi = (hash0 ± i2) % M， i = {1, 2, 3, …, M/2 } 当 hashi = (hash0 − i2)%M 时，当hashi<0时，需要hashi += M

下面我们主要使用线性探测，用开放定址法实现哈希表： 先搭出框子：

代码语言：javascript

AI代码解释

namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY, 
		DELETE
	};
	
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};
	
	template<class K,class V>
	class HashTable
	{
	private:
		vector<HashData<K, V>> _tables;
		// 记录实际存储数据个数
		size_t _n = 0;
	};
}

要注意的是，我们需要给每个存储值的位置加一个状态标识，否则删除值时，会影响后面新插入的值无法判断这个位置的状态。