【C++】哈希容器

unordered系列关联式容器

        在之前的博文中介绍过关联式容器中的map与set,同map与set一样,unordered_set与unordered_set也是关联式容器。

        在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,查询效率可以达到logN;在C++11中,STL又提供了4个unordered系列的关联式容器,这四个容器与红黑树结构的关联式容器的使用方法类似,但是其底层的实现不同。

        unordered_map与unordered_set的底层实现都是哈希表。unordered关联容器与其他关联容器的区别是:

  • unordered是单项迭代器
  • unordered遍历出来的数据不是有序的
  • unordered_set只能去重。不可以用于排序
  • unordered_map也不可以用于排序
  • 无序数据可以使用unordered关联容器具有优势,有序数据使用其他容器较快。

unordered_map的介绍

unordered_map的文档介绍

std::unordered_map

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

unordered_map的接口说明

unordered_map的构造 

函数说明功能介绍
unordered_map构造不同格式的unordered_map的对象

unordered_map的容量

函数说明功能介绍
bool empty() const noexcept;
检测unordered_map是否为空
size_type size() const noexcept;
获取unordered_map的有效元素个数

unordered_map的迭代器

函数说明功能介绍
begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器
rbegin返回unordered_map第一个元素的const迭代器
rend返回unordered_map最后一个元素下一个位置的const迭代器

unordered_map的元素访问

函数说明功能介绍
operator[]返回与key对应的value,没有一个默认值

【注意】:该函数实际上调用了哈希桶的插入操作,用参数key与value构造一个默认值往底层哈希桶中插入,如果key不在哈希桶中,插入成功,返回value;插入失败,说明key已经在哈希桶值,将key对应的value返回。

unordered_map的查询

函数说明功能介绍
iterator find ( const key_type& k );
返回key在哈希桶中的位置
size_type count ( const key_type& k ) const;
返回哈希桶中关键值为key的键值对的个数

【注意】:unordered_map中的key是不能重复的,因此count函数的返回值最大为1 

unordered_map的修改操作

函数说明功能介绍
insert向容器中插入键值对
erase删除容器中的键值对
clear清空容器中有效元素的个数
swap交换俩个容器中的元素

unordered_map桶操作

函数说明功能介绍

bucket_count

返回哈希桶中的桶的总数

bucket_size

返回n号桶中有效元素的个数

bucket

返回元素key所在的桶号

哈希底层结构

哈希概念

        哈希(散列):存储的值跟存储位置建立出一个对应关系。

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

下面介绍一种方法:哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)或者散列表。

该方法可以不经过任何比较,一次直接从表中得到想要的元素,通过某种函数使元素的存储位置与其关键码之间能够建立一一映射的关系,在查找的时候通过该函数可以很快找到该元素。

插入元素:根据待插入的关键码,以此函数计算出该元素的存储位置并按照此位置进行存放。

搜索元素:对元素的关键码进行同样的计算,把求得的函数值当作元素的存储位置,在结构中按照此位置取元素比较,若关键码相等,则搜索成功。

哈希设计介绍

哈希函数设计原则:

  • 哈希函数的定义域必须包括存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中。

常见哈希函数:

1.直接定址法

取关键字的某个线性函数为散列地址:Hash(key) = A*key + B;

【优点】:简单,均匀

【缺点】:需要事先知道关键字的分布情况

【使用场景】:适合查找范围小,数据集中的情况。

2.除留余数法

设散列表中允许的地址数为m,取一个不大于m,但是最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key)=key%p(p<=m),将关键码转换成哈希地址。



哈希冲突

哈希冲突: 不同关键字通过相同哈希函数计算出相同的哈希地址,这种现象是哈希冲突,也称为哈希碰撞。

解决哈希冲突的俩种常见的方法是:闭散列开散列

闭散列

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

1.线性探测

线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置。

插入方式:

  • 通过哈希函数获取待插入元素在哈希表中的位置
  • 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素。

删除方式:

  • 采用闭散列处理哈希冲突的时候,不能随便物理删除哈希表中已经存在的元素,这样可能会导致影响其他元素的搜索。
  • 可以采用标记的伪删除的方式来删除一个元素
	enum STATE{EXIST,EMPTY,DELETE};

 哈希表的扩容

