C++哈希（链地址法）（二）详解

文章目录

  • 1.开放地址法
    • 1.1key不能取模的问题
      • 1.1.1将字符串转为整型
      • 1.1.2将日期类转为整型
  • 2.哈希函数
    • 2.1乘法散列法（了解）
    • 2.2全域散列法（了解）
  • 3.处理哈希冲突
    • 3.1线性探测（挨着找）
    • 3.2二次探测（跳跃着找）
    • 3.3双重散列（了解）
  • 4.链地址法
    • 4.1扩容
    • 4.2基本的框架
    • 4.3插入
    • 4.4查找
    • 4.5删除
  • 5.代码

1.开放地址法

1.1key不能取模的问题

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加一个仿函数，这个仿函数支持把key转换成一个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个Key不能转换为整形，我们就需要自己实现一个仿函数传给这个参数，实现这个仿函数的要求就是尽量key的每个值都参与到计算中，让不同的key转换出的整形值不同。string做哈希表的key非常常见，所以我们可以考虑把string特化一下。

1.1.1将字符串转为整型

key如果是字符串，转为整形需要仿函数

// key / M , M哈希表的空间大小
size_t hash0 = hash(kv.first) % _tables.size();

// 将key转为无符号的整形，因为key可能是负数
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (auto& ch : s)
		{
			sum += ch;
			sum *= 131;
			// *131为了避免哈希冲突,每次的key都不一样
		}

		return sum;
	}
};

int main()
{
	const char* a[] = { "abcd","def","gca" };
	HashTable<string, string> ha;

	// 类型+()是匿名对象
	// 哈希冲突了
	cout << HashFunc<string>()("abcd") << endl;
	cout << HashFunc<string>()("aadd") << endl;
	cout << HashFunc<string>()("acbd") << endl;

	for (auto& ch : a)
	{
		ha.Insert({ ch,ch });
	}
    
    return 0;
}

1.1.2将日期类转为整型

struct Date
{
	int _year;
	int _month;
	int _day;

	Date(int year = 1,int month = 1,int day = 1)
		:_year(year),
		_month(month),
		_day(day)
	{}

	bool operator==(const Date& d)
	{
		return _year == d._year&&
			_month == d._month&&
			_day == d._day;
	}
};

struct DateHashFunc
{
	size_t operator()(const Date& d)
	{
		size_t hash = 0;
		hash += d._year;
		hash *= 131;

		hash += d._month;
		hash *= 131;

		hash += d._day;
		hash *= 131;

		return hash;
	}
};

int main()
{
	// 将日期类转化为整型
	HashTable<Date, int, DateHashFunc> ht;
	ht.Insert({ { 2024,12,10 }, 1 });
	ht.Insert({ { 2024,10,12 }, 1 });

	return 0;
}

2.哈希函数

设计哈希函数为了减少冲突，让更多的位参与运算，不管使用%不太接近2的幂次方的质数，还是用位运算计算都是可以的

2.1乘法散列法（了解）

  1. 乘法散列法对哈希表大小M没有要求，他的大思路第一步：用关键字 Key 乘上常数 A (0<A<1)，并抽
    取出 key * A 的小数部分。第二步：后再用M乘以key*A 的小数部分，再向下取整。
  2. h(key) = floor(M × ((A × key)%1.0)) ，其中floor表示对表达式进行下取整，A∈(0,1)，这里最重要的是A的值应该如何设定，Knuth认为 A = ( 5 − 1)/2 = 0.6180339887… (黄金分割点])比较好。
  3. 乘法散列法对哈希表大小M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A * key
    = 762.6539420558，取小数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 =669.6366651392，那么h(1234) = 669。

2.2全域散列法（了解）

  1. 如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。
  2. hab (key) = ((a × key + b)%P)%M ，P需要选⼀个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了一个P*(P-1)组全域散列函数组。假设P=17，M=6，a = 3， b = 4, 则 h34 (8) = ((3 × 8 + 4)%17)%6 = 5 。
  3. 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个散列函数，就会导致找不到插入的key了。

