哈希桶的模拟实现【C++】

文章目录

  • 哈希冲突解决
    • 闭散列 （开放定址法）
    • 开散列 （链地址法、哈希桶）
      • 开散列实现（哈希桶）
        • 哈希表的结构
        • Insert
        • Find
        • Erase

哈希冲突解决

闭散列 （开放定址法）

发生哈希冲突时，如果哈希表未被装满，说明在哈希表种必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的“下一个”空位置中去

如何寻找“下一个位置”
1、线性探测
发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止

Hi=(H0+i)%m ( i = 1 , 2 , 3 , . . . )

H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过线性探测后得到的存放位置
m：表的大小。

举例：
用除留余数法将序列{1,111,4,7,15,25,44,9}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：

使用除留余数法
1%10 =1 ,111 %10 =1
即111和1发生了哈希冲突 ，所以111找到1的下一个空位置插入
在这里插入图片描述

将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。
介于此，哈希表当中引入了负载因子（载荷因子）：

负载因子 = 表中有效数据个数 / 空间的大小
不难发现：
负载因子越大，产出冲突的概率越高，查找的效率越低
负载因子越小，产出冲突的概率越低，查找的效率越高

负载因子越小，也就意味着空间的利用率越低，此时大量的空间都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下
采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容

线性探测的缺点：一旦发生冲突，所有的冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要多次比较（踩踏效应），导致搜索效率降低
2、二次探测

二次探测为了避免该问题，找下一个空位置的方法为

Hi=(H0+i ^2 )%m ( i = 1 , 2 , 3 , . . . )

H0：通过哈希函数对元素的关键码进行计算得到的位置
Hi：冲突元素通过二次探测后得到的存放位置
m：表的大小

相比线性探测而言，二次探测i是平方，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积

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

template <>
struct DefaultHashFunc<string>
{
	size_t  operator() (const string& str)
	{
		//BKDR,将输入的字符串转换为哈希值
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

namespace open_address 
{
	enum  STATE
	{
		EXIST,
		EMPTY,
		DELETE
	};

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


	struct StringHashFunc
	{
		size_t operator()(const string& str)
		{
			return str[0];
		}
	};

	//template<class K, class V>
	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_table.resize(10);
		}
		bool insert(const pair<K, V> kv)
		{
			//扩容 
			if ((double)_n / (double)_table.size() >= 0.7)
			{
				HashTable<K, V>  newHT;
				size_t newSize = _table.size() * 2;
				newHT._table.resize(newSize);
				//遍历旧表的数据，将旧表的数据重新映射到新表中

				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
					{
						newHT.insert(_table[i]._kv);//插入的写成kv不行？
					}

				}
				_table.swap(newHT._table);
			}





			//线性探测

			HashFunc hf;

			size_t  hashi = hf(kv.first) % _table.size();

			//如果该位置没有元素，则直接插入元素 ，如果该位置有元素，找到下一个空位置，插入新元素
			while (_table[hashi]._state == EXIST)//不是EMPTY和DELETE这两种情况
			{
				++hashi;
				hashi %= _table.size();
			}
			//是EMPTY和DELETE这两种情况
			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashData<const K, V>* Find(const K& key)
		{
			HashFunc hf;
			//线性探测 
		//如果该位置没有元素，则直接插入元素 ，如果该位置有元素，找到下一个空位置，插入新元素
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY) //DELETE和EXIST
			{
				if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
				{
					return  (HashData<const K, V>*) & _table[hashi];
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			//先找到
			HashData<const K, V>* ret = Find(key);
			//再删除 
			if (ret != nullptr)
			{
				ret->_state = DELETE;
				_n--;
				return true;
			}
			//没找到 
			return false;
		}
	public:
		vector<HashData<K, V>> _table;
		size_t  _n = 0; //存储有效数据的个数

	};

}

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

开散列 （链地址法、哈希桶）

开散列，又叫哈希桶，首先对关键码集合用哈希函数计算哈希地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

举例：
用除留余数法将序列{1,111,4,7,15,25,44,9}插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的方式进行插入，插入过程如下：
在这里插入图片描述
将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点

闭散列的开放定址法，负载因子不能超过1，一般建议控制在[0.0, 0.7]

开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]

在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：
哈希桶的负载因子可以更大，空间利用率高
哈希桶在极端情况下还有可用的解决方案

开散列实现（哈希桶）

