【C++进阶】：哈希

2023-09-17 12:39:55

哈希

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log_2N log2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍。

一.unordered_map

  1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
  2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
  3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
  4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
  5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
  6. 它的迭代器至少是前向迭代器。
  7. 它的使用几乎与map一致。

二.底层结构

1.哈希概念

复杂的说

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( l o g 2 N log_2 N log2​N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

简单的说

在这里插入图片描述

上述就是一种k,v的映射关系，为了避免数组越界，我们还会对K(铅笔的号数)进行取模(%capcity)。相信大家也能发现，铅笔的号数肯定远远不止5个，例如：5号铅笔和10号铅笔都会储存在0号位置，这就是下哈希冲突。

2.解决哈希冲突

1.闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

第一种：线性探测

在这里插入图片描述

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

总的来说，将数据放入hash表时，如果该位置被占据，就向后查找，直到找到空位置进行插入。在查询数据时，一直查询直到找到或者找到空位置或者原点时停止。基于查找时找到空位置时停止，所以删除时就不能直接置空，需要标记该位置已被删除。接下来还有一个难点就是扩容。

根据查找规则来看，如果等hash表填满才扩容，毫无疑问会发生很多冲突，这是很低效的，所以必须有一个扩容规则来判断何时扩容。

在这里插入图片描述

enum State
{
	EXIST,
	DELETE,
	EMPTY
};

template<class K,class V>
struct HashData//创建hash表的类型
{
	pair<K, V> _kv;
	State _state=EMPTY;
};

template<class K,class V>
class Hash
{
public:
	Hash()
	{
		_table.resize(10);//初始开10给空间
	}

	void insert(const pair<K, V>& kv)
	{
		//判断是否需要扩容
		if (n * 10 / _table.size() >= 7)
		{
			//开一个新的表容量为原来二倍
			size_t newHash = _table.size() * 2;
			Hash<K, V>newHT;
			newHT._table.resize(newHash);

			//将旧表的值插入到新表里
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._state == EXIST)
					newHT.insert(_table[i]._kv);
			}
			//交换新旧表
			_table.swap(newHT._table);
		}

		//线性探测
		size_t hashi = kv.first % _table.size();//插入位置
		while (_table[hashi]._state == EXIST)//判断应该插入的位置
		{
			hashi++;
			hashi %= _table.size();
		}
		_table[hashi]._state = EXIST;
		_table[hashi]._kv = kv;
		n++;//有效长度加一
	}
private:
	vector<HashData<K, V>>_table;//创建hash表
	size_t n = 0;//记录有效长度
};

第二种二次探测

二次探测与线性探测基本一致，只是线性探测在找空位时依次向后找，而二次探测在找空位时，一次走i的平方。

在这里插入图片描述

2.开散列

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

在这里插入图片描述

在这里插入图片描述

接下来是扩容操作，其实开散表即使不扩容也能正常使用，但如果数据插入过多，会导致桶越来越长，最终变成长链表，导致查找效率降低。所以我们需要引入负载因子来判断何时应该扩容（负载因子计算看与闭散表一致）。

整个扩容需要遍历所有链表，把它们的指针都指向新链表就可以了。

在这里插入图片描述

这里需要补充一点，因为我们的K值不一定都是int类型，所以需要写仿函数来将它转成int，这样才能对应数组下标。

在这里插入图片描述

又因为字符串是我们常用的数据类型，所以我们可以将它进行一个特例化，单独将字符串转化拎出来（字符串转化规则是根据字符串哈希转化规则进行转化的，不明白的可以自行百度）。

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

接下来删除和查找都比较简单，直接看完整源代码。

Hash.h