在这里插入图片描述

3.处理哈希冲突

3.1线性探测（挨着找）

缺点：堆积

3.2二次探测（跳跃着找）

缺点：无法充分利用位置
3.1和3.2上一篇博客详细说明了

3.3双重散列（了解）

缺点：虽然可以充分利用位置，但是还是要解决冲突的问题

  • h1 (key) = hash0 = key % M , hash0位置冲突了，则双重探测公式为：hc(key, i) = hashi =
    (hash0 + i ∗ h2 (key)) % M， i = {1, 2, 3, …, M}
  • 要求 h2 (key) < M 且 h2 (key) 和M互为质数，有两种简单的取值方法：
    1、当M为2整数幂时，h2 (key) 从[0，M-1]任选一个奇数；
    2、当M为质数时， h2 (key) = key % (M − 1) + 1
  • 反例：保证 h2 (key) 与M互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为p = gcd(M, h1 (key)) > 1 ，那么所能寻址的位置的个数为 M/P < M ，使得对于一个关键字来
    12/gcd(12, 3) = 4
  • 下面演示 {19,30,52,74} 等这一组值映射到M=11的表中，设 h2 (key) = key%10 + 1
  • 本质是跳跃探测，减少冲突堆积
  • 双重散列就是让数据更加地分散，不容易产生哈希冲突

在这里插入图片描述

4.链地址法

开放地址法的问题是你占别人位置，别人来了又占其他人的位置，链地址法就不用占别人的位置，自己位置可以存多个位置，用了链表挂了多个数据

4.1扩容

  • 开放地址法的负载因子必须小于1，链地址法的负载因子没有这种规定，可以大于1，但是unordered_xxx中最大负载因子基本控制在1，大于1就会扩容。
    在这里插入图片描述

4.2基本的框架

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 HashTable<K, V> Node;
	public:
		// 构造
		HashTable()
			:_tables(__stl_next_prime(0)),
			_n(0)
		{}
		
	private:
		vector<Node*> _tables;// 指针数组
		size_t _n;// 表示存了多少个数据
	};
}

4.3插入

头插，尾插都可以，这里用了头插
在这里插入图片描述

// 插入
bool Insert(const pair<K,V>& kv)
{
	// 负载因子 == 1时扩容
	if (_n == _tables.size())
	{
		// 这种方法每个节点都要拷贝,影响效率
		// 并且原数组释放完后,不会自动析构每个节点,因为是内置类型
		// 还要自己写析构函数,比较麻烦
	    
		//HashTable<K, V> newht;
		//newht._tables.resize(_stl_next_prime(tables.size() + 1));
		//
		//for(size_t i = 0;i < _tables.size();i++)
		//{
		//	// 旧表的数据扩容后可能不冲突,必须一个一个取
		//	Node* cur = _tables[i];
		//	while (cur)
		//	{
		//		newht.Insert(cur->_kv);
		//		cur = cur->_next;
		//	}
		//}
		//_tables.swap(newht._tables);

		
		vector<Node*> newTable(_tables.size() * 2);
		for(size_t i = 0;i < _tables.size();i++)
		{
			// 表旧表中的数据插入到新表中
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				// 算cur在新表中的位置
				size_t hashi = cur->_kv.first % newTable.size();
				cur->_next = newTable[hashi];
				newTable[hashi] = cur;

				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newTable);
	}

	size_t hashi = kv.first % _tables.size();
	
	// 头插
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return true;
}

int main()
{
	int a2[] = { 19,30,5,36,13,20,21,12,24,96 };
	hash_bucket::HashTable<int, int> ht;

	for (auto e : a2)
	{
		ht.Insert({ e,e });
	}

	ht.Insert({ 100,100 });
	ht.Insert({ 200,200 });

	return 0;
}

