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

了解哈希并用线性探测和链地址法解决哈希冲突

article 2024/12/2 8:56:35

目录

1.哈希概念

2.哈希冲突

3.哈希冲突解决

3.1闭散列

3.2开散列

1.哈希概念

顺序结构以及平衡树中，元素在存储结构中的位置与元素的关键码之间不存在直接的对应关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法是：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果在元素的存储位置与它的关键码之间建立一个确定的对应函数关系 Hash()，使得每个关键码与结构中的一个唯一的存储位置相对应：Address== Hash(key)

  • 在插人时，根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
  • 搜索元素，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置

这种方法就是哈希（散列）方法（Hash method）。在哈希方法中使用的转换函数叫做哈希（散列）函数（Hash function）。而按此种想法构造出来的表或结构就叫做哈希表（Hash Table）（或称散列表）。

搜索元素就不必进行关键码的比较，直接调用哈希函数求出存储位置进行获取就行，因此搜索的速度比较快

2.哈希冲突

对于上面的例子，当有个新元素26要插入进哈希表中，hash(26) = 26 % 10 = 6,由于6下标位置已经存储了元素56，所以就发生了冲突。不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

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

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

常见哈希函数：

1. 直接定址法(常用)
取关键字的某个线性函数为散列地址：Hash（Key）=A*Key +B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

2.除留余数法(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key)= key% p(p<=m),将关键码转换成哈希地址

3.平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址;
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

3.哈希冲突解决

3.1闭散列

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

当有个新元素26要插入进哈希表中，hash(26) = 26 % 10 = 6,由于6下标位置已经存储了元素56，因此往后找空位（hash值不断加1），正好7下标为空，就将26存入。如果插入的新元素为19，hash(19) = 9,由于9下标已经存了99且9下标为哈希表的最后一个位置，所以往后找空位就要返回哈希表的开始，0下标为空将19存入。

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入：通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

删除：采用闭散列处理哈希冲突时，不能随便删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素99，如果直接删除，接下来要查找19，hash(19) = 19 % 10 = 9;发现9下标元素为空，就会觉得不存在元素19。因此线性探测采用标记的伪删除法来删除一个元素。

哈希表在什么情况下扩容？

平衡因子 = 表中元素个数 / 哈希表的长度

平衡因子越大，表明填入表中的元素越多，产生冲突的可能性就越大；

反之，平衡因子越小，表明填入表中的元素越少，产生冲突的可能性就越小

对于开放地址法，平衡因子应控制在0.7~0.8，

线性探测的实现：

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

// 特化，当key为string类型时
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

namespace open_address
{

    // 哈希表每个位置标记
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

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

	

	template<class K, class V>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10); // 初始容量设为10
		}


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

			// 判断扩容，平衡因子只要超过了0.7就扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				HashTable<K, V, Hash> ht;
				ht._tables.resize(_tables.size() * 2);
				for (int i = 0; i < _tables.size(); i++)
				{
					ht.Insert(_tables[i]._kv); // 让Insert帮我们做，就不用再写下面的插入逻辑
				}
				_tables.swap(ht._tables); // 最后交换
			}

			// 插入数据
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size(); // 为了防止hashi超过哈希表的下标
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				++hashi;
				hashi %= _tables.size();
			}

			return nullptr;
		}

		bool Delete(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}

			ret->_state = DELETE;
			return true;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n; // 插入元素个数
	};


}

线性探测优点：实现非常简单
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据"堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

3.2开散列

开散列法又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中 。
对于链地址法的扩容，当平衡因子为1时进行扩容 
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

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

namespace Hash_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:
		HashTable()
		{
			_tables.resize(10, nullptr);
		}
		~HashTable() // 析构存储的结点
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
			}
		}

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

			// 平衡因子==1扩容
			if (_n == _tables.size())
			{
				// 把原节点挪到新表上
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hs(cur->_kv.first) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

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


				_tables.swap(newTables);
			}
            
            // 插入新结点
			size_t hashi = hs(kv.first) % _tables.size();
			
			Node* newNode = new Node(kv);
			newNode->_next = _tables[hashi];
			_tables[hashi] = newNode;
			++_n;
			
			return true;
		}

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

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

	private:
		vector<Node*> _tables;
		size_t _n; // 存储元素个数
	};


}


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

相关文章：

  • Graphy 是一款终极、易于使用、功能齐全的 FPS 计数器、统计监视器和调试器，适用于您的 Unity 项目。
  • 基于yolov4深度学习网络的排队人数统计系统matlab仿真,带GUI界面
  • pytorch中一个tensor经过多次softmax会有什么变化？
  • Git命令大全（超详细）
  • 【实验13】使用预训练ResNet18进行CIFAR10分类
  • AI开发-数据可视化库-Seaborn
  • Asio2网络库
  • 微信小程序首页实现轮廓图及动态渲染的高级教程
  • USBasp给arduino nano烧写bootloader
  • 使用lumerical脚本语言创建定向耦合器并进行数据分析（纯代码实现）
  • 【c++篇】：探索哈希表--数据结构中的独特存在，打开数据组织与查找的新视界
  • 深入解析 Kubernetes 节点操作：Cordon、Uncordon 和 Drain 的使用与最佳实践
  • Leecode刷题C语言之N皇后
  • 若依框架保姆级入门使用
  • IREE AI编译器关键模块分析
  • TypeScript核心语法（3）——类型系统
  • vue3中是如何实现双向数据绑定的
  • 实测数据处理（BP算法处理）——SAR成像算法系列（十）
  • Rsa加解密 + 签名验签
  • 鸿蒙面试 --- 性能优化
  • 【梦幻工厂的探索】亚马逊——基础设施的打造者
  • 游戏引擎学习第29天
  • 文件包含（精讲）
  • 【论文复现】StreamPETR
  • 数据分析自动化工具对比指南Cursor Composer和Google Data Science Agent
  • 第八课 Unity编辑器创建的资源优化_特效篇（Particle System）详解