哈希表的结构
struct HashNode
	{
		pair<K, V>  _kv;
		HashNode<K,V>* _next;
		HashNode(  const pair<K, V> & kv)
			:_kv(kv)
			,_next(nullptr)
		{
			
		}
	};
Insert
	bool Insert(const pair<K,V> & kv)
		{
			
			size_t hashi = kv.first % _table.size();
			//负载因子到1就扩容 
			if (_n == _table.size())
			{
				size_t 	newsize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newsize, nullptr);

			
				//遍历旧表，将原哈希表当中的结点插入到新哈希表
				for (int i = 0; i <= _table.size(); i++)
				{
					Node* cur = _table[i];
					//插入到新哈希表
					while (cur != nullptr)
					{
						Node* next = cur->_next;
						// 重新分配hashi
						size_t hashi = cur->_kv.first % _table.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

				}
			}
	
			//头插 
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			return true;
		}

在这里插入图片描述

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

32.png)

		bool Erase(const K & key)
		{
			size_t hashi = key % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur != nullptr)
			{
				if (key == cur->_kv.first)
				{
					  if(prev==nullptr)//第二种情况 ,prev是nullptr ,就是头删
					  {
						_table[hashi] = cur->_next;
					  }
					  else//第一种情况 ,cur是头节点
					  {
						  prev->_next = cur->_next;
					  }
					  delete cur;
					return  true; 
				}
				prev = cur;
				cur = cur->_next;
			}
		

			//没找到 
			return false;
		}

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 HashTable
	{
	public:
		typedef HashNode<K,V>  Node;

		//iterator begin()
		//{

		//}
		//iterator end()
		//{

		//}
		//const_iterator begin()
		//{

		//}
		//const_iterator end()
		//{

		//}
		//GetNextPrime()
		//{

		//}
		HashTable()
		{
			_table.resize(10, nullptr);
		}
		~HashTable()
		{

		}
		//bool Insert(const pair<K, V>  kv)
		//{
		//	//负载因子到1就扩容 
		//	if (_n == _table.size())
		//	{
		//		size_t 	newsize = _table.size() * 2;
		//		vector<Node*> newtable;
		//		newtable.resize(newsize, nullptr);
		//	}
		//	size_t hashi = kv.first % _table.size();
		//	//头插 
		//	Node* newnode = new Node(key);
		//	newnode->_next = _table[hashi];
		//	_table[hashi] = newnode;
		//	++_n;
		//	return true;
		//}
		bool Insert(const pair<K,V> & kv)
		{
			
			size_t hashi = kv.first % _table.size();
			//负载因子到1就扩容 
			if (_n == _table.size())
			{
				size_t 	newsize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newsize, nullptr);

			
				//遍历旧表，将原哈希表当中的结点插入到新哈希表
				for (int i = 0; i <= _table.size(); i++)
				{
					Node* cur = _table[i];
					//插入到新哈希表
					while (cur != nullptr)
					{
						Node* next = cur->_next;
						// 重新分配hashi
						size_t hashi = cur->_kv.first % _table.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

				}
			}
	
			//头插 
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			return true;
		}

		Node *   Find(const K & key)
		{
			size_t hashi = key % _table.size();
			Node* cur = _table[hashi];
			while (cur != nullptr)
			{
				if (key == cur->_kv.first)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		bool Erase(const K & key)
		{
			size_t hashi = key % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur != nullptr)
			{
				if (key == cur->_kv.first)
				{
					  if(prev==nullptr)//第二种情况 ,prev是nullptr ,就是头删
					  {
						_table[hashi] = cur->_next;
					  }
					  else//第一种情况 ,cur是头节点
					  {
						  prev->_next = cur->_next;
					  }
					  delete cur;
					return  true; 
				}
				prev = cur;
				cur = cur->_next;
			}
		

			//没找到 
			return false;
		}
		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur != nullptr)
				{
				
					cout << cur->_kv.first << "->";
					cur = cur->_next;
				}
				printf("NULL\n");
			}
			cout << endl;
		}
	private:
		vector<Node*> _table;//指针数组
		size_t  _n = 0;//存储有效数据

	};
}

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/276045.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

MySQL数据库多版本并发控制（MVCC)

MySQL数据库多版本并发控制（MVCC)