如果使用开放地址法,可以利用载荷因子:

散列表的载荷因子:a = 填入表中的元素个数 / 散列表的长度

a是散列表装满程度的标志因子,由于散列表的长度是定值,a与“填入表中的元素个数”成正比。

  • 负载因子越大,冲突概率越大,空间利用率更高
  • 负载因子越小,冲突概率越小,空间利用率更低(空间浪费越多)

哈希表不能满了再扩容,控制负载因子再0.7-0.8之间。如果超过0.8,查表时的CPU缓存不命中,按照指数曲线上升。

在扩容之后映射关系需要改变,重新映射,这样也会导致哈希冲突的变化。

线性探测的实现

#include<iostream>
#include<string>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){// BKDRsize_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;};template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}// 扩容//if ((double)_n / (double)_table.size() >= 0.7)if (_n * 10 / _table.size() >= 7){size_t newSize = _table.size() * 2;// 遍历旧表,重新映射到新表HashTable<K, V, HashFunc> newHT;newHT._table.resize(newSize);// 遍历旧表的数据插入到新表即可for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}// 线性探测HashFunc hf;size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size();}_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){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key){return (HashData<const K, V>*) & _table[hashi];}++hashi;hashi %= _table.size();}return nullptr;}// 按需编译bool Erase(const K& key){HashData<const K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}return false;}private:vector<HashData<K, V>> _table;size_t _n = 0; // 存储有效数据的个数};
}

【线性探测的优点】:实现简单

【线性探测的缺点】:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即不同关键码占据了棵利用的空位置,使得寻找某关键码的位置需要多次比较,导致搜索效率低下。

2.二次探测

线性探测的缺点是产生冲突之后,会将数据堆积在一起,这与其找下一个空位置有关系,查找数据需要逐个进行查找,可以使用二次探测解决问题。

二次探测:

找下一个空位置的方法:

hashi = key % n

hashi + i ^2(i为移动的位置)

i>=0

【研究表明】:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任 何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。

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

开散列

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

【说明】开散列使用的是哈希桶,如果不扩容,就会不断插入,某些桶就会越来越长,效率得不到保障,负载因子适当放大,一般负载因子控制到1,平均下来,每一个桶一个数据。

开散列的实现

// 泛型编程:不是针对某种具体类型,针对广泛的类型(两种及以上) -- 模板
namespace hash_bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};// 前置声明template<class K, class T, class KeyOfT, class HashFunc>class HashTable;template<class K, class T, class KeyOfT, class HashFunc>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T, KeyOfT, HashFunc> Self;Node* _node;HashTable<K, T, KeyOfT, HashFunc>* _pht;HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node), _pht(pht){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){if (_node->_next){// 当前桶还没完_node = _node->_next;}else{KeyOfT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();// 从下一个位置查找查找下一个不为空的桶++hashi;while (hashi < _pht->_table.size()){if (_pht->_table[hashi]){_node = _pht->_table[hashi];return *this;}else{++hashi;}}_node = nullptr;}return *this;}bool operator!=(const Self& s){return _node != s._node;}};// set -> hash_bucket::HashTable<K, K> _ht;// map -> hash_bucket::HashTable<K, pair<K, V>> _ht;template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashNode<T> Node;// 友元声明template<class K, class T, class KeyOfT, class HashFunc>friend struct HTIterator;public:typedef HTIterator<K, T, KeyOfT, HashFunc> iterator;iterator begin(){// 找第一个桶for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];if (cur){return iterator(cur, this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}HashTable(){_table.resize(10, nullptr);}~HashTable(){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;}}bool Insert(const T& data){KeyOfT kot;if (Find(kot(data))){return false;}HashFunc hf;// 负载因子到1就扩容if (_n == _table.size()){size_t newSize = _table.size() * 2;vector<Node*> newTable;newTable.resize(newSize, nullptr);// 遍历旧表,顺手牵羊,把节点牵下来挂到新表for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;// 头插到新表size_t hashi = hf(kot(cur->_data)) % newSize;cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashi = hf(kot(data)) % _table.size();// 头插Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return true;}Node* Find(const K& key){HashFunc hf;KeyOfT kot;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){HashFunc hf;KeyOfT kot;size_t hashi = hf(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}--_n;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){cout << cur->_kv.first << ":" << cur->_kv.second << "->";cur = cur->_next;}printf("NULL\n");}cout << endl;}private:vector<Node*> _table; // 指针数组size_t _n = 0; // 存储了多少个有效数据};
}

