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

C++之闭散列哈希表

article 2025/1/9 18:42:55

目录

unordered_set和unordered_map 

哈希概念

哈希表基本结构 

哈希冲突

线性探测​编辑

 二次探测

前几期我们学习了红黑树和红黑树的模拟实现，最终使用红黑树封装了map和set。本期开始我们将学习下一个重要的知识点---哈希表，最终使用哈希表封装unordered_map和unordered_set。

unordered_set和unordered_map 

在学习哈希之前，我们先了解一下unordered_set和unordered_map,这两个容器也都是关联式容器，我们之前已经学习了map和set。unordered_set和unordered_map与set和map大体上是一样的，但是也有几点不同。

1.map和set的底层是用红黑树进行封装实现的，也正因为如此，红黑树是一个搜索二叉树，搜索二叉树的元素我们是按照中序遍历的方法进行遍历的。所以map和set的元素的遍历是有序的，而unordered_set和undered_map的元素的遍历是无序的。

2.map和set是双向迭代器，而unordered_set和unordered_map是单项迭代器，通过C++官方文档就可以看出来。

3.map和set查找一个元素时，因为底层是红黑树，所以最多查找高度次，所以查找一个元素的时间复杂度为O(logN)，而unordered_set和unordered_map底层是哈希，所以查找一个元素的时间复杂度为O(1),为什么是O(1),下面会为大家阐述。

哈希概念

有N个数的集合，这N个数的范围为[1,26],N个数中有重复的数，现在要统计这N个数中，每个数出现的次数，我们该如何进行统计呢？

 有一种方法，就是开辟一个大小为27的一维数组，让这N个数的每个数都%27,然后将取模之后得到的数作为数组的下标，对应数组元素的值为这一数字出现的次数，通过这一方法就可以统计得到N个数每个元素出现的次数。这其实就是哈希的一种体现。

哈希表：通过哈希函数，使得关键码和元素位置建立一一映射的表，我们称之为哈希表。

哈希表基本结构 

namespace CloseHash
{
	enum Status
	{
		EMPTY,
		DELETE,
		EXIST
	};
	template<class K, class V>
	struct HashData
	{

	private:
		pair<K, V> _kv;
		Status  _st = EMPTY;
	};


	template<class K,class V>
	class HashTable
	{
	private:
		vector<HashData<K, V>> _v;
		int _n;  //哈希表中有效元素的个数
	};

}

哈希冲突

何为哈希冲突呢？前提为我们要用一个一维数组存储数据。

有1组数为1,7,2,8，映射在大小为7的数组中，1映射到下标为1的位置，7也映射到1的位置，但是数组的一个元素中只能存储一个数据，那么1先存入之后，7要存入时这就产生了冲突，我们就称这为哈希冲突。

简单来说，哈希冲突就是不想同的元素，通过哈希映射，映射到了哈希表的同一位置。 

如何解决哈希冲突呢？我们使用了闭散列的方法，即为线性探测和二次探测法。什么是线性探测？什么又是二次探测法呢？

线性探测

线性探测就是，当第二个元素与第一个元素产生哈希冲突时，从产生冲突的位置开始，依次往后继续寻找空的位置，寻找到空的位置之后，将产生冲突的元素放在空的位置。代码实现如下。

代码如下。

	//哈希表中元素的插入
		bool insert( const pair<K,V>& kv)
		{
			//先去判断哈希表中是否存在当前要插入的元素，因为哈希表的原理是不排序加去重
			HashData<K, V>* ret = find(kv.first);
			if (ret != nullptr)
			{
				return false;
			}
			if (_v.size() == 0 || _n*10 / _v.size() > 7)
			{
				int NewSize = _v.size() == 0 ? 10 : _v.size() * 2;
				HashTable<K, V> ht;
				ht._v.resize(NewSize);
				for (int i = 0; i< _v.size(); i++)
				{
					if (_v[i]._st == EXIST)
					{
						ht.insert(_v[i]._kv);
					}
				}
				_v.swap(ht._v);

			}
			HashFunc<K> hf;
			int  start = hf(kv.first) % _v.size();
			int i = 0;
			size_t index = start;
			while (_v[start]._st == EXIST)
			{
				++i;
				start = index + i;
				start% _v.size();
			}

			_v[start]._kv = kv;
			_v[start]._st = EXIST;
			++_n;
			return true;

		}

大家来想一个问题？当哈希表中的元素越来越多时，产生哈希冲突的概率必然也是越来越大的，怎么样去避免这类现象出现呢？

唯一的办法就是不断的去扩容，所以我们引入了平衡因子的概念，就是哈希表中的有效元素个数除以哈希表的容量，注意，这里的容量是size()，即vector中申请并初始化之后的元素的数目。 

二次探测

何为二次探测，并不是探测两次，而是2次方。图示如下。

二次探测和线性探测类似。线性探测有一个缺点，就是当相同位置的元素过多时，就会侵占当前位置附近的其他位置，这就导致，本来处在附近位置的元素又去侵占其它元素的位置，这样会降低整个哈希表的查找效率，所以我们引入了二次探测，即插入的元素引起哈希冲突时，并不会在后续的第一个空位置插入冲突的元素，而是会去寻找当前位置+i*i的位置，如果当前位置为空，则插入元素。

代码如下。

