C++ unordered_set和unordered_map

哈希

  • 1. unordered_set/unordered_map
    • 1.1 背景
    • 1.2 unordered_set
      • 1.2.1 特性
      • 1.2.2 常用方法
    • 1.3 unordered_map
      • 1.3.1 特性
      • 1.3.2 常用方法
  • 2. 哈希
    • 2.1概念
    • 2.2 哈希冲突
      • 2.2.1哈希函数
      • 2.2.2 解决哈希冲突
        • 2.2.2.1 闭散列
        • 2.2.2.2 开散列

1. unordered_set/unordered_map

1.1 背景

之前我们不是学习了以红黑树为底层的容器set和map吗，那是C++98提供的关联式容器，而我们今天要学习的unordered_set/unordered_map是在C++11引入的新容器，看名字就知道和set、map的关系匪浅。set、map的查询效率可以达到log2（N），但是在数据很多的时候，效率也不是很理想。所以就引入了这两个容器。那这两个容器能把效率提高多少呢，看完这篇文章就知道了。

1.2 unordered_set

1.2.1 特性

  1. unordered_set（无序集合）是一种不按特定顺序的存储唯一元素，根据关键字可以快速查询到元素的容器。
  2. unordered_set中的存放的元素不能修改，插入和删除是可以的。
  3. 和set相比查询效率高，为常数级，但它通常在遍历元素子集的范围迭代方面效率较低。
  4. 该容器的一些特性和set差不多，可以放在一起比较记忆。

1.2.2 常用方法

unorder_set<string> first容器定义
first.empty()判断容器是否是空，是空返回true，反之为false
first.size()返回容器大小
first.maxsize()返回容器最大尺寸
first.begin()返回迭代器开始
first.end()返回迭代器结束
first.find(value)返回value在迭代器的位置
first.count(key)返回key在容器的个数
first.insert(value)将value插入到容器中
first.erase(key)通过key删除
first.clear()清空容器
在线文档

1.3 unordered_map

1.3.1 特性

  1. unordered_map是一个将key和value关联起来的容器，它可以高效的根据单个key值查找对应的value。
  2. key值应该是唯一的，key和value的数据类型可以不相同。
  3. unordered_map存储元素时是没有顺序的，只是根据key的哈希值，将元素存在指定位置，所以根据key查找单个value时非常高效，平均可以在常数时间内完成。
  4. unordered_map查询单个key的时候效率比map高，但是要查询某一范围内的key值时比map效率低。
  5. 可以使用[]操作符来访问key值对应的value值。

1.3.2 常用方法

insert()：插入数据。
erase()：删除数据。
find()：查找数据。
clear()：数据的清空。
empty()：数据的判空。
size()：获取有效元素的大小。
count()：获取键值中查找元素的个数。如果有返回1，否则返回0。
rbegin()：在反向迭代器中表示起始元素。
rend()：在反向迭代器中表示末尾元素。
operator[key]：通过键值（key）获取该key对应的value。

2. 哈希

2.1概念

在前面学习过的数据结构中，存放的关键值和存储的位置没有任何关联，所以查找一个元素必须要经过多次的比较才能得到该元素。那么有没有一种方法可以实现元素之间不用比较也能查找到该元素呢？哈希的思想就引入进来了。

插入操作：
       在往该结构中插入元素时，通过关键码和一个函数，计算出存放该元素的位置。

查找操作：
       怎么放进去的就怎么找出来，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

几个名词：

  1. 哈希函数（散列函数）（将关键码转换成位置的方法）
  2. 哈希表（散列表）（使用上述方法构造出来的结构）

一个例子：
数据{1，9，16，10，8，0}
哈希函数 hash(key) = key % 10;
在这里插入图片描述
相信大家看了这个例子，可以体会到哈希的妙，但这出现了一个问题，两个元素映射到了同一个地方，这种情况叫哈希冲突，解决该问题也是我们研究的一个重要问题。

2.2 哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

2.2.1哈希函数

产生这种情况的原因可能是哈希函数设计的不够合理。

设计原则：

  1. 形式简单
  2. 计算出来的结果分布均匀
  3. 哈希函数的定义域必须包括需要存储的全部关键码

一些常见哈希函数

  1. 直接定址法–(常用)
    取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况
  2. 除留余数法–(常用)
    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key%
    p(p<=m),将关键码转换成哈希地址
  3. 平方取中法–(了解)
    假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
    平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
  4. 折叠法–(了解)
    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这 几部分叠加求和，并按散列表表长，取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
  5. 随机数法–(了解)
    选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。 通常应用于关键字长度不等时采用此法
  6. 数学分析法–(了解)
    设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址、

2.2.2 解决哈希冲突

解决该冲突常见的两种方法是开散列和闭散列。

