首页 > 编程语言 >【C++进阶学习】第九弹——哈希的原理与实现——开放寻址法的讲解

【C++进阶学习】第九弹——哈希的原理与实现——开放寻址法的讲解

时间:2024-07-28 11:25:44浏览次数:16  
标签:key tables 进阶 hashi C++ 哈希 ._ size

前言:

在前面,我们已经学习了很多存储机构,包括线性存储、树性存储等,并学习了多种拓展结构,效率也越来越高,但是是否有一种存储结构可以在大部分问题中都一次找到目标值呢?哈希可能能实现

目录

一、哈希的概念

二、哈希冲突

三、哈希冲突解决

3.1 开放寻址法

节点结构

插入操作

查找操作

删除操作

打印操作

3.2 链地址法

四、测试代码(开放寻址法)

五、总结


一、哈希的概念

哈希就是一种特殊的存储结构,通过特定的函数,使得数据的存储位置与它的关键码之间建立一种一一映射的关系,这样在查找数据时就可以直接通过关键值来快速查找

通过这种方法:

当我们向其中插入数据时,就可以利用此特定函数插入到关键码对应的位置下

当我们搜索数据时,通过关键码,进行相应的处理就可以找到要找的数据

这种方法就叫做哈希,特定的函数就是哈希函数,这种方法所建立的结构就叫做哈希函表

我们来看这样一个例子:

对于这样一个数组{1,5,3,17,19,0},按照上述规则我们首先要先找一个合适的哈希函数,

这里我们哈希函数可以设为:hashi(key)=key%capacity;capacity为存储空间底层空间总的大小

现在我们根据上面这个例子来思考这样一个问题,如果有这样一个数据,比如13,通过上面的哈希函数计算得我们应该把它放在关键码为3的位置上,但是此时这个位置上已经有数据了,我们应该如何解决呢?这样的问题就叫做哈希冲突

二、哈希冲突

哈希冲突指的是在使用哈希表进行数据存储和查找时,不同的关键字通过哈希函数计算得到了相同的哈希值。

哈希函数是将关键字映射到哈希表中的某个位置的函数。由于哈希表的存储空间是有限的,而可能的关键字数量是无限的,所以不同的关键字有可能被映射到相同的位置,这就产生了哈希冲突。

哈希冲突会影响哈希表的性能,比如增加查找、插入和删除操作的时间复杂度。

常见的解决哈希冲突的方法有(这两种方法会在后面详细讲解):

  1. 开放寻址法:当发生冲突时,通过一定的探查方式在哈希表中寻找其他空闲的位置来存储冲突的元素。
  2. 链地址法:在哈希表的每个位置上建立一个链表,将所有哈希值相同的元素都存储在这个链表中。

三、哈希冲突解决

解决哈希冲突常见的两种方法主要是:开放寻址法和链地址法

3.1 开放寻址法

开放定址法是解决哈希冲突的一种方法,其基本思想是当发生冲突时,通过某种系统的方法在哈希表中寻找下一个空槽位,并将冲突的关键码存储在这个槽位中。下面我们先来看一下开放寻址法的重点:

  1. 探测序列:开放定址法中,探测序列决定了当发生冲突时如何查找下一个槽位。常见的探测序列方法有:

    • 线性探测:当冲突发生时,顺序检查表中的下一个槽位,直到找到空槽位。
    • 二次探测:探测序列为 1, 4, 9, 16, ...,即探测位置是 i^2 的倍数,其中 i 是从0开始的整数。
    • 伪随机探测:使用伪随机数生成器来确定探测序列。
  2. 删除操作:在开放定址法中,删除元素比较复杂,因为不能简单地将槽位置为空,否则会影响后续的查找操作。通常,删除一个元素时,将其标记为已删除,但在查找时跳过已删除的元素。

  3. 装填因子:装填因子是哈希表中已存储元素个数与哈希表大小的比值。开放定址法中,装填因子不宜过高,否则冲突概率增加,查找效率下降。(因为这个原因,所以需要扩容)

节点结构

因为我们并不知道插入要操作何种类型的数据,可能是整形,浮点型或string的,所以我们可以选择将它们全转化为整形来处理,这里就需要我们借助仿函数和模板特化来实现

	template<class K>       