4.4查找

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

	return nullptr;
}

4.5删除

删除分为三种情况：

  1. 头删，让下一个节点变为头节点
  2. 删除中间的节点，保留前一个节点的指针指向后一个节点的指针
  3. 尾删，让最后一个节点的前一个节点的指针指向空
  4. 2和3可以归为一类，删除中间的节点可以是前一个节点指向空
    在这里插入图片描述
// 删除
bool Erase(const K& key)
{
	size_t hashi = 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;

			--_n;
			return true;
		}
		else
		{
			prev = cur;
			cur = cur->_next;
		}
	}

	return false;
}

5.代码

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(__stl_next_prime(0)),
			_n(0)
		{}

		// 析构
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;

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

		// 插入
		bool Insert(const pair<K,V>& kv)
		{
			Hash hash;

			// 如果插入的值存在冗余了返回false
			if (Find(kv.first))
			{
				return false;
			}

			// 负载因子 == 1时扩容
			if (_n == _tables.size())
			{
				// 这种方法每个节点都要拷贝,影响效率
				// 并且原数组释放完后,不会自动析构每个节点,因为是内置类型
				// 还要自己写析构函数,比较麻烦
			    
				//HashTable<K, V> newht;
				//newht._tables.resize(_stl_next_prime(tables.size() + 1));
				//
				//for(size_t i = 0;i < _tables.size();i++)
				//{
				//	// 旧表的数据扩容后可能不冲突,必须一个一个取
				//	Node* cur = _tables[i];
				//	while (cur)
				//	{
				//		newht.Insert(cur->_kv);
				//		cur = cur->_next;
				//	}
				//}
				//_tables.swap(newht._tables);

				
				vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));
				for(size_t i = 0;i < _tables.size();i++)
				{
					// 表旧表中的数据插入到新表中
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						// 算cur在新表中的位置
						size_t hashi = hash(cur->_kv.first) % newTable.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTable);
			}

			size_t hashi = hash(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 hash;

			size_t hashi = hash(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)
		{
			size_t hashi = 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;

					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

	private:
		vector<Node*> _tables;// 指针数组
		size_t _n;// 表示存了多少个数据
	};
}

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

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

相关文章

记6（人工神经网络

记6（人工神经网络

目录 1、M-P神经元2、感知机3、Delta法则4、前馈型神经网络&#xff08;Feedforward Neural Networks&#xff09;5、鸢尾花数据集——单层前馈型神经网络&#xff1a;6、多层神经网络&#xff1a;增加隐含层7、实现异或运算&#xff08;01、10为1,00、11为0&#xff09;8、线性…
阅读更多...
增删改查(CRUD)操作

增删改查(CRUD)操作

文章目录 MySQL系列&#xff1a;1.CRUD简介2.Create(创建)2.1单行数据全列插入2.2 单行数据指定插入2.3 多⾏数据指定列插⼊ 3.Retrieve(读取)3.1 Select查询3.1.1 全列查询3.1.2 指定列查询3.1.3 查询字段为表达式&#xff08;都是临时表不会对原有表数据产生影响&#xff09;…
阅读更多...
python 语音识别

python 语音识别

目录 一、语音识别 二、代码实践 2.1 使用vosk三方库 2.2 使用SpeechRecognition 2.3 使用Whisper 一、语音识别 今天识别了别人做的这个app，觉得虽然是个日记app 但是用来学英语也挺好的，能进行语音识别，然后矫正语法，自己说的时候 ，实在不知道怎么说可以先乱说，然…
阅读更多...
openssl 生成证书 windows导入证书

openssl 生成证书 windows导入证书

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 源码指引&#xff1a;github源…
阅读更多...
深度学习编译器的演进：从计算图到跨硬件部署的自动化之路

深度学习编译器的演进：从计算图到跨硬件部署的自动化之路