开散列与闭散列的比较

优先使用开散链的方法。

虽然链地址的方法处理溢出,需要增设链接指针,但是开地址法必须保持大量的空闲空间以确保搜索效率,而表项所占的空间比指针大,所以使用链地址法比开地址法节省空间。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

安装 Terraform for Tencent 使用

第一步 &#xff1a;下载安装包 前往 Terraform 官网&#xff0c;使用命令行直接安装 Terraform 或下载二进制安装文件。 解压并配置全局路径 Linux/MAC&#xff1a;export PATH$PATH:${可执行文件所在目录} 例如&#xff1a;export PATH$PATH:$/usr/bin/terraform Win…

vue2学习 -- 核心语法

文章目录 前置简介1. 模板语法2. 数据2.1 数据绑定2.2 el与data的两种写法2.3 MVVM模型2.4 Object.defineProperty2.5 Vue中的数据代理 3. 事件3.1 事件处理3.2 事件修饰符3.3 键盘事件 4. 计算属性5. 监视(侦听)属性5.1 书写形式5.2 深度监视5.3 简写形式5.4 计算属性和监听属…

Go语言生成excel、将excel保存到本地、将多个excel表格压缩为压缩包、在压缩文件上传OSS删除本地excel文件和压缩包

最近在公司了个需求&#xff0c;主要涉及到文件导出&#xff0c;需要根据特定表格文件生成excel文件导出&#xff0c;同时对导出的excel临时保存本地&#xff0c;生成压缩包&#xff0c;将压缩包上传至OSS&#xff08;Object Storage Service&#xff09;后删除本地临时文件。下…

Go+Redis零基础到用户管理系统API实战_20240730 课程笔记

概述 如果您没有Golang的基础&#xff0c;应该学习如下前置课程。 Golang零基础入门Golang面向对象编程Go Web 基础Go语言开发REST API接口_20240728Go语言操作MySQL开发用户管理系统API教程_20240729Redis零基础快速入门_20231227 基础不好的同学每节课的代码最好配合视频进…

AI绘画模型之:VAE、SD 与 SD-XL

重磅推荐专栏: 《大模型AIGC》 《课程大纲》 《知识星球》 本专栏致力于探索和讨论当今最前沿的技术趋势和应用领域,包括但不限于ChatGPT和Stable Diffusion等。我们将深入研究大型模型的开发和应用,以及与之相关的人工智能生成内容(AIGC)技术。通过深入的技术解析和实践经…

Linux常用工具

文章目录 tar打包命令详解unzip命令&#xff1a;解压zip文件vim操作详解netstat详解df命令详解ps命令详解find命令详解 tar打包命令详解 tar命令做打包操作 当 tar 命令用于打包操作时&#xff0c;该命令的基本格式为&#xff1a; tar [选项] 源文件或目录此命令常用的选项及…

19082 中位特征值

这个问题可以通过深度优先搜索&#xff08;DFS&#xff09;和优先队列来解决。我们首先使用DFS来计算每个节点的特征值&#xff0c;然后我们将所有节点的特征值放入一个优先队列中&#xff0c;然后我们从优先队列中取出中间的元素&#xff0c;这就是我们要找的中位数。 以下是…

如何选择合适的自动化测试工具!

选择合适的自动化测试工具是一个涉及多方面因素的决策过程。以下是一些关键步骤和考虑因素&#xff0c;帮助您做出明智的选择&#xff1a; 一、明确测试需求和目标 测试范围&#xff1a;确定需要自动化的测试类型&#xff08;如单元测试、集成测试、UI测试等&#xff09;和测试…

React-Native 宝藏库大揭秘:精选开源项目与实战代码解析

1. 引言 1.1 React-Native 简介 React-Native 是由 Facebook 开发的一个开源框架&#xff0c;它允许开发者使用 JavaScript 和 React 的编程模型来构建跨平台的移动应用。React-Native 的核心理念是“Learn Once, Write Anywhere”&#xff0c;即学习一次 React 的编程模型&am…