2.2.2.1 闭散列
  1. 线性探测：如果发现插入元素的位置已经有元素了，那就依次往后找空位放进去，比如上述例子的0元素应该放在2位置上。

插入操作：
       通过哈希函数计算出位置，如果该位置为空则放进去，否则依次往后。
查找操作：
       通过哈希函数计算出位置，比对值是否一样，如果一样就查找成功，如果碰到空则证明没有该元素（因为元素是依次往后探测的，不可能留空隙，所以遇到空就证明没有该元素）。
删除操作：
       不能随便的物理删除一个元素，不然会影响查找操作，比如现在有一个场景：你删除了一个元素，然后要查找的元素在你删除元素的后面，根据上面的查找规则，你是查不到这个元素的。所以我们采取了标志位的方法来删除元素，删除一个元素就是简单的把该元素的标志位改为已删除。

代码实现：

enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY; // 标记
	};

//将关键字转化成无符号整型，这样才能进行取余操作
	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 hash = 0;
			for (auto e : s)
			{
				hash += e;
				hash *= 131;
			}

			return hash;
		}
	};


	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable(size_t size = 10)
		{
			_tables.resize(size);
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hs;
			// 线性探测
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (key == _tables[hashi]._kv.first
					&& _tables[hashi]._state == EXIST)
				{
					return &_tables[hashi];
				}

				++hashi;
				hashi %= _tables.size();
			}

			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//哈希表应满足元素个数和空间的比率，	
			//如果 ((double)_n / (double)_tables.size() >= 0.7)就该扩容了。
			if (_n * 10 / _tables.size() >= 7)
			{

				HashTable<K, V, Hash> newHT(_tables.size() * 2);
				// 遍历旧表，插入到新表
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			Hash hs;
			// 线性探测
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size();
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				_n--;
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}

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

使用这种方式解决冲突虽然很简单，但是如果冲突验证，那么查询的效率会降低很多。

2.2.2.2 开散列

开散列法又叫链地址法(开链法)，将冲突的元素通过链表链接起来，将链表的头保存在哈希表中，每个链表也叫桶。
还是上面的例子，用开散列法看看
在这里插入图片描述
这种结构的插入、删除、查找操作就是链表的基本操作，这里我们就不多说了，直接看代码。

//将关键字映射成整型
	template<class K>
	struct HashFunC
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//模版特化，string常作为key
	template<>
	struct HashFunC<string>
	{
		//将字符串每个字母的ASCII乘一个系数然后累加
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (char c : key)
			{
				hash += c;
				hash *= 131;
			}

			return hash;
		}
	};
	
	template<class K,class V>
	struct HashBucketNode
	{
		HashBucketNode(const pair<K,V>& value)
			:_value(value)
			,next(nullptr)
		{}
		pair<K, V> _value;
		HashBucketNode<K, V>* next;
	};

	template<class K,class V,class Hash = HashFunC<K>>
	class HashBucket
	{
		typedef struct HashBucketNode<K,V> Node;
	public:
		HashBucket(size_t size = 10)
			:_table(size,nullptr)
			,_size(0)
		{}
		~HashBucket()
		{
			Clear();
		}
		// 哈希桶中的元素不能重复
		Node* Insert(const pair<K, V>& value)
		{
			if (!Find(value.first))
			{
				CheckCapacity();
				size_t hashi = HashFunc(value.first);
				//头插
				Node* newnode = new Node(value);
				newnode->next = _table[hashi];
				_table[hashi] = newnode;
				_size++;
				return newnode;
			}
		}

		// 删除哈希桶中为data的元素(data不会重复)
		bool Erase(const K& key)
		{
			if (Find(key))
			{
				size_t hashi = HashFunc(key);
				Node* pre = nullptr;
				Node* cur = _table[hashi];
				while (cur)
				{
					if (cur->_value.first == key)
					{
						//头删单独处理
						if (!pre)
							_table[hashi] = cur->next;
						else
						pre->next = cur->next;
						delete cur;
						_size--;
						return true;
					}
					pre = cur;
					cur = cur->next;
				}
			}
			return false;
		}

		Node* Find(const K& key)
		{
			size_t hashi = HashFunc(key);
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_value.first == key)
					return cur;
				cur = cur->next;
			}

			return nullptr;
		}
		void Swap(HashBucket<K,V,Hash>& ht)
		{
			_table.swap(ht._table);
			swap(_size, ht._size);
		}
		void Clear()
		{
			for (auto& e : _table)
			{
				if (e)
				{
					Node* cur = e;
					while (cur)
					{
						Node* next = cur->next;
						delete cur;
						cur = next;
					}
					e = nullptr;
				}
			}
		}

		size_t Size()const
		{
			return _size;
		}

		bool Empty()const
		{
			return 0 == _size;
		}
	private:
		size_t HashFunc(const K& key)
		{
			Hash hash;
			return hash(key) % _table.size();
		}
		void CheckCapacity()
		{
			//当装填因子为1
			if (_size == _table.size())
			{
				HashBucket<K, V,Hash> newHashBucket(_table.size() * 2);
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while(cur)
					{
						Node* next = cur->next;
						newHashBucket.Insert(cur->_value);
						cur = next;
					}
				}
				Swap(newHashBucket);
			}
		}

	private:
		vector<Node*> _table;
		size_t _size;
	};