struct HashFunc         //仿函数,这里的功能是将其他类型转化为整形
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template<>     //特化
struct HashFunc<string>    //string类的不可以直接转化为整形,所以需要特殊处理
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

enum Status
	{
		EMPTY,     //此位置为空
		EXIST,     //此位置不为空
		DELETE     //此位置数据已被删除
	};
	template<class K, class V>     //因为不能确定我们要处理什么类型的数据,所以我们采用类模板的形式
	struct HashData
	{
		pair<K, V> _kv;   
		Status _s;        //此位置的状态
	};
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()     //初始化HashTable
		{
			_tables.resize(10);
		}

		
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;        //存储个数
	};

插入操作

开放寻址法的关键就在于数据的插入,在这里我们重点讲解一下线性探测的思想

这就是线性探测的思路,同时我们还要在装填因子足够大的时候进行扩容,比如上面这个例子,此时10个位置中已经填入7个因子,我们就可以进行按2倍扩容:

代码实现如下:

		//插入
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//负载因子0.7就扩容
			if (_n * 10 / _tables.size() == 7)
			{
				size_t newSize = _tables.size() * 2;
				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);    //直接交换就可以得到扩容后的结果
			}

			Hash hf;
			//线性探测
			size_t hashi = hf(kv.first) % _tables.size();  //这里涉及到模板的特化,后面会讲
			while (_tables[hashi]._s == EXIST)    //当此位置不为空时,就往后找
			{                                     //当为空或已删除时都是可以放入数据的
				hashi++;
				hashi %= _tables.size();        //这里进行这个操作的目的是防止hashi大于_tables.size()
			}
			_tables[hashi]._kv = kv;     //找到后将这个位置值改为插入值
			_tables[hashi]._s = EXIST;   //状态改为存在
			_n++;

			return true;
		}

查找操作

上面的插入操作中,我们首先就先用查找操作看是否已经有这个数据,因为哈希是不允许存在重复数据的,这里我们就来看一下这个查找操作

		//查找
		HashData<K, V>* Find(const K& key)
		{
			Hash hf;      //仿函数
			size_t hashi = hf(key) % _tables.size();   //所有计算都要用仿函数将key转换为整形
			while (_tables[hashi]._s == EXIST)      //从不为空的位置开始找
			{
				if (_tables[hashi]._s != EMPTY
					&& _tables[hashi]._kv.first == key)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return NULL;
		}

删除操作

我们删除一个数据时,并不能简单的找到这个数据就进行删除,这样会对我们后序很多操作带来不少麻烦,比如我们把4删除了,再找44就会很不容易,这也就是我们前面在定义节点结构是要定义状态的原因,我们删除一个操作后可以把它的状态更改,这样我们在进行其他操作的时候就可以直到这个位置上的值已被删除

		//删除
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				_n--;
				return 0;
			}
			else
				return true;
		}

打印操作

		//打印
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)     //当这个位置有数据时,打印出有效数据
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":"
					<< _tables[i]._kv.second << endl;
				else if (_tables[i]._s == EMPTY)
					printf("[%d]->EMPTY\n", i);
				else
					printf("[%d]->DELETE\n", i);
			}
		}

3.2 链地址法

链地址法有些东西与上面的代码有些冲突,不好测试,我们放在下一篇讲

四、测试代码(开放寻址法)

我们给出几个测试用例检验一下上面的开放寻址法是否有误:

测试一:

		void TestHT1()
	{
		HashTable<int, int> j;
		int a[] = { 4,14,24,34,5,7,1 };
		for (auto e : a)
		{
			j.Insert(make_pair(e, e));
		}
		j.Insert(make_pair(3, 3));
		j.Print();


		j.Insert(make_pair(3, 3));     //这里有一个隐藏的bug
		if (j.Find(3))
			cout << "3存在" << endl;
	}

运行结果:

测试二:

	void TestHT2()    //测试string
	{
		string arr[] = { "香蕉","甜瓜","苹果","香蕉","苹果","苹果" };
		HashTable<string, int> ht;
		for (auto e : arr)
		{
			auto ret = ht.Find(e);
			if (ret)
				ret->_kv.second++;
			else
			{
				ht.Insert(make_pair(e, 1));
			}
		}
		ht.Print();
	}

