哈希表的实现（2）：拉链法实现哈希表

一，拉链法

在使用线性探测法实现哈希表时，会发生哈希冲突。这个时候就得向后找位置给新插入的值。这个过程无疑会对哈希表的效率有很大的影响。那我们能不能通过另一种方式来实现哈希表，让哈希表不会发生哈希冲突呢？答案当然是可以的，这个方法就被叫做拉链法。

拉链法：

拉链法就是让哈希表里的元素存的是一个单链表指针，然后像链表一样头插哈希值相同的元素到同一个位置上。

如图所示：

二，哈希表的实现

1，定义节点

再stl库里面有现成的单链表可以使用，但是为什么我们要自己定义一个节点呢？这其实是为了后续的哈希表的封装打下基础。

节点定义如下：

template<class K,class V>
	struct Node
	{
		Node(const pair<K,V>key)
			:_kv(key)
			,next(nullptr)
		{}
 
		pair<K, V>_kv;
		Node<K, V>* next;
	};

 2，定义哈希表

还是和使用线性探测法实现哈希表类似，哈希表里面主要有两个成员：

1，vector<Node<K,V>*>_hashtables。

2，_n。

哈希表结构如下：

class Hash_table
	{
	public:
       Hash_table()
		{
			_hashtables.resize(10, nullptr);//先初始化，开好十个空间
		}

    private:
        vector<Node<K,V>*>_hashtables;
        size_t _n = 0;
    }

3，Insert函数实现

1，算出hashi,使用的方法还是除留余数法法。

2，插入，使用头插法插入。不需要判断是否为空。

3，当插入的个数_n ==_hashtables.size()时便要扩容。

在这里扩容的方式有两种：

 1，创建新的哈希表，调用Insert将旧表的内容插入到新表里面。插入结束后再将新表换给旧表

 2，创建新的vector<Node<K,V>*>new_tables,再将旧表的_hashtables里的节点一个一个的搬到new_tables里。搬完以后再将新表换给旧表。

代码如下：

//插入函数
		bool Insert(const pair<K, V> key)//插入节点
		{
			 
			if (_n == _hashtables.size())//表已被填满
			{
			//	//解决方式1：开一个新表，将旧表里面的内容重新插入到新表里在交换
			//	Hash_table<K, V>new_Ht;
			//	int newSize = _hashtables.size()*2;
			//	new_Ht._hashtables.resize(newSize);

			//	for (int i = 0;i < _hashtables.size();i++)
			//	{
			//		Node<K, V>* cur = _hashtables[i];
			//		while(cur)
			//		{
			//			new_Ht.Insert(cur->_kv);
			//			cur = cur->next;
			//		}
			//	}

			//	_hashtables.swap(new_Ht._hashtables);

				//解决方式2：不要直接插入，而是要将就表里的链移到新表里，然后再交换。这种方式更加高效，不会浪费太多的空间
				vector<Node<K,V>*> new_tables;
				int newSize = 2 * _hashtables.size();//扩容后的大小
				new_tables.resize(newSize);//给新的new_tables开两倍的空间

				for (int i = 0;i < _hashtables.size();i++)
				{
					Hash Func;
					Node<K,V>* cur =_hashtables[i];
					while (cur)//将链表节点搬到new_tables里
					{
						Node<K,V>* next = cur->next;
						size_t idx =  Func(cur->_kv.first) % newSize;
						cur->next = new_tables[idx];
						new_tables[idx] = cur;
						cur = next;
					}

					_hashtables[i] = nullptr;//搬完以后要将原来旧表对应的值变为nullptr,fan防止二次析构
				}
			 
				 

				_hashtables.swap(new_tables);//交换
			}

			Hash Func;//类模板实例化出来一个类
			size_t hashi = Func(key.first) % _hashtables.size();//计数出映射的位置
			Node<K,V>* newNode = new Node<K,V>(key);//先new出来一个新节点

			//头插
			Node<K,V>* Next = _hashtables[hashi];
			_hashtables[hashi] = newNode;
			newNode->next = Next;

			_n++;//插入成功个数加1
			return true;

	    }

