当前位置： 首页 > article >正文

哈希——哈希表处理哈希冲突的方法

article 2024/11/5 13:46:30

 处理哈希冲突

  • 实践中哈希表⼀般还是选择除法散列法作为哈希函数。

当然哈希表无论选择什么哈希函数也避免不了冲突（主要作用就是减少冲突），那么插入数据时，如何解决冲突呢？主要有两种两种方法，开放定址法和链地址法。
 

开放定址法

线性探测 

  • 从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。
  • h(key) = hash0 = key % M,  hash0位置冲突了，则线性探测公式为：hc(key, i) = hashi = (hash0 + i) % M，i = {1, 2, 3, ..., M - 1}，因为负载因子小于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。
  • 线性探测的比较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下面的⼆次探测可以⼀定程度改善这个问题。

简单点说，就是线性探测会发生堆积问题，以下面的图来说，19占了（8）的位置，30经过哈希函数也是要插到（8）的位置，但（8）有值， 就往后插了；20要插（9）也往后插了，以此类推；这种就是堆积；    

也不是说堆积不好，但相同的哈希key（h(key)）在一起，总感觉不太好

线性探测的插入
		//线性探测
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			//我们哈希表负载因⼦控制在0.7
			//if (_n * 10 / _tables.size() > 7)
			//{
			//	//.....
			//	//重复线性探测的过程
			//	vector<HashData<K, V>> newtable(_tables.size() * 2);
			//	size_t hhash0 = kv.first % newtable.size();
			//	size_t hhashi = hhash0;
			//	//为什么没有显示
			//	while (newtable[hhashi]._state == EMPTY)
			//	{
			//		//线性探测;
			//		hhashi++;
			//		hhashi = hhashi % newtable.size();
			//	}

			//	newtable[hhashi]._state = EXIST;
			//	newtable[hhashi]._kv = kv;
			//	++_n;

			//	_tables.swap(newtable);
			//}


			if (_n * 10 / _tables.size() >= 7)
			{
				
				//自我实现扩大的是两倍
				//HashTable<K, V> newt;
				//newt._tables.resize(_tables.size() * 2);

				//c++实现
				HashTable<K, V, Hash> newt;
				//lower_bound(first, last, n);  +1 正好能找到比他大的
				newt._tables.resize(__stl_next_prime(_tables.size() + 1));   //素数表

				for (auto e : _tables)
				{
					if (e._state == EXIST)
					{
						newt.Insert(e._kv);
					}
				}

				_tables.swap(newt._tables);
			}


			//线性探测
			//不是 capacity    size才是哈希表的容积
			Hash hash;
			size_t hsah0 = hash(kv.first) % _tables.size();
			size_t hashi = hsah0;


			//为什么没有显示
			while (_tables[hashi]._state != EMPTY)
			{
				//线性探测;
				hashi++;
				hashi = hashi % _tables.size();
			}

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

			return true;
		}

二次探测 

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

如下图：

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

hc(key, i) = hashi = (hash0 ± i2) % M， i = {1, 2, 3, ..., }

  • 二次探测当 hashi = (hash0 - i2)%M 时，当hashi<0时，需要hashi += M

下面演⽰ {19,30,52,63,11,22} 等这一组值映射到M=11的表中。
 

二次探测的插入
//二次探测
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n * 10 / _tables.size() >= 7)
			{
				//自我实现扩大的是两倍
				//HashTable<K, V> newt;
				//newt._tables.resize(_tables.size() * 2);

				//c++实现
				HashTable<K, V> newt;
				//lower_bound(first, last, n);  +1 正好能找到比他大的
				newt._tables.resize(__stl_next_prime(_tables.size() + 1));
				for (auto e : _tables)
				{
					if (e._state == EXIST)
					{
						newt.Insert(e._kv);
					}
				}
				_tables.swap(newt._tables);
			}

			//不是 capacity    size才是哈希表的容积
			size_t hsah0 = kv.first % _tables.size();
			size_t hashi = hsah0;
			size_t i = 1;
			int flag = 1;
			//为什么没有显示
			while (_tables[hashi]._state != EMPTY)
			{
				//二次探测

				hashi = (hashi + i * i * flag) % _tables.size();

				if (flag > 0)
				{
					flag = -1;
				}
				else if(flag < 0)
				{
					flag = 1;
					i++;
				}
				//当然 既然插入的方法变了， 那么查找的方法也肯定有变化，但在这里就不演示了
			}

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

			return true;
		}

 双重散列

  • 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止
  • h1(key) = hash0 = key % M, hash0位置冲突了，则双重探测公式为：hc(key, i) = hashi = (hash0 + i ∗ h2(key)) % M， i = {1, 2, 3, ..., M}
  • 要求 h2(key) < M 且 h2(key) 和M互为质数，