bool insert( const pair<K,V>& kv)
		{
			//先去判断哈希表中是否存在当前要插入的元素，因为哈希表的原理是不排序加去重
			HashData<K, V>* ret = find(kv.first);
			if (ret != nullptr)
			{
				return false;
			}
			if (_v.size() == 0 || _n*10 / _v.size() > 7)
			{
				int NewSize = _v.size() == 0 ? 10 : _v.size() * 2;
				HashTable<K, V> ht;
				ht._v.resize(NewSize);
				for (int i = 0; i< _v.size(); i++)
				{
					if (_v[i]._st == EXIST)
					{
						ht.insert(_v[i]._kv);
					}
				}
				_v.swap(ht._v);

			}
			HashFunc<K> hf;
			int  start = hf(kv.first) % _v.size();
			int i = 0;
			size_t index = start;
			while (_v[start]._st == EXIST)
			{
				++i;
				//start = index + i;
				start = index + i * i;
				start% _v.size();
			}

			_v[start]._kv = kv;
			_v[start]._st = EXIST;
			++_n;
			return true;

		}

闭散列哈希表整体代码如下。

#pragma once
#include<iostream>
#include<vector>
#include <string>
using namespace std;

namespace CloseHash
{
	enum Status
	{
		EMPTY,
		DELETE,
		EXIST
	};

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

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

			return value;
		}

	};
	template<class K, class V>
	struct HashData
	{


		pair<K, V> _kv;
		Status  _st = EMPTY;
	};


	template<class K,class V,class hashFunc=HashFunc<K>>
	class HashTable
	{
	public:
		bool  erase(const K& key)
		{
			HashData<K, V>* ret = find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_st = DELETE;
				_n--;
				return true;
			}
		}

		HashData<K,V>* find(const K& key)
		{
			if (_v.size() == 0)
			{
				return nullptr;
			}
			HashFunc<K> hf;
			size_t start = hf(key) % _v.size();
			int i = 0;
			size_t index = start;
			
			while (_v[start]._st != EMPTY)
			{
				if (_v[start]._kv.first == key && _v[start]._st == EXIST)
				{
					return &_v[start];
				}
				++i;
				start = index + i;
			}
			return nullptr;
		}

	

		//哈希表中元素的插入
		bool insert( const pair<K,V>& kv)
		{
			//先去判断哈希表中是否存在当前要插入的元素，因为哈希表的原理是不排序加去重
			HashData<K, V>* ret = find(kv.first);
			if (ret != nullptr)
			{
				return false;
			}
			if (_v.size() == 0 || _n*10 / _v.size() > 7)
			{
				int NewSize = _v.size() == 0 ? 10 : _v.size() * 2;
				HashTable<K, V> ht;
				ht._v.resize(NewSize);
				for (int i = 0; i< _v.size(); i++)
				{
					if (_v[i]._st == EXIST)
					{
						ht.insert(_v[i]._kv);
					}
				}
				_v.swap(ht._v);

			}
			HashFunc<K> hf;
			int  start = hf(kv.first) % _v.size();
			int i = 0;
			size_t index = start;
			while (_v[start]._st == EXIST)
			{
				++i;
				//start = index + i;
				start = index + i * i;
				start% _v.size();
			}

			_v[start]._kv = kv;
			_v[start]._st = EXIST;
			++_n;
			return true;

		}



	private:
		vector<HashData<K,V>> _v;
		int _n;  //哈希表中有效元素的个数
	};


	void  HashTest()
	{
		HashTable<int, int> ht;
		ht.insert(make_pair(1, 1));
		ht.insert(make_pair(2, 1));
		ht.insert(make_pair(3, 1));
		ht.insert(make_pair(4, 1));

		cout << ht.find(1) << endl;
		cout << ht.find(5) << endl;

	}



}

 调试代码，发现运行结果符合预期。

 以上便是哈希表中闭散列哈希表的所有内容，下期将为大家带来开散列哈希表的内容。

本期内容到此结束^_^

 


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

相关文章：

  • GitLab创建用户，设置访问SSH Key
  • OSPF - 2、3类LSA（Network-LSA、NetWork-Sunmmary-LSA）
  • selenium合集
  • 道品科技智慧农业与云平台：未来农业的变革之路
  • 用JAVA编写一个简单的小游戏
  • Flink系统知识讲解之：如何识别反压的源头
  • 使用 Python 的 pyttsx3 库进行文本转语音
  • 探索电商宝藏：用Java打造1688商品详情爬虫，挖掘商业价值
  • ChatGPT加速器：解锁高效智能对话的新工具
  • 怎么对PDF插入图片并设置可见程度-免费PDF编辑工具分享
  • fetch-pack: unexpected disconnect while reading sideband packet报错问题排查
  • 设置密码，保护隐私：Excel文件加密的几种方法
  • CH348结合开源ModBus协议组成串口温度采集服务器
  • K-means算法在无监督学习中的应用
  • 网络安全-XSS跨站脚本攻击（基础篇）
  • C++虚函数（八股总结）
  • 深入理解 JSON 数据传递方式：数组格式与对象包装格式的对比与选择
  • 力扣第141题：环形链表 C语言解法
  • CentOS: RPM安装、YUM安装、编译安装（详细解释+实例分析！！！）
  • ExcelDataReader：一个.Net高性能Excel开源读取器
  • 游戏引擎学习第76天
  • 将txt转成excel正则化公式的调整
  • 超完整Docker学习记录，Docker常用命令详解
  • 前后端实现防抖节流实现
  • HTB：Bank[WriteUP]
  • Java虚拟机（Java Virtual Machine，JVM）