在数据库中&#xff0c;并发控制是确保多个事务能够同时执行&#xff0c;而不会导致数据不一致或冲突的关键机制。多版本并发控制(MVCC)是一种流行的并发控制方法&#xff0c;它可以允许多个事务同时读取同一数据项的不同版本&#xff0c;而不会相互阻塞。本文将讨论MVCC的原理…
阅读更多...
【每日一题】LeetCode206.反转链表

【每日一题】LeetCode206.反转链表

个人主页&#xff1a;白日依山璟 专栏&#xff1a;Java|数据结构与算法|每日一题 文章目录 1. 题目描述示例1示例2示例3提示 2. 思路3.代码 1. 题目描述 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例1 输入&#xff1a;head [1…
阅读更多...
FreeRTOS任务调度

FreeRTOS任务调度

开启任务调度器 vTaskStartScheduler(); 无参数, 无返回值. 作用是用于启动任务调度器&#xff0c;任务调度器启动后&#xff0c; FreeRTOS 便会开始进行任务调度 . 如果允许了静态创建任务, 则创建空闲任务和创建定时器任务都会变为需要程序员手动实现创建. 1.创建空闲任务(…
阅读更多...
成为一名成功的互联网产品经理需要掌握哪些技能？

成为一名成功的互联网产品经理需要掌握哪些技能？

在现代互联网产业中&#xff0c;产品经理扮演着至关重要的角色。作为产品经理&#xff0c;需要不断地学习和提高自己的技能&#xff0c;以便为用户提供更佳的产品体验。以下是成为一名成功的互联网产品经理所需要掌握的技能&#xff1a; 1.产品设计技能 产品设计是产品经理的…
阅读更多...
Linux 线程概念

Linux 线程概念

文章目录 前言线程的概念线程的操作操作的原理补充与说明 前言 ① 函数的具体说明被放在补充与说明部分 ② 只说些基础概念和函数使用 线程的概念 网络回答&#xff1a;Linux 线程是指在 Linux 操作系统中创建和管理的轻量级执行单元。线程是进程的一部分&#xff0c;与进程…
阅读更多...
使用数组创建链表的解决方案

使用数组创建链表的解决方案

因为在创建链表时用到了这种方法&#xff0c;后面发现这种方法创建链表做删除操作时不是很好&#xff0c;就打算删除&#xff0c;但是觉得这种方法可能对部分读者有参考意义&#xff0c;就基于数组创建链表的方法单独发了一篇&#xff0c;完整的~链表五大基础操作的实现方法可参…
阅读更多...
2022 年全国职业院校技能大赛高职组云计算正式赛卷第二场-容器云

2022 年全国职业院校技能大赛高职组云计算正式赛卷第二场-容器云

2022 年全国职业院校技能大赛高职组云计算赛项试卷 云计算赛项第二场-容器云 目录 2022 年全国职业院校技能大赛高职组云计算赛项试卷 【赛程名称】云计算赛项第二场-容器云 【任务 1】容器云平台搭建[5 分] 【任务 2】容器云应用部署&#xff1a; Docker Compose 编排部署[7.0…
阅读更多...
Python新手上路：“用Python和Pygame创造你的流星雨”

Python新手上路：“用Python和Pygame创造你的流星雨”

文章目录 一、前言二、下载安装过程1.官网下载安装包2.安装python过程第一步第二步第三步第四步第五步安装完成 3.简单测试Python3.1 检查 Python 版本号3.2 打开 Python 解释器3.3 输入你的第一个代码3.4 运行 Python 脚本 4.安装Pygame4.1 cmd命令安装Pygame4.2 pip升级4.3 安…
阅读更多...
thinkcmf 文件包含 x1.6.0-x2.2.3 已亲自复现

thinkcmf 文件包含 x1.6.0-x2.2.3 已亲自复现

thinkcmf 文件包含 x1.6.0-x2.2.3 CVE-2019-16278 已亲自复现 漏洞名称漏洞描述影响版本 漏洞复现环境搭建漏洞利用 修复建议总结 漏洞名称 漏洞描述 ThinkCMF是一款基于PHPMYSQL开发的中文内容管理框架&#xff0c;底层采用ThinkPHP3.2.3构建。ThinkCMF提出灵活的应用机制&a…
阅读更多...
k8s的二进制部署（二）网络

k8s的二进制部署（二）网络