有两种简单的取值方法：

  1. 当M为2整数冥时， 从[0，M-1]任选⼀个奇数；（其中要保证 每个key对应的  h2(key)是一致的）
  2. 当M为质数时， h2(key) = key % (M - 1) + 1
  • 保证 与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最大公约数p = gcd(M, h1(key)) > 1，那么所能寻址的位置的个数为  M / P < M，使得对于⼀个关键字来说无法充分利⽤整个散列表。（简单来说就是充分利用整个散列表，尽量在减少堆积的同时也减少散列表的空位置）

举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为   12/ gcd(12, 3) = 4。（这个是反例）

（为什么要保证是互质总的来说就是，散列表的位置很多都用不到。还有就是这个公式可以最大的程度利用，其中具体情况 可以自行搜索了解其数学解法哦）

下面演示 {19,30,52} 等这⼀组值映射到M=11的表中，设 h2(key) = key%10 + 1
 

二次探测
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n * 10 / _tables.size() >= 7)
			{
				//自我实现扩大的是两倍
				//HashTable<K, V> newt;
				//newt._tables.resize(_tables.size() * 2);

				//c++实现
				HashTable<K, V> newt;
				//lower_bound(first, last, n);  +1 正好能找到比他大的
				newt._tables.resize(__stl_next_prime(_tables.size() + 1));
				for (auto e : _tables)
				{
					if (e._state == EXIST)
					{
						newt.Insert(e._kv);
					}
				}
				_tables.swap(newt._tables);
			}

			//不是 capacity    size才是哈希表的容积
			size_t hsah0 = kv.first % _tables.size();
			size_t hashi = hsah0;
			size_t i = 1;
			int flag = 1;
			//为什么没有显示
			while (_tables[hashi]._state != EMPTY)
			{
				//二次探测

				hashi = (hashi + i * i * flag) % _tables.size();

				if (flag > 0)
				{
					flag = -1;
				}
				else if(flag < 0)
				{
					flag = 1;
					i++;
				}
				//当然 既然插入的方法变了， 那么查找的方法也肯定有变化，但在这里就不演示了
			}

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

			return true;
		}

链地址法

解决冲突的思路:

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

下面演示 {19,30,5,36,13,20,21,12,24,96} 等这一组值映射到M=11的表中。

  • 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。

  • 负载因子越大，哈希冲突的概率越高，空间利用率越高；
  • 负载因子越小，哈希冲突的概率越低，空间利用率越低；

这里就在 负载因子 == 1 时扩容；

stl中unordered_xxx的最大负载因⼦基本控制在1，大于1就扩容，之后手动实现unordered_xxx也使用这个方式。

  • 如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对了。但是假设不是被针对了，用了全域散列法，但是偶然情况下，某个桶很长，查找效率很低怎么办？

在Java8的HashMap中当桶的长度超过⼀定阀值(8)时就把链表转换成红黑树。这是一个解决极端场景的思路，大家可以了解一下。
其实一般也不会很长，毕竟会扩容；扩容的时候哈希表的数据会重新，经过哈希函数分到不同位置；
 

链地址法代码实现

namespace hash_bucket {

	template<class K, class V>
	struct HashData
	{

	public:
		pair<K, V> _kv;
		HashData* next;


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

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

