C++ 哈希表-EW帮帮网

哈希概念

哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

1 直接定址法

当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。

eg.387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

在leecode上这道题目可以很好地解释直接定址法。

class Solution {
public:
    int firstUniqChar(string s) {
        int count[26]={0};
        for(auto ch:s)
        {
            count[ch-'a']++;
        }
        for(size_t i=0;i<s.size();i++)
        {
            if(count[s[i]-'a']==1)
            return i;
        }
        return -1;
    }
};

2 哈希冲突

直接定址法虽然简单直观，但存在显著缺陷。当关键字分布较为离散时，会造成内存资源的大量浪费，甚至出现内存不足的情况。例如，若仅有 N 个取值范围在 [0, 9999] 的数据，要将其映射到长度为 M 的数组中（通常 M ≥ N），此时就需要借助哈希函数 hf，将关键字 key 存储到数组的 h (key) 位置，并且 h (key) 的计算结果必须保证在 [0, M) 区间内。

然而，这种映射方式存在一个关键问题：不同的关键字 key 可能会被映射到数组的同一位置，这种现象被称为哈希冲突或哈希碰撞。从理论上来说，若能找到一个完美的哈希函数，就能完全避免冲突。但在实际应用场景中，哈希冲突无法彻底消除。因此，我们一方面要致力于设计性能优良的哈希函数，以降低冲突发生的频率；另一方面，还需制定有效的冲突解决策略，从而保障哈希表的正常运作和数据存储的准确性。

3 负载因⼦

在哈希表中，负载因子（Load Factor）是一个衡量哈希表空间利用率和性能的重要指标，其定义为哈希表中已存储的元素数量 N 与哈希表总大小 M 的比值，即 负载因子 = N/M。这一概念在不同文献中也被称作载荷因子或装载因子。

负载因子的影响：

冲突概率：负载因子越大，意味着哈希表中的元素越密集，不同关键字通过哈希函数映射到同一位置的可能性显著增加，导致哈希冲突的概率升高。
空间利用率：较高的负载因子表明哈希表空间被充分利用，但可能引发频繁的冲突处理开销；而较低的负载因子虽然减少了冲突概率，却会造成存储空间的浪费。

设计权衡：

当负载因子接近或超过 1 时，哈希表的性能会因频繁冲突而显著下降，通常需要进行扩容操作（增大 M）以维持效率。
常见的哈希表实现会在负载因子达到某个阈值（如 0.75）时自动扩容，以平衡空间利用率和冲突处理成本。

合理控制负载因子是优化哈希表性能的关键，需要根据具体应用场景权衡空间与时间的开销

4 将关键字转为整数

我们将关键字映射到数组中位置，⼀般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后⾯代码实现中再进⾏细节展⽰。下⾯哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的Key是关键字转换成的整数。

5 哈希函数

一个理想的哈希函数应当具备均匀性（Uniformity）和随机性（Randomness），即能将 N 个关键字以等概率的方式均匀映射到哈希表的 M 个槽位中，使每个槽位被占用的概率趋近于 1/M。这种均匀分布可以最小化哈希冲突的发生频率，并确保哈希表的空间利用率达到最优。

尽管完美的均匀分布在实践中难以实现，但通过精心设计哈希函数（如选择合适的散列算法和表大小）并结合动态扩容机制，可以将冲突率控制在合理范围内，从而实现高效的哈希表性能。

5.1 除法散列法/除留余数法

除法散列法原理

除法散列法（除留余数法）是一种常见的哈希函数构建方法。其哈希函数定义为 (h(key)=key % M) ，也就是用关键字 key 除以哈希表大小 M ，所得余数作为该关键字在哈希表中映射位置的下标。

避免取值的原因

2 的幂情况：若 (M = 2^X) ，根据二进制运算规则， (key % 2^X) 实际上等同于保留 key 的后 X 位二进制数。这就导致只要后 X 位相同的不同关键字，计算出的哈希值都一样，容易引发哈希冲突。比如 63（二进制 00111111）和 31（二进制 00011111），当 \(M = 16 = 2^4) 时，二者后 4 位相同，哈希值都是 15 。
10 的幂情况：当 (M = 10^X) 时，(key % 10^X) 本质是保留 key 的后 X 位十进制数。像 112 和 12312 ，当 (M = 100 = 10^2) 时，后两位都是 12，哈希值相同，增加冲突概率。