节点部署完成之后,节点的状态都是Notready&#xff0c;所以要部署k8s网络&#xff1a; k8s的网络类型&#xff1a; k8s中的通信模式&#xff1a; pod内部之间容器与容器之间的通信。 在同一个pod中的容器共享资源和网络&#xff0c;使用同一个网络命名空间&#xff0c;可以直…
阅读更多...
设计模式（4）--对象行为(6)--备忘录

设计模式（4）--对象行为(6)--备忘录

1. 意图 在不破坏封装的前提下&#xff0c;捕获一个对象的内部状态&#xff0c;并在该对象之外保存这个状态。 这样以后可以将该对象恢复到原先保存的状态。 2. 三种角色 原发器(Originator)、备忘录(Memento)、负责人(Caretaker) 3. 优点 3.1 保持了封装边界。屏蔽了原发器的…
阅读更多...
（13）Linux 进程的优先级、进程的切换以及环境变量等

（13）Linux 进程的优先级、进程的切换以及环境变量等

前言&#xff1a;我们先讲解进程的优先级。然后讲解进程的切换&#xff0c;最后我们讲解环境变量&#xff0c;并且做一个 "让自己的可执行程序不带路径也能执行"的实践&#xff0c;讲解环境变量的到如何删除&#xff0c;最后再讲几个常见的环境变量。 一、进程优先级…
阅读更多...
redis的搭建及应用(二)-redis的持久化策略

redis的搭建及应用(二)-redis的持久化策略

Redis的持久化策略 RDB RDB持久化是指在指定的时间间隔内将redis内存中的数据集快照写入磁盘&#xff0c;实现原理是redis服务在指定的时间间隔内先fork一个子进程&#xff0c;由子进程将数据集写入临时文件&#xff0c;写入成功后&#xff0c;再替换之前的文件&#xff0c;用二…
阅读更多...
Spring对bean的管理

Spring对bean的管理

一.bean的实例化 1.spring通过反射调用类的无参构造方法 在pom.xml文件中导入坐标&#xff1a; <dependencies><dependency><groupId>org.springframework</groupId><artifactId>spring-context</artifactId><version>5.3.29<…
阅读更多...
云手机引领社交平台运营新潮流

云手机引领社交平台运营新潮流

在网络高度发展的今天&#xff0c;社交平台已经成为企业宣传推广的关键渠道之一。传统的社交运营方式已经无法满足效率的要求&#xff0c;云手机因而开始引领社交平台运营的新潮流。本文将深入探讨云手机如何重新定义社交平台运营&#xff0c;为用户和企业带来更为便捷、智能的…
阅读更多...
w7数据库基础之mysql函数

w7数据库基础之mysql函数

系统函数 1.version() --mysql版本 2.user() --当前登录的数据库用户名system_user() 3.database() --当前使用的数据库名。schema() 4.datadir --数据库路径 5.version_compile_os 操作系统版本&#xff0c;like 后面可以使用%%进行模糊查询。 6.hostname 当前机器…
阅读更多...
BFS解决多源最短路相关leetcode算法题

BFS解决多源最短路相关leetcode算法题

文章目录 1.01矩阵2.飞地的数量3.地图中的最高点4.地图分析 1.01矩阵 01矩阵 class Solution {int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0}; public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {//正难则反&#xff0c;找0…
阅读更多...
Apache Commons JCS缓存解决方案

Apache Commons JCS缓存解决方案

第1章&#xff1a;引言 大家好&#xff0c;我是小黑&#xff01;今天&#xff0c;咱们来聊聊Apache Commons JCS&#xff0c;一个Java界里的缓存大杀器。缓存技术&#xff0c;对于提高应用性能来说&#xff0c;就像是给它加了一剂兴奋剂&#xff0c;能让数据访问变得快如闪电。…
阅读更多...
Go 泛型之泛型约束

Go 泛型之泛型约束

Go 泛型之泛型约束 文章目录 Go 泛型之泛型约束一、引入二、最宽松的约束&#xff1a;any三、支持比较操作的内置约束&#xff1a;comparable四、自定义约束五、类型集合&#xff08;type set&#xff09;六、简化版的约束形式七、约束的类型推断八、小结 一、引入 虽然泛型是…
阅读更多...
uniCloud 创建项目

uniCloud 创建项目

1. 新建项目 2. 新建云服务空间 若提示需登录&#xff0c;则登录 若提示需实名认证&#xff0c;则完成实名认证 3. 关联云服务空间 关联成功后
阅读更多...
最新文章

Copyright @ 2022~2023