4，Find函数实现

1，计算hashi,遍历查找每这个hashi对应的链表，查找到了便返回该节点的地址。

2，遍历以后没有返回结果便返回nullptr。

代码：Hash hf表示一个仿函数，作用是将key转化为整型值。

Node<K, V>* Find(const K& key)
		{
			Hash hf;
			int hashi = hf(key) % _hashtables.size();//计算hashi
			Node<K, V>* cur = _hashtables[hashi];
			while (cur)//遍历hashi对应的链表
			{
				if (cur->_kv.first== key)
				{
					return cur;//找到了便可以返回节点d
				}
				cur = cur->next;
			}
			 
			return nullptr;//找不到便返回nullptr
		}

5，Erase函数

1,通过计算得到hashi。

2，再遍历hashi,进行删除节点的操作。

3，_n--

代码：

bool Erase(const K& key)
		{
			int hashi = key % _hashtables.size();//计算hashi
            
            //定义两个指针pre和cur,来进行删除操作，pre保存cur的上一个节点的地址。
			Node<K, V>* cur = _hashtables[hashi];
			Node<K, V>* pre = nullptr;
			while (cur)
			{
				if (cur->_kv.second == key)
				{
					if (pre)
					{
						pre->next = cur->next;//cur不是头节点时
						
					}
					else
					{
						_hashtables[hashi] = cur->next;//cur是头节点时
					}

					delete cur;//删除cur指向的节点
					_n--;//个数减一
					return true;
				}

				pre = cur;
				cur = pre->next;
			}

			return false;
		}

6，析构函数

1，Node<K,V>节点是我自己定义的节点，所以编译器不会自动的释放这些节点。所以需要我们自己来手动释放。

2，释放的方式也很简单，通过遍历找到表里不是空的节点。再遍历这些节点依次释放。

代码：

~Hash_table()//vector里面的链表时自己实现的，所以要写构造函数将这些节点释放
		{
			int n = _hashtables.size();
			for (int i = 0;i < n;i++)//遍历表
			{
				Node<K, V>* cur = _hashtables[i];//当前节点
				Node<K, V>* next = nullptr;//下一个节点
				while (cur)//遍历释放节点
				{
					next = cur->next;
					delete cur;
					cur = next;
				}
			}
		}

7，拷贝构造函数

1，为了避免析构两次的问题，就得构造新的Node<K,V>*节点，这个节点里的值由拷贝的对象提供

2，实现链表的链接。

代码：

//拷贝构造函数
		Hash_table(const Hash_table<K, V>& hash)
		{

			int newSize = hash._hashtables.size();//拷贝对象的表的大小
			_hashtables.resize(newSize);//开与拷贝对象一样大小的空间

			for (int i = 0;i < newSize;i++)
			{
				Node<K, V>* cur = hash._hashtables[i];//cur指向拷贝对象的链表节点

				Node<K, V>* headNode = nullptr;//指向拷贝者的链表头
				Node<K, V>* ptr = nullptr;//指向拷贝者的链表节点

				if (cur)
				{

					while (cur)
					{
						Node<K, V>* node = new Node<K, V>(cur->_kv);//new出新节点，避免二次析构
						if (!headNode)//链接操作
						{
							headNode = node;//头节点为空，就先将头节点初始化。
						}
						else//链接操作
						{
							ptr = headNode;
							while (ptr->next)//找到链表的尾节点
							{
								ptr = ptr->next;
							}
							ptr->next = node;
						}

						cur = cur->next;
						_n++;
					}

					_hashtables[i] = headNode;//链接完了以后将头节点交给_hashtables[i]

				}
				 
			}
			 
		}

8，赋值重载

1，构造新表，拷贝赋值者。

2，将新表换给自己。

代码：

//赋值重载
		Hash_table<K, V>& operator =(const Hash_table<K, V>&hash)
		{
			Hash_table<K, V>new_Ht(hash);
			_hashtables.swap(new_Ht._hashtables);
			_n = new_Ht._n;
			return *this;
		}