在这里插入图片描述

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

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

相关文章

Rust并发编程thread多线程和channel消息传递

Rust并发编程thread多线程和channel消息传递

安全高效的处理并发是 Rust 诞生的目的之一&#xff0c;主要解决的是服务器高负载承受能力。 并发&#xff08;concurrent&#xff09;的概念是指程序不同的部分独立执行&#xff0c;这与并行&#xff08;parallel&#xff09;的概念容易混淆&#xff0c;并行强调的是"同…
阅读更多...
如何理解OSI七层模型?

如何理解OSI七层模型?

一、是什么 OSI &#xff08;Open System Interconnect&#xff09;模型全称为开放式通信系统互连参考模型&#xff0c;是国际标准化组织 ( ISO ) 提出的一个试图使各种计算机在世界范围内互连为网络的标准框架 OSI将计算机网络体系结构划分为七层&#xff0c;每一层实现各自…
阅读更多...
存储随笔原创科普视频首播～

存储随笔原创科普视频首播～

一周之前&#xff0c;存储随笔创建了B站账号。小编利用上个周末休息时间专门研究了B站视频录制的各种方案。发现并没有想象的很容易&#xff0c;先花了很长时间准备了一个PPT&#xff0c;再准备演讲大纲&#xff0c;最终磕磕绊绊完成了首期原创视频录制&#xff01; 可能不尽如…
阅读更多...
PCB布线中晶振电容、电源大小电容、电源电容的设计细节

PCB布线中晶振电容、电源大小电容、电源电容的设计细节

嵌入式软硬件爱好者 一张手册走天下。嵌入式单片机/Linux/Openwrt/电子电路技术交流分享。//主打一个技术层面的剑走偏锋&#xff0c;直击众人重视和不重视的重点//专注基础&#xff0c;才能走的更远 晶振电容 晶振旁边的电容在电路设计中不是用于滤波的。实际上&#xff0c;…
阅读更多...
中国疆域从古至今版图演变，中国历史各个朝代地图大全

中国疆域从古至今版图演变，中国历史各个朝代地图大全

一、图片描述 每个朝代都有数十张地图&#xff0c;朝代疆域全图重点区域地图&#xff0c;图片是JPG格式&#xff0c;都是高清地图&#xff0c;行政名称清晰可见&#xff0c;非常适合喜欢历史的朋友。本套历史朝代地图&#xff0c;大小1.32G&#xff0c;18个压缩文件。 二、图…
阅读更多...
ShardingSphere水平分表——开发经验（2）

ShardingSphere水平分表——开发经验（2）

1. 什么场景下分表&#xff1f; 数据量过大或者数据库表对应的磁盘文件过大。 Q&#xff1a;多少数据分表&#xff1f; A&#xff1a;网上有人说1kw&#xff0c;2kw&#xff1f;不准确。 1、一般看字段的数量&#xff0c;有没有包含text类型的字段。我们的主表里面是不允许有t…
阅读更多...
C语言数据结构之归并排序

C语言数据结构之归并排序

疏雨池塘见 微风襟袖知 目录 归并排序的介绍 基本思想 时间复杂度分析 ⭐归并排序步骤 空间复杂度分析 代码展示 ✨归并排序的非递归 代码展示 总结&#x1f525; 归并排序的介绍 归并排序&#xff0c;是创建在归并操作上的一种有效的排序算法。算法是采用分治法&#xff…
阅读更多...
项目1-加法计算器

项目1-加法计算器

1.创建项目 2.导入前端代码 2.1 static包内 2.2 测试前端代码是否有误 显示成功说明无误 2.3 定义用户接口 请求路径&#xff1a;calc/sum 请求方式&#xff1a;GET/POST 接口描述&#xff1a;计算两个整数相加 请求参数: 参数名类型是否必须备注num1Integer是参与计算的第…
阅读更多...
瑞萨杯(一)

瑞萨杯(一)

基础信息 RA6M5&#xff1a;ARM V8架构&#xff0c;24MHz外置晶振&#xff0c;200MHz主频 SCI&#xff08;Serial Communications Interface&#xff09;&#xff0c;意为串行通信接口 参考链接&#xff1a; 【瑞萨RA系列FSP库开发】RASCKeil的环境搭建_瑞萨ra mdk-CSDN博客…
阅读更多...
主干网络篇 | YOLOv8改进之在主干网络中引入密集连接卷积网络DenseNet