建议取值

建议 M 取不太接近 2 的整数次幂的一个质数（素数）。因为质数的约数只有 1 和它本身，能使关键字更均匀地分布在哈希表中，减少因数字特性导致的冲突聚集。

Java 中 HashMap 的特殊应用

Java 的 HashMap 采用除法散列法时，哈希表大小 M 取 2 的整数次幂。它并非简单取模，而是利用位运算优化。以 (M = 2^{16}) 为例，先将 key 右移 16 位得到 (key') ，再将 key 和 (key') 进行异或运算，将结果作为哈希值。这样既保证映射值在 ([0, M)) 范围内，又让 key 的所有位都参与计算，使哈希值分布更均匀。这体现了理论和实践的差异，实践中会根据实际需求和性能考量灵活运用哈希方法，而不是单纯遵循理论建议

5.2 乘法散列法

乘法散列法原理

乘法散列法是构建哈希函数的一种方式。它对哈希表大小 M 没有特殊限定。基本步骤如下：

首先，将关键字 key 乘以一个常数 A（(0 < A < 1) ），然后提取出 (key times A) 结果的小数部分。
接着，用哈希表大小 M 乘以刚才提取出的小数部分，并对乘积进行向下取整操作，得到的结果就是关键字 key 对应的哈希值。其哈希函数表达式为 (h(key)=\lfloor M\times((A* key)%1.0)rfloor) ，其中 (lfloor \ \rfloor\) 表示向下取整， (A \in (0, 1)\) 。

常数 A 的取值

Knuth 认为常数 A 取黄金分割点 \(A = (\sqrt{5} - 1)/2 = 0.6180339887\cdots\) 比较理想。选择这个值的原因是，它能让关键字在哈希表中分布得相对更均匀，减少哈希冲突。

示例解析

以给定例子来说，已知 \(M = 1024\) ， \(key = 1234\) ， \(A = 0.6180339887\) 。

先计算 \(A\times key = 0.6180339887*1234 = 762.6539420558\) 。
取出小数部分为 \(0.6539420558\) 。
再计算 \(M*((A*key)\%1.0)=0.6539420558*1024 = 669.6366651392\) 。
最后通过向下取整，得到 \(h(1234)=\lfloor669.6366651392\rfloor = 669\) ，即关键字 1234 通过乘法散列法得到的哈希值为 669 。这种方法通过巧妙的数学运算，将关键字映射到哈希表的相应位置，在一定程度上保证了哈希值的分布均匀性。

5.3 全域散列法

当散列函数公开且固定时，恶意对手可能构造特定数据集，让所有关键字集中映射到哈希表同一位置，引发严重冲突，破坏哈希表正常功能。全域散列通过增加散列函数随机性来抵御这种攻击。它从一组散列函数中随机选取一个用于哈希表操作，使攻击者难以确定能导致最坏情况的数据。

全域散列函数的构造

全域散列函数 \(h_{ab}(key)=((a\times key + b)\%P)\%M\) 。其中：

P 是一个足够大的质数，这是为了保证计算结果的离散性和均匀性，让关键字能更均匀地分布在哈希表中。
a 随机选自 \([1, P - 1]\) 之间的整数， b 随机选自 \([0, P - 1]\) 之间的整数。不同的 a 和 b 组合构成了全域散列函数组。

示例解析

给定 \(P = 17\) ， \(M = 6\) ， \(a = 3\) ， \(b = 4\) ，计算 \(h_{34}(8)\) ：

先计算 \((a\times key + b)\) ，即 \(3×8 + 4 = 28\) 。
再对 \(P = 17\) 取模， \(28\%17 = 11\) 。
最后对 \(M = 6\) 取模， \(11\%6 = 5\) ，所以 \(h_{34}(8) = 5\) 。

6 处理哈希冲突

实践中哈希表⼀般还是选择除法散列法作为哈希函数，当然哈希表⽆论选择什么哈希函数也避免不了冲突，那么插⼊数据时，如何解决冲突呢？主要有两种两种⽅法，开放定址法和链地址法。