#include<iostream>
#include<vector>
using namespace std;


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_adress
{
	enum State
	{
		EXIST,
		DELETE,
		EMPTY
	};

	template<class K, class V>
	struct HashData//创建hash表的类型
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V>
	class Hash
	{
	public:
		Hash()
		{
			_table.resize(10);//初始开10给空间
		}

		void insert(const pair<K, V>& kv)
		{
			//判断是否需要扩容
			if (n * 10 / _table.size() >= 7)
			{
				//开一个新的表容量为原来二倍
				size_t newHash = _table.size() * 2;
				Hash<K, V>newHT;
				newHT._table.resize(newHash);

				//将旧表的值插入到新表里
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
						newHT.insert(_table[i]._kv);
				}
				//交换新旧表
				_table.swap(newHT._table);
			}

			//线性探测
			size_t hashi = kv.first % _table.size();//插入位置
			while (_table[hashi]._state == EXIST)//判断应该插入的位置
			{
				hashi++;
				hashi %= _table.size();
			}
			_table[hashi]._state = EXIST;
			_table[hashi]._kv = kv;
			n++;//有效长度加一
		}
	private:
		vector<HashData<K, V>>_table;//创建hash表
		size_t n = 0;//记录有效长度
	};
}



namespace hash_bucket
{
	template<class K,class V>
	struct HashData//创建节点
	{
		HashData<K, V>* next;
		pair<K, V>_kv;
		HashData(const pair<K,V>&kv)
			:next(nullptr)
			,_kv(kv)
		{}
	};


	template<class K,class V,class HashFunc= DefaultHashFunc<K>>
	class Hash
	{
		typedef HashData<K, V> Node;
	public:
		Hash()
		{
			_table.resize(10,nullptr);
		}
		~Hash()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;
				}

				_table[i] = nullptr;
			}
		}
		HashFunc hf;
		bool Insert(const pair<K, V>& kv)
		{
			//如果重复插入返回false
			if (Find(kv.first))
			{
				return false;
			}

			//扩容
			if (_n == _table.size())
			{
				vector<Node*>newTable;
				newTable.resize(_table.size() * 2, nullptr);
				//遍历所有节点
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						size_t hashi = hf(cur->_kv.first) % newTable.size();
						cur->next = newTable[hashi];
						newTable[hashi] = cur;
						cur = cur->next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newTable);
			}


			size_t hashi = hf(kv.first) % _table.size();
			//头插
			Node*newNode = new Node(kv);
			newNode->next = _table[hashi];
			_table[hashi] = newNode;
			_n++;

			return true;
		}

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

		bool Erase(const K& key)
		{
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->next;
					}
					else
					{
						prev->next = cur->next;
					}

					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->next;
			}
			--_n;
			
			return false;
		}

		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->next;
				}
				printf("NULL\n");
			}
			cout << endl;
		}

	private:
		vector<Node*>_table;
		size_t _n = 0;
	};
	
}

test.cpp

int main()
{
	hash_bucket::Hash<int, int> ht;
	int a[] = { 1,111,4,7,15,25,44,9 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}
	ht.Print();

	ht.Insert(make_pair(14, 14));
	ht.Print();

	ht.Insert(make_pair(24, 24));
	ht.Print();

	ht.Insert(make_pair(34, 34));
	ht.Print();

	ht.Erase(44);
	ht.Erase(4);
	ht.Erase(24);
	ht.Print();

	hash_bucket::Hash<string, string> dict;
	dict.Insert(make_pair("sort", "排序"));
	dict.Insert(make_pair("left", "xxx"));
	dict.Insert(make_pair("insert", "插入"));
	dict.Insert(make_pair("string", "字符串"));
	dict.Insert(make_pair("bucket", "桶"));

	auto dret = dict.Find("left");
	//dret->_kv.first = "xx";
	dret->_kv.second = "左边";
	dict.Print();

	return 0;
}
更多推荐

Linux常用命令 - 网络管理与通信命令

网络管理命令ifconfig功能：配置和显示Linux的网络接口和参数。最前面是网卡名。flags里面分别是：UP：表示接口已经启用BROADCAST：表示主机支持广播RUNNING：表示接口在工作中MULTICAST：表示主机支持多播mtu：最大传输单元，1500字节。inet：网卡的IP地址netmask：网络掩码

使用 sklearn 进行数学建模的通用模板

前言无论是本科和研究生都会有的数学建模含金量还是很高的，下面将介绍一下进行数学建模的一些基本操作方法，这里主要是利用sklearn进行建模，包括前期的一些数据预处理以及一些常用的机器学习模型以及一些简单粗暴的通用建模步骤，仅代表我自己意见。一、数学建模常见的问题类型常见的问题类型只有三种：分类、回归、聚类。而明确具体问