第一章 问题的诞生——深度学习部署的硬件困境 1.1 计算图的理想化抽象 什么是计算图&#xff1f; 想象你正在组装乐高积木。每个积木块代表一个数学运算&#xff08;如加法、乘法&#xff09;&#xff0c;积木之间的连接代表数据流动。深度学习框架正是用这种"积木拼接…
阅读更多...
Agentic Automation：基于Agent的企业认知架构重构与数字化转型跃迁---我的AI经典战例

Agentic Automation：基于Agent的企业认知架构重构与数字化转型跃迁---我的AI经典战例

文章目录 Agent代理Agent组成 我在企业实战AI Agent企业痛点我构建的AI Agent App 项目开源 & 安装包下载 大家好&#xff0c;我是工程师令狐&#xff0c;今天想给大家讲解一下AI智能体&#xff0c;以及企业与AI智能体的结合&#xff0c;文章中我会列举自己在企业中Agent实…
阅读更多...
论文阅读：Realistic Noise Synthesis with Diffusion Models

论文阅读：Realistic Noise Synthesis with Diffusion Models

这篇文章是 2025 AAAI 的一篇工作&#xff0c;主要介绍的是用扩散模型实现对真实噪声的仿真模拟 Abstract 深度去噪模型需要大量来自现实世界的训练数据&#xff0c;而获取这些数据颇具挑战性。当前的噪声合成技术难以准确模拟复杂的噪声分布。我们提出一种新颖的逼真噪声合成…
阅读更多...
Baklib揭示内容中台与人工智能技术的创新协同效应

Baklib揭示内容中台与人工智能技术的创新协同效应

内容概要 在当今信息爆炸的时代&#xff0c;内容的高效生产与分发已成为各行业竞争的关键。内容中台与人工智能技术的结合&#xff0c;为企业提供了一种新颖的解决方案&#xff0c;使得内容创造的流程更加智能化和高效化。 内容中台作为信息流动的核心&#xff0c;能够集中管…
阅读更多...
Spring Boot 中的事件发布与监听：深入理解 ApplicationEventPublisher（附Demo）

Spring Boot 中的事件发布与监听：深入理解 ApplicationEventPublisher（附Demo）

目录 前言1. 基本知识2. Demo3. 实战代码 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 基本的Java知识推荐阅读&#xff1a; java框架 零基础从入门到精通的学习路线 附开源项目面经等&#xff08;超全&am…
阅读更多...
DeepSeek 第二弹：Janus-Pro 文生图模型

DeepSeek 第二弹：Janus-Pro 文生图模型

最近&#xff0c;DeepSeek 可谓是科技圈的焦点&#xff0c;还火出了圈外&#xff0c;掀起了一场全民创作热潮。大家纷纷借助 DeepSeek R1 挥洒才情&#xff0c;实现诗人、小说家的梦想。然而&#xff0c;就在这场文字狂欢之际&#xff0c;DeepSeek 又悄然推出了一款重磅产品——…
阅读更多...
leetcode 2563. 统计公平数对的数目

leetcode 2563. 统计公平数对的数目

题目如下 数据范围 显然数组长度最大可以到10的5次方n方的复杂度必然超时&#xff0c;阅读题目实际上就是寻找两个位置不同的数满足不等式即可(实际上i j无所谓是哪个 我们只要把位置小的想成i就行)。 按照上面的思路我们只需要排序数组然后从前往后遍历数组然后利用二分查找…
阅读更多...
2024第十五届蓝桥杯网安赛道省赛题目--cc(CyberChef)/crypto

2024第十五届蓝桥杯网安赛道省赛题目--cc(CyberChef)/crypto

打开链接后是&#xff1a; 通过题目界面可以知道是AES加密&#xff0c;并且告诉我们key是gamelabgamelab&#xff0c;IV是gamelabgamelab&#xff0c;Mode是CBC模式&#xff0c;输入是flag&#xff0c;输出为Hex十六进制4da72144967f1c25e6273950bf29342aae635e2396ae17c80b1b…
阅读更多...
【视频+图文详解】HTML基础4-html标签的基本使用