6.1 开放定址法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。

线性探测：

• 从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。

• h ( key ) = hash 0 = key % M, hash0位置冲突了，则线性探测公式为：hc ( key , i ) = hashi = ( hash 0 + i ) % M ， i = {1, 2, 3, ..., M − 1}，因为负载因⼦⼩于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。

• 线性探测的⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，

hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位

置，这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。

h(19) = 8 ， h(30) = 8 ， h(5) = 5 ， h(36) = 3 ， h(13) = 2 ， h(20) = 9 ， h(21) =

10 ， h(12) = 1

⼆次探测：

• 从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置；

• h ( key ) = hash 0 = key % M , hash0位置冲突了，则⼆次探测公式为：

hc ( key , i ) = hashi = ( hash 0 ± i 2 ) % M ， i = {1, 2, 3, ...,M/2 }

• ⼆次探测当 hashi = ( hash 0 − i 2 )% M 时，当hashi<0时，需要hashi += M

h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0

6.2 开放定址法代码实现

开放定址法在实践中，不如下⾯讲的链地址法，因为开放定址法解决冲突不管使⽤哪种⽅法，占⽤的都是哈希表中的空间，始终存在互相影响的问题。所以开放定址法，我们简单选择线性探测实现即可。

#pragma once
#include<vector>

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
{
public:
private:
	vector<HashData<K, V>> _tables;
	size_t _n; // 表中存储数据个数
};

扩容

这⾥我们哈希表负载因⼦控制在0.7，当负载因⼦到0.7以后我们就需要扩容了，我们还是按照2倍扩容，但是同时我们要保持哈希表⼤⼩是⼀个质数，第⼀个是质数，2倍后就不是质数了。那么如何解决了，⼀种⽅案就是上⾯1.4.1除法散列中我们讲的Java HashMap的使⽤2的整数幂，但是计算时不能直接取模的改进⽅法。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法，给了⼀个近似2倍的质数表，每次去质数表获取扩容后的⼤⼩。

         static const int __stl_num_primes = 28;
		 static const unsigned long __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
		 };

inline unsigned long __stl_next_prime(unsigned long n)
 {
	 // Note: assumes long is at least 32 bits.
		const unsigned long* first = __stl_prime_list;
	    const unsigned long* last = __stl_prime_list + __stl_num_primes;
	    const unsigned long* pos = lower_bound(first, last, n);
	    return pos == last ? *(last - 1) : *pos;
 }
bool Insert(const pair<K, V>& kv)
{
	// 0.7负载因子就开始扩容
	if ((double)_n / (double)_tables.size() >= 0.7)
	{
		HashTable<K, V, HASH> new_hashtable(__stl_next_prime(_tables.size() + 1));
		for (auto e : _tables)
		{
			new_hashtable.Insert(e._kv);
		}

		_tables.swap(new_hashtable._tables);
	}

	size_t hash0 = kv.first % _tables.size();
	size_t hashi = hash0;
	size_t i = 1;

	// 线性探测
	while (_tables[hashi]._state == EXIST)
	{
		hashi = (hash0 + i) % _tables.size();
		++i;
	}

	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	++_n;

	return true;
}

key不能取模的问题

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函数⽀持把key转换成⼀个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就⽤默认参数即可，如果这个Key不能转换为整形，我们就需要⾃⼰实现⼀个仿函数传给这个参数，实现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整形值不同。string做哈希表的key⾮常常⻅，所以我们可以考虑把string特化⼀下

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

	};

   //特化
	template<>
	class HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t size = 0;
			for (auto e : s)
			{
				size += e;
			}
			return size;
		}
	};

完整代码：

#pragma once
#include<vector>

         static const int __stl_num_primes = 28;
		 static const unsigned long __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
		 };