数据包络分析（DEA）——CCR模型

写在前面：博主本人大学期间参加数学建模竞赛十多余次，获奖等级均在二等奖以上。为了让更多学生在数学建模这条路上少走弯路，故将数学建模常用数学模型算法汇聚于此专栏，希望能够对要参加数学建模比赛的同学们有所帮助。目录1.模型原理1.1模型介绍1.2数据包络分析的CCR模型1.2.1投入导向的CCR模型1.2.2产出导向的CC

cocosCreator 之 Graphics绘制基础图形，五角星，线型图，柱形图

版本：3.4.0环境：MacGraphics组件Graphics组件主要用于绘画使用，属于渲染组件。继承结构：#mermaid-svg-WHveKVDzMTXmCbpg{font-family:"trebuchetms",verdana,arial,sans-serif;font-size:16px;fill:#333

【数据结构】二叉树的前序遍历（七）

题目：二叉树的前序遍历题目详情：给你二叉树的根节点root，返回它节点值的前序遍历；我们先来看几个示例：输入：root=[1，null，2，3]输出：[1，2，3]示例2：输入：root=[1，2]输出：[1，2]示例三：输入：root=[]输出：[]提示：树中结点数目在范围【0，100】内-100<=Node.val

正则表达式新解

文章目录是什么？正则用法匹配单个字符匹配一组字符其他元字符核心函数贪婪匹配和非贪婪匹配正则练习是什么？正则表达式(RegularExpression)是一种文本模式，包括普通字符（例如，a到z之间的字母）和特殊字符（称为"元字符"），可以用来描述和匹配字符串的特定模式。正则表达式是一种用于模式匹配和搜索文本的工具。正则

go学习之函数知识

函数文章目录函数1.函数入门(1)为什么需要函数？(2)什么是函数：2.包3.函数的调用机制通俗理解调用过程：return语句递归调用4.函数注意事项和细节讨论5.init函数6.匿名函数7.闭包8.defer9.函数参数的传递方式10.字符串中常用的函数11.时间和日期相关的函数12.内置函数13.go的错误处理机制

车载多通道语音识别挑战赛（ICMC-ASR）丨ICASSP2024

由希尔贝壳、理想汽车、西工大音频语音与语言处理研究组、新加坡南洋理工大学、天津大学、WeNet开源社区、微软、中国信通院等单位发起的“车载多通道语音识别挑战赛”（ICMC-ASR）将作为IEEE声学、语音与信号处理国际会议（ICASSP2024）的旗舰赛事，正式启动。报名参加此次赛事，您将获得：业界首个新能源车智能座舱

SpringMvc第六战-【SpringMvcJSON返回&异常处理机制】

前言：小编讲述了：JSR303的概念，应用场景和在具体实例的使用；和拦截器的应用今天小编来讲述的为cJSON返回&异常处理机制，json返回就不用多说，毕竟大部分数据都是通过Json来传递数据的，异常返回的作用小编也就不多说了反正很重要！目录一.SpringMVC之JSON数据返回1.在pom.xml导入Json依赖2

【性能优化下】组织结构同步优化二，全量同步/增量同步，断点续传实现方式

看到这一篇文章的xdm，应该对组织结构同步有一些想法了吧，如果没有，可以看前面两篇文章，可以通过如下地址查看一下：【性能优化上】第三方组织结构同步优化一，你get到了吗？坑爹，线上同步近3w个用户导致链路阻塞引入发的线上问题，你经历过吗？这类文章，主要是期望能给xdm带来不一样的思考，如有表述不当的地方，还请不吝赐教，

Vue的模板语法（下）

一.事件处理事件修饰符Vue通过由点(.)表示的指令后缀来调用修饰符，.stop，.prevent，.capture，.self，.once.stop：阻止事件冒泡。当一个元素触发了事件，并且该元素包含嵌套的父元素时，使用.stop修饰符可以防止事件被传递到祖先元素。.prevent：阻止默认事件。当一个元素上触发了某