三，全部代码

//开散列，拉链法实现哈希表
#include<string>
#include<iostream>
#include<vector>
using namespace std;
namespace close_locate
{
	template<class K,class V>
	struct Node
	{
		Node(const pair<K,V>key)
			:_kv(key)
			,next(nullptr)
		{}
 
		pair<K, V>_kv;
		Node<K, V>* next;
	};

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

	};

	template <>
	struct Getkey<string>
	{
		size_t operator()(const string& key)
		{
			size_t sum = 0;
			int n = key.size();
			for (int i = 0;i < n;i++)
			{
				sum = sum * 31 + key[i];
			}
			return sum;
		}
	};



	template <class K,class V,class Hash = Getkey<K>>
	class Hash_table
	{
	public:
		template<class K>
		int Getkey(const K& key)
		{
			Hash hf;
			return hf(key)%_hashtables.size();
		}

		Hash_table()
		{
			_hashtables.resize(10, nullptr);//先初始化，开好十个空间
		}

		~Hash_table()//vector里面的链表时自己实现的，所以要写构造函数将这些节点释放
		{
			int n = _hashtables.size();
			for (int i = 0;i < n;i++)
			{
				Node<K, V>* cur = _hashtables[i];
				Node<K, V>* next = nullptr;
				while (cur)
				{
					next = cur->next;
					delete cur;
					cur = next;
				}
			}
		}

		//拷贝构造函数
		Hash_table(const Hash_table<K, V>& hash)
		{

			//Hash_table<K, V> new_Ht;
			int newSize = hash._hashtables.size();
			_hashtables.resize(newSize);

			for (int i = 0;i < newSize;i++)
			{
				Node<K, V>* cur = hash._hashtables[i];
				Node<K, V>* headNode = nullptr;
				Node<K, V>* ptr = _hashtables[i];

				if (cur)
				{

					while (cur)
					{
						Node<K, V>* node = new Node<K, V>(cur->_kv);
						if (!headNode)
						{
							headNode = node;
						}
						else
						{
							ptr = headNode;
							while (ptr->next)
							{
								ptr = ptr->next;
							}
							ptr->next = node;
						}
						cur = cur->next;
						_n++;
					}

					_hashtables[i] = headNode;

				}
				 
			}
			 
		}
			
		//赋值重载
		Hash_table<K, V>& operator =(const Hash_table<K, V>&hash)
		{
			Hash_table<K, V>new_Ht(hash);
			_hashtables.swap(new_Ht._hashtables);
			_n = new_Ht._n;
			return *this;
		}

		
		//插入函数
		bool Insert(const pair<K, V> key)//插入节点
		{
			 
			if (_n == _hashtables.size())//表已被填满
			{
			//	//解决方式1：开一个新表，将旧表里面的内容重新插入到新表里在交换
			//	Hash_table<K, V>new_Ht;
			//	int newSize = _hashtables.size()*2;
			//	new_Ht._hashtables.resize(newSize);

			//	for (int i = 0;i < _hashtables.size();i++)
			//	{
			//		Node<K, V>* cur = _hashtables[i];
			//		while(cur)
			//		{
			//			new_Ht.Insert(cur->_kv);
			//			cur = cur->next;
			//		}
			//	}

			//	_hashtables.swap(new_Ht._hashtables);

				//解决方式2：不要直接插入，而是要将就表里的链移到新表里，然后再交换。这种方式更加高效，不会浪费太多的空间
				vector<Node<K,V>*> new_tables;
				int newSize = 2 * _hashtables.size();
				new_tables.resize(newSize);

				for (int i = 0;i < _hashtables.size();i++)
				{
					Hash Func;
					Node<K,V>* cur =_hashtables[i];
					while (cur)
					{
						Node<K,V>* next = cur->next;
						size_t idx =  Func(cur->_kv.first) % newSize;
						cur->next = new_tables[idx];
						new_tables[idx] = cur;
						cur = next;
					}

					_hashtables[i] = nullptr;
				}
			 
				 

				_hashtables.swap(new_tables);
			}

			Hash Func;//类模板实例化出来一个类
			size_t hashi = Func(key.first) % _hashtables.size();//计数出映射的位置
			Node<K,V>* newNode = new Node<K,V>(key);//先new出来一个新节点

			//头插
			Node<K,V>* Next = _hashtables[hashi];
			_hashtables[hashi] = newNode;
			newNode->next = Next;
			_n++;
			return true;

	    }

		Node<K, V>* Find(const K& key)
		{
			Hash hf;
			int hashi = hf(key) % _hashtables.size();
			Node<K, V>* cur = _hashtables[hashi];
			while (cur)
			{
				if (cur->_kv.first== key)
				{
					return cur;
				}
				cur = cur->next;
			}
			 
			return nullptr;
		}

		bool Erase(const K& key)
		{
			int hashi = key % _hashtables.size();
			Node<K, V>* cur = _hashtables[hashi];
			Node<K, V>* pre = nullptr;
			while (cur)
			{
				if (cur->_kv.second == key)
				{
					if (pre)
					{
						pre->next = cur->next;
						
					}
					else
					{
						_hashtables[hashi] = cur->next;
					}
					delete cur;
					_n--;
					return true;
				}

				pre = cur;
				cur = pre->next;
			}

			return false;
		}

		void buketCount()//统计哈希桶的各种数据
		{
			int Maxlen = 0;//统计最长的哈希桶长度
			int sum = 0;//统计一共有多少个桶
			double averagelen = 0;//统计平均有多少个桶
			int buketCount = 0;

			int n = _hashtables.size();
			for (int i = 0;i < n;i++)
			{
				Node<K, V>* cur = _hashtables[i];
				if (cur)
				{
					buketCount++;
					int len = 0;
					while (cur)
					{
						sum++;
						len++;
						cur = cur->next;
					}
					Maxlen = max(Maxlen, len);
				}
			}

			averagelen = (double)sum / (double)buketCount;

			cout << "buketCount: " << buketCount << " " << "averagelen: " << averagelen << " " << "Maxlen: " << Maxlen << " ";
		}

		void Print()
		{

			int n = _hashtables.size();
			for (int i = 0;i < n;i++)
			{
				Node<K, V>* cur = _hashtables[i];
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << endl;;
					cur = cur->next;
				}
			}

			cout << endl << endl;
		}


	private:
		vector<Node<K,V>*>_hashtables;
		size_t _n = 0;
	};

}

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

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