主干网络篇 | YOLOv8改进之在主干网络中引入密集连接卷积网络DenseNet

前言：Hello大家好，我是小哥谈。DenseNet（密集连接卷积网络）是一种深度学习神经网络架构，它在2017年由Gao Huang等人提出。DenseNet的核心思想是通过密集连接（dense connection）来促进信息的流动和共享。在传统的卷积神经网络中，每个层的输入只来自于前一层的输出。而在…
阅读更多...
C语言之strsep用法实例(八十六)

C语言之strsep用法实例(八十六)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…
阅读更多...
【Python音视频技术】Python音视频技术系列文章2---视频提取音频转换文字

【Python音视频技术】Python音视频技术系列文章2---视频提取音频转换文字

接上一篇文章 【Python音视频技术】玩AI视频创作引发写Python音视频技术系列文章1---视频添加字幕 之前我想在视频中提取音频转换文字&#xff0c; 当时是用 PC剪映专业版搞定的&#xff0c; 详情见 【AI应用】模仿爆款视频二次创作短视频操作步骤 。 这里我准备用pytho…
阅读更多...
铁道障碍物检测6种YOLOV8

铁道障碍物检测6种YOLOV8

铁道障碍物检测6种&#xff0c;采用YOLOV8训练&#xff0c;得到PT模型&#xff0c;然后转换成ONNX模型&#xff0c;OPENCV调用 铁道障碍物检测6种YOLOV8
阅读更多...
android Fragment 生命周期 方法调用顺序

android Fragment 生命周期 方法调用顺序

文章目录 Introlog 及结论代码 Intro 界面设计&#xff1a;点击左侧按钮&#xff0c;会将右侧 青色的RightFragment 替换成 黄色的AnotherRightFragment&#xff0c;而这两个 Fragment 的生命周期方法都会打印日志。 所以只要看执行结果中的日志&#xff0c;就可以知道 Fragme…
阅读更多...
Linux 系统 快速卸载docker

Linux 系统 快速卸载docker

(卸载前一定要做好相关数据的备份) 卸载&#xff1a; 第一种卸载方法 1、查询docker安装过的包&#xff1a; yum list installed | grep docker 2、删除安装包&#xff1a; yum remove docker-ce.x86_64 ddocker-ce-cli.x86_64 -y 3、删除镜像/容器等 rm -rf /var/lib/dock…
阅读更多...
IT运维服务规范标准与实施细则

IT运维服务规范标准与实施细则

一、 总则 本部分规定了 IT 运维服务支撑系统的应用需求&#xff0c;包括 IT 运维服务模型与模式、 IT 运维服务管理体系、以及 IT 运维服务和管理能力评估与提升途径。 二、 参考标准 下列文件中的条款通过本部分的引用而成为本部分的条款。凡是注日期的引用文件&#xff0c…
阅读更多...
基于QT的实现的人脸识别、人脸标记、人脸比对

基于QT的实现的人脸识别、人脸标记、人脸比对

该项目使用的人脸模型框架采用的是seetaface开源版本&#xff0c;经过测试发现效果还算可以。 人脸识别的效果图如下: 人脸比对的效果图如下&#xff1a; 鉴于测试识别的精度特意找了不同两人相似的人脸进行比对&#xff0c;效果如下图&#xff1a; 由于该模型采用的阈值是0.6…
阅读更多...
前端框架前置课（1）---AJAX阶段

前端框架前置课（1）---AJAX阶段

1. AJAX入门 1.1 AJAX概念和axios使用 1.1.1 什么是AJAX? 1.1.2 怎么用AJAX? 引入axios.js 获取省份列表数据 1.2 认识URL 1.3 URL查询参数 1.4 常用请求方和数据提交 1.5 HTTP协议-报文 1.5.1 HTTP响应状态码 1.5.1.1 状态码&#xff1a;1XX&#xff08;信息&#xff09…
阅读更多...
vulhub中Apache Shiro 认证绕过漏洞复现（CVE-2020-1957）

vulhub中Apache Shiro 认证绕过漏洞复现（CVE-2020-1957）

Apache Shiro是一款开源安全框架&#xff0c;提供身份验证、授权、密码学和会话管理。Shiro框架直观、易用&#xff0c;同时也能提供健壮的安全性。 在Apache Shiro 1.5.2以前的版本中&#xff0c;在使用Spring动态控制器时&#xff0c;攻击者通过构造..;这样的跳转&#xff0…
阅读更多...
Oracle等待事件-db file parallel read

Oracle等待事件-db file parallel read

前面两篇聊了Oracle等待事件-db file scattered read和Oracle等待事件-db file sequential read 相比于前两者等待事件只有读，但是到db file parallel 就有db file parallel read 和 db file parallel write db file parallel read是指当进程并行发出多个 I/O 请求以将数据…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站