【视频+图文详解】HTML基础4-html标签的基本使用

图文教程 html标签的基本使用 无序列表 作用&#xff1a;定义一个没有顺序的列表结构 由两个标签组成&#xff1a;<ul>以及<li>&#xff08;两个标签都属于容器级标签&#xff0c;其中ul只能嵌套li标签&#xff0c;但li标签能嵌套任何标签&#xff0c;甚至ul标…
阅读更多...
Python-基于PyQt5,wordcloud,pillow,numpy,os,sys等的智能词云生成器

Python-基于PyQt5,wordcloud,pillow,numpy,os,sys等的智能词云生成器

前言&#xff1a;日常生活中&#xff0c;我们有时后就会遇见这样的情形&#xff1a;我们需要将给定的数据进行可视化处理&#xff0c;同时保证呈现比较良好的量化效果。这时候我们可能就会用到词云图。词云图&#xff08;Word cloud&#xff09;又称文字云&#xff0c;是一种文…
阅读更多...
自制虚拟机(C/C++)(二、分析引导扇区，虚拟机读二进制文件img软盘)

自制虚拟机(C/C++)(二、分析引导扇区，虚拟机读二进制文件img软盘)

先修复上一次的bug&#xff0c;添加新指令&#xff0c;并增加图形界面 #include <graphics.h> #include <conio.h> #include <windows.h> #include <commdlg.h> #include <iostream> #include <fstream> #include <sstream> #inclu…
阅读更多...
工作流引擎Camunda

工作流引擎Camunda

一&#xff0c;什么是Camunda&#xff1f; Camunda是一个开源的工作流引擎和业务流程管理平台&#xff0c;基于Java和Spring框架构建。它支持BPMN 2.0标准&#xff0c;允许用户通过图形界面或编程方式定义复杂的工作流和业务流程。Camunda可以嵌入到任何Java应用程序中&#x…
阅读更多...
C++，STL，【目录篇】

C++，STL，【目录篇】

文章目录 一、简介二、内容提纲第一部分&#xff1a;STL 概述第二部分&#xff1a;STL 容器第三部分&#xff1a;STL 迭代器第四部分&#xff1a;STL 算法第五部分&#xff1a;STL 函数对象第六部分&#xff1a;STL 高级主题第七部分&#xff1a;STL 实战应用 三、写作风格四、…
阅读更多...
【已解决】黑马点评项目Redis版本替换过程的数据迁移

【已解决】黑马点评项目Redis版本替换过程的数据迁移

黑马点评项目Redis版本替换过程的数据迁移 【哭哭哭】附近商户中需要用到的GEO功能只在Redis 6.2以上版本生效 如果用的是老版本&#xff0c;美食/KTV的主页能正常返回&#xff0c;但无法显示内容 上次好不容易升到了5.0以上版本&#xff0c;现在又用不了了 Redis 6.2的windo…
阅读更多...
文献阅读 250201-The carbon budget of China: 1980–2021

文献阅读 250201-The carbon budget of China: 1980–2021

The carbon budget of China: 1980–2021 来自 <https://www.sciencedirect.com/science/article/pii/S2095927323007703> 中国碳预算&#xff1a;1980–2021 年 ## Abstract: Using state-of-the-art datasets and models, this study comprehensively estimated the an…
阅读更多...
《OpenCV》——图像透视转换

《OpenCV》——图像透视转换

图像透视转换简介 在 OpenCV 里&#xff0c;图像透视转换属于重要的几何变换&#xff0c;也被叫做投影变换。下面从原理、实现步骤、相关函数和应用场景几个方面为你详细介绍。 原理 实现步骤 选取对应点&#xff1a;要在源图像和目标图像上分别找出至少四个对应的点。这些对…
阅读更多...
最新文章

Copyright @ 2022~2023