相关文章

第二十八周：文献阅读笔记（弱监督学习）+ pytorch学习

第二十八周：文献阅读笔记（弱监督学习）+ pytorch学习

第二十八周&#xff1a;文献阅读笔记&#xff08;弱监督学习&#xff09; 摘要Abstract1. 弱监督学习1.1. 文献摘要1.2. 引言1.3. 不完全监督1.3.1. 主动学习与半监督学习1.3.2. 通过人工干预1.3.3. 无需人工干预 1.4. 不确切的监督1.5. 不准确的监督1.6. 弱监督学习的创新点 2…
阅读更多...
Vue-14、Vue绑定style样式

Vue-14、Vue绑定style样式

1、对象写法 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>绑定css样式</title><!--引入vue--><script type"text/javascript" src"https://cdn.jsdelivr.net/npm/v…
阅读更多...
数据结构：堆和堆排序

数据结构：堆和堆排序

数据结构&#xff1a;堆和堆排序 文章目录 数据结构&#xff1a;堆和堆排序1.二叉树的存储结构1.顺序结构2.链式结构 2.堆3.堆的实现4.堆排序&#xff08;选择排序中的一类&#xff09;1. 基本思想2.代码实现 1.二叉树的存储结构 1.顺序结构 顺序结构存储就是使用数组来表示一…
阅读更多...
ssm基于VUE.js的在线教育系统论文

ssm基于VUE.js的在线教育系统论文