热文推荐
  1. 你对Spring Security使用场景以及底层原理有了解吗？

    SpringSecurity使用场景有哪些？SpringSecurity是一个基于Spring框架的安全性解决方案，提供了全面的身份验证、授权和安全功能。它可以应用于多种场景以确保应用程序的安全性和保护敏感资源。以下是一些常见的SpringSecurity的使用场景：用户登录和认证：SpringSecurity可以处理

  2. 在Java开发中无法绕开的框架：SpringBoot

    SpringBoot简介SpringBoot是一个基于Spring框架的快速开发框架，它的出现极大地简化了Spring应用的开发流程。SpringBoot通过自动配置和约定大于配置的方式，让开发者可以快速搭建一个可运行的、独立的、生产级别的应用程序。SpringBoot的优点不仅仅在于它的快速开发，还在于它的可扩展性和

  3. 【校招VIP】前端操作系统之存储管理加密

    考点介绍加密算法有很多，如不可逆的摘要算法MD5、SHA（安全哈希算法），可逆的Base64编码，对称加密算法DES、AES，还有非对称加密算法DH、RSA等。那是不是说明我们可以使用任何一种加密算法就能保证网站的安全性，答案是否。前端操作系统之存储管理加密-相关题目及解析内容可点击文章末尾链接查看！一、考点题目1.下

  4. Linux开发和编程指南：搭建环境、Shell脚本与常见编程语言配置及使用

    文章目录Linux开发和编程Linux上的程序开发环境搭建Shell编程和脚本编写常见编程语言在Linux上的开发环境配置和使用PythonJavaC/C++PHP总结python精品专栏推荐python基础知识（0基础入门）python爬虫知识Linux开发和编程在这篇文章中，我们将介绍如何搭建Linux上的程序开发

  5. MySQL学习系列（5）-每天学习10个知识

    目录1.锁（Locking）和乐观锁与悲观锁2.分布式系统中保证数据一致性3.MySQL的复制延迟问题及解决方法4.索引比全表扫描更快的情况5.分区剪枝（PartitionPruning）6.使用`LIMIT`和`OFFSET`的技巧7.使用`EXPLAIN`语句分析查询性能8.MySQL事务隔离级别9.死锁（Dead

  6. char s[]和char *s的区别，数组和指针的，堆和栈指针的一些思考

    最近在学习的时候看到一个概念，数组不等价于指针，很合理但又很难理解。例如chars[]和char*s有什么区别，前者是数组，后者是指针，个人学习成果如下：1.chars[]和char*s的区别chars[]：①数组，chars[]定义了一个字符数组②内存分配:内存在栈上分配。③大小固定:一旦定义，数组的大小就不能改变。

  7. WMS系统库存分类以优化仓储管理

    1.定义库存分类是指根据一定的规则和标准，将仓库中的货物按照特定的属性、特征或需求进行分类和分组的过程。通过库存分类，可以实现对仓库中货物的有序摆放、快速检索、有效管理和合理分配。2.目的库存分类在WMS系统中的应用具有以下目的：-优化空间利用：通过合理分类，将相似属性的货物放置在一起，最大限度地利用仓库空间，提高仓储

  8. 群狼调研（长沙顾客满意度调查）开展食品安全群众满意度调查

    本文由群狼调研(长沙电信运营商满意度调查)出品，欢迎转载，请注明出处。食品安全群众满意度调查的内容应该涵盖广泛的食品安全领域，从食品产地到生产过程，再到食品标签、监管政策等多个方面。以下是可能包括在食品安全群众满意度调查中的内容：1.食品产地和生产过程：了解公众对食品产地、生产工艺、生产环境等方面的信任程度和满意度。2

  9. 征战MINI学习路线

    征战MINI学习路线征战MINI与ACX720开发板的具体差异1.时钟电路管脚约束一样，仅仅是位号名称不同，ACX720的晶振位号是U2，征战MINI的位号是X1，如下图所示：2.拨码开关电路管脚约束一样，仅仅是位号名称不同，如下图所示：3.EEPROM电路管脚约束一样，仅仅是位号名称不同，如下图所示：4.LED灯电路