inline unsigned long __stl_next_prime(unsigned long n)
 {
	 // Note: assumes long is at least 32 bits.
		const unsigned long* first = __stl_prime_list;
	    const unsigned long* last = __stl_prime_list + __stl_num_primes;
	    const unsigned long* pos = lower_bound(first, last, n);
	    return pos == last ? *(last - 1) : *pos;
 }
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 HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}

	};
	template<>
	class HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t size = 0;
			for (auto e : s)
			{
				size += e;
			}
			return size;
		}
	};

	template<class K, class V, class HASH = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable(const size_t n = __stl_next_prime(0))
			:_n(0)
			, _tables(n)
		{}

		bool Insert(const pair<K, V>& kv)
		{
			// 0.7负载因子就开始扩容
			if ((double)_n / (double)_tables.size() >= 0.7)
			{
				HashTable<K, V, HASH> new_hashtable(__stl_next_prime(_tables.size() + 1));
				for (auto e : _tables)
				{
					new_hashtable.Insert(e._kv);
				}

				_tables.swap(new_hashtable._tables);
			}

			size_t hash0 = kv.first % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;

			// 线性探测
			while (_tables[hashi]._state == EXIST)
			{
				hashi = (hash0 + i) % _tables.size();
				++i;
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			size_t hash0 = key % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;

			// 线性探测
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._kv.first == key && _tables[hashi]._state != DELETE)
				{
					return &_tables[hashi];
				}

				hashi = (hash0 + i) % _tables.size();
				++i;
			}
			return nullptr;
		}

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


	private:
		vector<HashData<K, V>> _tables;
		size_t _n; // 表中存储数据个数
	};
}

1.6.3 链地址法

解决冲突的思路

开放定址法中所有的元素都放到哈希表⾥，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶。

h(19) = 8 ， h(30) = 8 ， h(5) = 5 ， h(36) = 3 ， h(13) = 2 ， h(20) = 9 ， h(21) =

10 ， h(12) = 1,h(24) = 2,h(96) = 88

扩容

开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了，可以⼤于1。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；stl中unordered_xxx的最⼤负载因⼦基本控制在1，⼤于1就扩容，我们下⾯实现也使⽤这个⽅式。

极端场景

如果极端场景下，某个桶特别⻓怎么办？其实我们可以考虑使⽤全域散列法，这样就不容易被针对

了。但是假设不是被针对了，⽤了全域散列法，但是偶然情况下，某个桶很⻓，查找效率很低怎么

办？这⾥在Java8的HashMap中当桶的⻓度超过⼀定阀值(8)时就把链表转换成红⿊树。⼀般情况下，不断扩容，单个桶很⻓的场景还是⽐较少的，下⾯我们实现就不搞这么复杂了，这个解决极端场景的思路，⼤家了解⼀下。

1.6.4 链地址法代码实现

	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode* next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, next(nullptr)
		{}
	};

	template<class K,class V ,class Hash=HashFunc<K>>
	class HashBucket
	{
		typedef HashNode<K, V> Node;
	public:

		HashBucket(const size_t n= __stl_next_prime(0))
			:_tables(n,nullptr)
			,_n(0)
		{}

		~HashBucket()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;

				}
				_tables[i] = nullptr;
			}
		}

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

			Hash hs;

			if (_n == _tables.size())
			{
				vector<Node*> newtable(__stl_next_prime(_tables.size()),nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* cur=_tables[i];
					while (cur)
					{
						Node* movenode = cur;
						cur = cur->next;

						size_t hash0 = hs(movenode->_kv.first)% newtable.size();
						movenode->next = newtable[hash0];
						newtable[hash0] = movenode;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtable);
			}
			size_t hash0 = hs(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->next = _tables[hash0];
			_tables[hash0] = newnode;
			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			Hash hs;
			size_t hash0 = key % _tables.size();
			Node* cur = _tables[hash0];
			while (cur != nullptr)
			{
				if (hs(cur->_kv.first) == key)
					return cur;
				cur = cur->next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hash0 = key % _tables.size();
			Node* cur = _tables[hash0];
			Node* prve = nullptr;
			while (cur)
			{
				if (hs(cur->_kv.first)==key)
				{
					if (prve == nullptr)
					{
						_tables[hash0] = cur->next;
					}
					else
					{
						prve->next = cur->next;
					}
					--_n;
					delete cur;
					return true;
				}

				prve = cur;
				cur = cur->next;
			}
			return false;
		}

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

C++ 哈希表