摘 要 随着学习压力越来越大&#xff0c;课外参加补习班的学生越来越多。现在大多数学生采用请家教、自学、报名补习班的方式进行课外的额外学习。请家教费用昂贵&#xff0c;自学效率低&#xff0c;碰到自己不会的知识不能及时得到解达&#xff0c;报名补习班需要时间、地点的…
阅读更多...
TinyGPT-V：2.8B参数引领轻量级多模态AI

TinyGPT-V：2.8B参数引领轻量级多模态AI

前言 在当前多模态大型语言模型&#xff08;MLLM&#xff09;快速发展的背景下&#xff0c;TinyGPT-V的出现标志着一个重要的技术突破。这款轻量级模型以其2.8B参数的设计&#xff0c;在AI领域引起广泛关注&#xff0c;成为GPT-4V等模型的高效替代方案。 Huggingface模型下载&…
阅读更多...
爬虫之牛刀小试（六）：爬取BOSS网站招聘的内容

爬虫之牛刀小试（六）：爬取BOSS网站招聘的内容

今天决定再次尝试一下 selenium BOSS网站 想要找到我们感兴趣的职位&#xff0c;随便举个例子吧&#xff0c;比如家教啥的 搜一下 找到我们感兴趣的内容 接着尝试用selenium模拟登录&#xff0c;如下所示&#xff1a; 接着找到对应的位置让selenium自己干就行了。 最后的…
阅读更多...
SSM基础入门

SSM基础入门

SSM Mybatis、Spring和SpringMVC这三个框架整合在一起完成业务功能开发 文章目录 SSM5.1 流程5.2 详细步骤5.2.1 基本配置5.2.2 功能模块开发5.2.3 测试5.2.3.1 单元测试5.2.3.2 PostMan测试 5.3 统一结果封装5.3.1 概念5.3.2 实现 5.4 统一异常处理5.4.1 异常处理器的使用5.4…
阅读更多...
统计学-R语言-4.5

统计学-R语言-4.5

文章目录 前言多变量数据多维列联表复式条形图并列箱线图R语言中取整运算主要包括以下五种&#xff1a; 点带图多变量散点图重叠散点图矩阵式散点图 练习 前言 本篇文章将继续对数据的类型做介绍&#xff0c;本片也是最后一个介绍数据的。 多变量数据 掌握描述多变量数据的分…
阅读更多...
openssl3.2 - 官方demo学习 - server-arg.c

openssl3.2 - 官方demo学习 - server-arg.c

文章目录 openssl3.2 - 官方demo学习 - server-arg.c概述笔记备注END openssl3.2 - 官方demo学习 - server-arg.c 概述 TLS服务器, 等客户端来连接; 如果客户端断开了, 通过释放bio来释放客户端socket, 然后继续通过bio读来aceept. 笔记 对于开源工程, 不可能有作者那么熟悉…
阅读更多...
vue前端开发自学demo,父子组件之间传递数据demo2

vue前端开发自学demo,父子组件之间传递数据demo2

vue前端开发自学demo,父子组件之间传递数据demo2!实际上&#xff0c;组件之间传递数据的&#xff0c;数据类型&#xff0c;是可以多种多样的&#xff0c;下面为大家展示几个常见的数据类型&#xff0c;比如数字类型&#xff0c;数组类型&#xff0c;对象类型。 代码如下所示&a…
阅读更多...
sublime中添加GBK编码模式

sublime中添加GBK编码模式

当写代码的中文注释时&#xff0c;编译代码出现如下错误&#xff1a; 解决办法&#xff0c;添加GBK模式&#xff1a; &#xff11;.　点击Preferences -> Package Control&#xff1a; 2. 在跳出来的搜索框里搜索conver, 点击ConverToUTF8 3. File左上角会多出GBK的选项 由…
阅读更多...
PiflowX-DorisRead组件

PiflowX-DorisRead组件