社区养老服务小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;服务人员管理&#xff0c;服务产品管理&#xff0c;服务预约管理&#xff0c;服务状态管理&#xff0c;服务退订管理&#xff0c;活动管理&#xff0c;视频管理 微信端账号功能包…

基于cubeMX的STM32的RTC实时时钟实现

1、在仪器仪表的项目开发中&#xff0c;时常需要设备显示当前的日期和时间&#xff0c;这时&#xff0c;可以使用STM32自带的RTC实时时钟模块来实现此功能。这里我们使用STM32F103RCT6单片机芯片为例。 2、cubeMX的设置 &#xff08;1&#xff09;RTC设置 &#xff08;2&…

民大食堂用餐小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;商家管理&#xff0c;档口号管理&#xff0c;商家餐品管理&#xff0c;餐品种类管理&#xff0c;购物车管理&#xff0c;订单信息管理 微信端账号功能包括&#xff1a;系统首页&a…

yolov10来了!用yolov10训练自己的数据集(原理、训练、部署、应用)

一、引言 YOLOv9还没热乎呢&#xff0c;YOLOv10就出来了&#xff0c;太卷了&#xff01;太快了&#xff01; 自今年2月YOLOv9发布之后&#xff0c; YOLO&#xff08;You Only Look Once&#xff09; 系列的接力棒传到了清华大学研究人员的手上。YOLOv10推出的消息引发了AI界的…

使用 Postman 进行 Trello API 自动化测试的完整指南

文章目录 前言一、自动化测试是什么&#xff1f;二、比较自动化测试与手工测试1. 自动化测试2. 手工测试 三、环境搭建1.创建Collection2.创建环境变量3.添加API请求 四、设计测试用例1. API简单调用2. 获取所有emoji3. 创建一个新看板&#xff1a;4. 获得创建的看板信息5. 在看…

安装nodejs服务器

Java项目可以运行在tomcat服务器&#xff0c;开始完成前后端完全分离。前端有自己独立的工程。我们需要把前端独立的工程运行起来。 运行在nodejs服务器下。 验证是否安装成功&#xff1a;敲cmd--输入node --version 1.安装npm java项目需要依赖jar,安装maven。前端项目也需要依…

Vitis HLS 完美嵌套循环通过 m_axi 接口读取DDR 的迭代次数细粒度控制实验 — 问题描述

1 自媒体账号 目前运营的自媒体账号如下&#xff1a; 哔哩哔哩 【雪天鱼】: 雪天鱼个人主页-bilibili.comCSDN 【雪天鱼】: 雪天鱼-CSDN博客 QQ 学习交流群 FPGA科研硕博交流群 910055563 (进群有一定的学历门槛&#xff0c;长期未发言会被请出群聊&#xff0c;主要交流FPG…

免费!OpenAI发布最新模型GPT-4o mini,取代GPT-3.5,GPT-3.5退出历史舞台?

有个小伙伴问我&#xff0c;GPT-4O mini是什么&#xff0c;当时我还一脸懵逼&#xff0c;便做了一波猜测&#xff1a; 我猜测哈&#xff0c;这个可能是ChatGPT4o的前提下&#xff0c;只支持文本功能的版本&#xff0c;速度更快 结果&#xff0c;大错特错。 让我们一起看看Open…

【简单介绍Gitea】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

吴恩达老师机器学习-ex4

梯度检测没有实现。有借鉴网上的部分 导入相关库&#xff0c;读取数据 因为这次的数据是mat文件&#xff0c;需要使用scipy库中的loadmat进行读取数据。 通过对数据类型的分析&#xff0c;发现是字典类型&#xff0c;查看该字典的键&#xff0c;可以发现又X&#xff0c;y等关…

类和对象【下】

一、类的默认成员函数 默认成员函数从名字就告诉我们何为默认成员函数&#xff0c;即&#xff1a;用户没有实现&#xff0c;编译器默认自动实现的函数。 这时你不禁一喜&#xff0c;还有这好事&#xff0c;编译器给我打工&#xff0c;那么&#xff0c;我们今天都来了解一下都有…