运行结果:

五、总结

以上就是用开放寻址法来创建一个哈希表的完整代码,由于排版原因,整体看起来可能有些乱,有不懂的地方欢迎与我私信交流!!

标签:key,tables,进阶,hashi,C++,哈希,._,size
From: https://blog.csdn.net/2301_80220607/article/details/140693632

相关文章

  • Codeforces Round 962 (Div. 3) A - D详细题解(思路加代码Python,C++(垃圾灰名小白想
             吐槽一下,这次比赛不知道怎么的,可能是div3参加的人比较多吗,代码题解上去后全是inqueue,比赛的过程中我还看了提交的,80多页几千个提交全是inqueue,我的代码等了**半个多小时才运行,然后发现timelimit真的有点搞心态,思路在下一题我还要反过来去优化上一题,不过......
  • Visual Studio C++ 安装以及使用教程
    官网下载网址https://visualstudio.microsoft.com/zh-hans/VisualStudio:面向软件开发人员和Teams的IDE和代码编辑器(microsoft.com)下载好后双击运行跳出该界面,等待加载结束在组件选择界面,只需要选择这一项,勾选好后点击安装即可下载完后,点击图标打开C++点击创......
  • 【免费领源码】Java/Mysql数据库+SSM校园兼职网站 25557,计算机毕业设计项目推荐上万套
    摘 要当今人类社会已经进入信息全球化和全球信息化、网络化的高速发展阶段。丰富的网络信息已经成为人们工作、生活、学习中不可缺少的一部分。人们正在逐步适应和习惯于网上贸易、网上购物、网上支付、网上服务和网上娱乐等活动,人类的许多社会活动正在向网络化发展。兼职......
  • 【免费领源码】Java/Mysql数据库+springboot驾校预约管理系统 25540,计算机毕业设计项
    摘 要随着科学技术的飞速发展,各行各业都在努力与现代先进技术接轨,通过科技手段提高自身的优势;对于驾校预约管理系统当然也不能排除在外,随着网络技术的不断成熟,带动了驾校预约管理系统,它彻底改变了过去传统的管理方式,不仅使服务管理难度变低了,还提升了管理的灵活性。这种......
  • C++字体库开发之go语言绑定六
    export.h#defineFONTVIEW_API__declspec(dllimport)typedefvoid*GoFontSetPtr;#ifdef__cplusplusextern"C"{#endifFONTVIEW_APIGoFontSetPtropenFontSet(constchar*stream,size_tsize);FONTVIEW_APIvoidfreeFontSet(GoFontSetPtrfontset);......
  • 三种语言实现二分(C++/Python/Java)
    题目给定一个按照升序排列的长度为......
  • C++模板——泛型编程
    目录1.什么是泛型编程2.函数模板2.1定义格式2.2实例化及原理 2.3参数匹配原则3.类模板 3.1定义格式3.2实例化 4.非类型模板参数 5.模板的特化 5.1概念5.2函数模板和类模板特化6.模板的分离编译 1.什么是泛型编程 如何实现一个通用的加......
  • C++基础(1)
    1.命名空间1.1namespace的价值在C/C++中,变量、函数和后⾯要学到的类都是⼤量存在的,这些变量、函数和类的名称将都存在于全局作⽤域中,可能会导致很多冲突。使⽤命名空间的⽬的是对标识符的名称进⾏本地化,以避免命名冲突或名字污染,namespace关键字的出现就是针对这种问题的......
  • 秒懂C++之string类(上)
    目录 一.string类的常用接口说明二.不太常用接口(了解接口)三.string类的遍历访问3.1迭代器iterator3.2反向迭代器四.string的其他功能4.1reserve(扩容)4.2resize4.3at4.4append4.5+=4.6insert一.string类的常用接口说明#include<string>#include......
  • 哈希表
    拉链法#include<iostream>usingnamespacestd;constintN=100003;//N设为1个质数inth[N];inte[N],ne[N],idx;//y总的找质数voidf(){ for(inti=100000;;i++) { boolflag=true; for(intj=2;j*j<=i;j++) if(i%j==0) { ......