DorisRead组件 组件说明 从Doris存储读取数据。 计算引擎 flink 有界性 目前Doris Source是有界流&#xff0c;不支持CDC方式读取。 组件分组 Doris 端口 Inport&#xff1a;默认端口 outport&#xff1a;默认端口 组件属性 名称展示名称默认值允许值是否必填描述…
阅读更多...
【遇见Transformer】Transformer代码、原理全方位解析，相信我，看这一篇就够了！

【遇见Transformer】Transformer代码、原理全方位解析，相信我，看这一篇就够了！

目录 前言 预备知识 本章代码环境 关注我&#xff0c;不迷路 &#xff01; Transformer模型的结构​编辑 Transformer模型的基本原理 注意力机制 自注意力机制 两者的区别 多头注意力机制 Transformer模型的训练 Transformer模型的应用 论文地址 前言 预备知识 在…
阅读更多...
学习python仅此一篇就够了（文件操作：读，写，追加）

学习python仅此一篇就够了（文件操作：读，写，追加）

python文件操作 文件编码 编码技术即&#xff1a;翻译的规则&#xff0c;记录了如何将内容翻译成二进制&#xff0c;以及如何将二进制翻译回可识别内容。 计算机中有许多可用编码&#xff1a; UTF-8 GBK BUG5 文件的读取操作 open&#xff08;&#xff09;函数 在pyth…
阅读更多...
数据库锁表原因、排查、解决

数据库锁表原因、排查、解决

一.场景 场景1场景2二.原因三.排查四.解决方案 一.场景 场景1 锁表通常发生在DML&#xff08; insert 、update 、delete &#xff09; A操作进行全量数据同步&#xff0c;对整个表的粒度进行上锁&#xff0c;导致B操作只能等待A操作完成才能进入插入数据。此时就出现了锁表…
阅读更多...
【分布式技术】监控平台zabbix介绍与部署

【分布式技术】监控平台zabbix介绍与部署

目录 一、为什么要做监控&#xff1f; 二、zabbix是什么&#xff1f; 三、zabbix有哪些组件&#xff1f; ​编辑Zabbix 6.0 功能组件&#xff1a; ●Zabbix Server ●数据库 ●Web 界面 ●Zabbix Agent ●Zabbix Proxy ●Java Gateway 四、zabbix的工作原理&#xf…
阅读更多...
test Property-based Testing-04-junit-quickcheck

test Property-based Testing-04-junit-quickcheck

拓展阅读 开源 Auto generate mock data for java test.(便于 Java 测试自动生成对象信息) 开源 Junit performance rely on junit5 and jdk8.(java 性能测试框架。性能测试。压测。测试报告生成。) junit-quickcheck&#xff1a;基于 JUnit 风格的属性驱动测试库 junit-qu…
阅读更多...
对C语言的理解

对C语言的理解

1.计算机语言 就是我们人类与计算机进行交流的媒介。我们可以使用编程语言对计算机下达命令&#xff0c;从而让计算机完成我们所需要的功能。 语言 语法 逻辑 计算机语言有很多种。如&#xff1a;C 、C、Java、Go、JavaScript、Python&#xff0c;Scala等。 2.计算机语言简史…
阅读更多...
Java基础之并发篇（二）

Java基础之并发篇（二）

1、前言 本篇主要基于Java基础之并发篇&#xff08;一&#xff09;继续梳理java中关于并发相关的基础只是。本篇基于网络整理&#xff0c;和自己编辑。在不断的完善补充哦。 2、synchronized 的原理是什么? synchronized是 Java 内置的关键字&#xff0c;它提供了一种独占的…
阅读更多...
Linux CentOS 7.6安装JDK详细保姆级教程

Linux CentOS 7.6安装JDK详细保姆级教程

一、检查系统是否自带jdk java --version 如果有的话&#xff0c;找到对应的文件删除 第一步&#xff1a;先查看Linux自带的JDK有几个&#xff0c;用命令&#xff1a; rpm -qa | grep -i java第二步:删除JDK&#xff0c;执行命令&#xff1a; rpm -qa | grep -i java | xarg…
阅读更多...
最新文章

Copyright @ 2022~2023