	//如果不想每次实现都自己传，可以利用全特化，将其设置为默认模板
	//以string 为例子

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t num = 0;
			for (auto ch : s)
			{
				num += ch;
				//为什么要乘 131 
				//这涉及到BKDR-哈希表算法
				//这可以最大程度避免冲突的情况，具体如何实现可以上网搜索
				num *= 131;

			}
			return num;
		}

	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		typedef HashData<K, V> Node;
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			// Note: assumes long is at least 32 bits.
			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
			};
			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;
		}

		HashTable()
			//:_tables(__stl_next_prime(0))
			:_tables(11)
			,_n(0)
		{}

		bool Insert(const pair<K, V>& kv)
		{
			
			// 负载因子 == 1时扩容
			// 
			// 这种没必要，有多少节点还有删多少节点，复制多少节点；效率很低；
			// 而且vector的默认析构函数还不能将 节点上的全部节点都删掉；还有自己实现
			//if (_n == _tables.size())
			//{
			//	HashTable newtb;
			//	newtb._tables.resize(__stl_next_prime(_tables.size() + 1));

			//	for (size_t i = 0; i < _tables.size(); i++)
			//	{
			//		Node* cur = _tables[i];
			//		while (cur)
			//		{
			//			newtb.Insert(cur->_kv);
			//			cur = cur->next;
			//		}
			//	}
			//	_tables.swap(newtb._tables);
			//}


			//负载因子 == 1时扩容
			if (_n == _tables.size())
			{
				vector<Node*> newtb;
				newtb.resize(__stl_next_prime(_tables.size() + 1));
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Hash hhash;
						Node* next = cur->next;
						size_t hhash0 = hhash(cur->_kv.first) % newtb.size();
						//头插
						cur->next = newtb[hhash0];
						newtb[hhash0] = cur;

						cur = next;
					}
				}
				_tables.swap(newtb);
			}
			
			Hash hash;
			size_t hash0 = hash(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 hash;
			size_t hash0 = hash(key) % _tables.size();

			Node* cur = _tables[hash0];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->next;
				}
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hash0];

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hash0] = cur->next;
					}
					else
					{
						prev->next = cur->next;
					}
					delete cur;
					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->next;
				}

			}
			return false;
		}
	private:
		vector<Node*> _tables; // 指针数组
		size_t _n = 0;		    // 表中存储数据个数
	};
}


http://www.kler.cn/a/378065.html

相关文章：

  • VSCode 1.82之后的vscode server离线安装
  • git rebase 使用 - 【nolankywu】
  • Jetson Orin NX平台自研载板 IMX477相机掉线问题调试记录
  • 【力扣专题栏】面试题 01.02. 判定是否互为字符重排，如何利用数组模拟哈希表解决两字符串互排问题？
  • java访问华为网管软件iMaster NCE的北向接口
  • 【Clikhouse 探秘】ClickHouse 物化视图：加速大数据分析的新利器
  • Python小游戏20——超级玛丽
  • 微信小程序 - 获取汉字拼音首字母（汉字英文首字母）根据汉字查拼音，实现汉字拼音首字母获取，在小程序上实现汉字的拼音提取首字母！
  • 什么是贪心算法
  • Apache POI—读写Office格式文件
  • HarmonyOS ArkTS Web组件jsbridge
  • Hadoop-002-部署并配置HDFS集群
  • Codeforces Round 981 (Div. 3) （A~F）
  • Java入门10——封装（private）
  • 【Linux】--- 开发工具篇：yum、vim、gcc、g++、gdb、make、makefile
  • 萤石私有化设备视频平台EasyCVR视频融合平台如何构建农业综合监控监管系统？
  • 面试题整理 4
  • 阿里云docker安装禅道记录
  • TCP三次握手，四次挥手，以及11种状态详解
  • Oracle 第17章：数据字典与视图
  • python的数据结构列表方法及扩展（栈和队列）
  • InstructIR: High-Quality Image Restoration Following Human Instructions 论文阅读笔记
  • IDEA 好用的插件分享
  • Blender进阶：贴图与UV
  • 【C++篇】跨越有限与无限的边界：STL之set容器中的自我秩序与无限可能
  • 【踩坑】修复高版本dgl中distributed.load_partition不返回orig_id问题