C++进阶:哈希(1)

目录

  • 1. 简介unordered_set与unordered_map
  • 2. 哈希表(散列)
    • 2.1 哈希表的引入
    • 2.2 闭散列的除留余数法
      • 2.2.1 前置知识补充与描述
      • 2.2.2 闭散列哈希表实现
    • 2.3 开散列的哈希桶
      • 2.3.1 结构描述
      • 2.3.2 开散列哈希桶实现
      • 2.3.3 哈希桶的迭代器与key值处理仿函数
  • 3. unordered_set与unordered_map的封装
    • 3.1 哈希桶的细节调整
    • 3.2 具体封装

1. 简介unordered_set与unordered_map

  1. 在C++库中,除开map与set这两个关联式容器外,还存在着另外两个此类容器,unordered_set,unordered_map。
  2. unordered中文释义为无序的,这也正是这一对容器使用时的表征特点,这一对容器分别对应set与map,即K模型与KV模型的存储数据结点。
  3. 那么,除开使用迭代器遍历时,其内存储数据无序外,这一对容器与map与set容器有何不同,为什么要在已有map与set的情况下,再向库中加入这一对乍看功能冗余且劣于原本map与set的容器呢?我们来看下面的一组对照试验。
  4. unordered_set与unordered_map其的关键性常用接口与使用和map,set相同,不同的是其只支持正向迭代器且多了一些桶,负载因子相关的接口。
#include <iostream>
using namespace std;
#include <unordered_set>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <vector>int main()
{const int N = 1000000;vector<int> data(N);set<int> s;unordered_set<int> us;srand((unsigned int)time(NULL));for (int i = 0; i < N; i++){//data.push_back(rand());//重复数据多//data.push_back(rand() + i);//重复数据少data.push_back(i);//有序数据}//插入int begin1 = clock();for (auto e : data){s.insert(e);}int end1 = clock();int begin2 = clock();for (auto e : data){us.insert(e);}int end2 = clock();cout << "insert number:" << s.size() << endl << endl;//查找int begin3 = clock();for (auto e : data){s.find(e);}int end3 = clock();int begin4 = clock();for (auto e : data){us.find(e);}int end4 = clock();int begin5 = clock();for (auto e : data){s.erase(e);}int end5 = clock();int begin6 = clock();for (auto e : data){us.erase(e);}int end6 = clock();cout << "set Insert:" << end1 - begin1 << endl;cout << "unordered Insert:" << end2 - begin2 << endl << endl;cout << "set Find:" << end3 - begin3 << endl;cout << "unordered Find:" << end4 - begin4 << endl << endl;cout << "set Erase:" << end5 - begin5 << endl;cout << "unordered Erase:" << end6 - begin6 << endl << endl;return 0;
}

运行结果:
在这里插入图片描述

  1. 由运行结果可得
    <1> 当数据无序时在重复数据较多的情况下,unordered系列的容器,插入删除效率更高
    <2> 当数据无序但重复数据较少的情况下,两种类型的容器,两者插入数据效率仿佛
    <3> 当数据有序时,红黑树系列的容器插入效率更高
  2. 在日常的应用场景中,很少出现有序数据情况,虽然map,set有着遍历自得有序这一优势,但关联式容器的主要功能为映射关系与快速查询,其他优点尽是附带优势。所以,unordered系列容器的加入与学习是必要的。

2. 哈希表(散列)

2.1 哈希表的引入

  1. 在初阶数据结构的学习中,我们学习了一种排序方式,叫做基数排序,其使用数组下标表示需排序数据,下标对应的元素代表相应数据的出现次数。以此映射数据并排序,时间复杂度只有O(n)。
  2. 基数排序创建的数据存储数组,除可以用于数据排序外,我们不难发现其用来查询一个数据在或不再,可以通过访问下标对应数据直接得到,查询效率及其高。
  3. 这一为排序所创建的存储数组,就是一个简单的哈希表,我们也称之为散列,即数据并非连续而是散列在一段连续的空间中。
  4. 哈希表中的哈希,是指一种数据结构的设计思想,为通过某种映射关系为存储数据创建一个key值,其的映射关系不一,但都可以通过key值找到唯一对应的一个数据,且使得数据散列在存储空间中。
  5. 上述的存储结构为常见哈希表结构的一种,我们称之为直接定址法哈希表,但此种哈希表其使用上存在诸多限制,当存储数据的范围跨度较大时,就会使得空间浪费十分严重。接下来,我们来学习几种在其基础上进行优化具有实用价值的常用哈希表结构。

2.2 闭散列的除留余数法

2.2.1 前置知识补充与描述

  1. 除留余数法:为了解决存储数据大小范围跨度过大的问题,我们不再直接使用存储数据左key值映射,而是通过存储数据除以哈希表大小得到的余数做key值。这样就能将所有数据集中映射至一块指定大小的空间中。
  2. 哈希冲突/哈希碰撞:取余数做key值的方式虽然能够使得数据映射到一块指定空间中,并大幅度减少空间的浪费,可是这也会产生一个无法避免的问题,那就是不同数据的经过取余得到的余数可能相同,如此就会导致同一key值映射多个数据,使得无法进行需要的存储与查询。这一问题就被称为哈希碰撞。
  3. 线性探测与二次探测:哈希碰撞的解决存在多种方法策略,这里我们简单了解两种常用方式
    <1> 线性探测:当前key值对应数据位被占用时,向后遍历(hashi + i),直至找到为空的数据位再将数据存入,而探测查询时,也以线性逻辑搜索直至遍历至空,则代表查询数据不存在,越界回绕
    <2> 二次探测:当前key指对数据位被占用时,当前key值依次加正整数的平方(hashi + i 2 i^2 i2)直至遍历至空存入,探测查询时,依次逻辑或至空结束,越界回绕。
  4. 补充:
    <1> 负载因子:哈希表中存储数据个数与哈希表长度的比值,一般控制在0.7左右,若负载因子超过,进行扩容
    <2> 线性探测容易导致数据的拥堵与踩踏,二次探测的方式为对此的优化
    <3> 处理非数字类型数据,将其转换为size_t类型后,再进行key值映射,采用仿函数的方式

在这里插入图片描述

2.2.2 闭散列哈希表实现

  1. 哈希表结构
//结点状态
enum State
{EMPTY,//可插入,查询结束EXIST,//不可插入,向后查询DELETE//可插入,向后查询
};//数据结点
template<class K, class V>
struct HashNode
{pair<K, V> _kv;State _state;HashNode(const pair<K, V>& kv = make_pair(K(), V())):_kv(kv),_state(EMPTY){}
};//哈希表
template<class K, class V, class hash = HashFunc<K>>
class HashTable
{typedef HashNode<K, V> HashNode;typedef Hash_iterator<K, V, hash> iterator;
public:HashTable(size_t n = 10){_table.resize(n);}//迭代器相关iterator begin();iterator end();	//查找HashNode* Find(const K key);//插入bool Insert(const pair<K, V>& kv);//删除bool Erase(const K key);private:vector<HashNode> _table;//结点size_t n = 0;//存储数据个数hash hs;//仿函数,处理key值
};
  1. 操作实现
//查找
HashNode* Find(const K key)
{int hashi = hs(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST && hs(_table[hashi]._kv.first) == hs(key)){return &_table[hashi];}hashi++;hashi %= _table.size();}return nullptr;
}//插入
bool Insert(const pair<K, V>& kv)
{//扩容,类型转换//重新建立映射关系,插入(现代写法)if ((double)n / (double)_table.size() >= 0.7){HashTable<K, V, hash> newtable(_table.size() * 2);//迭代器for (auto& e : _table){newtable.Insert(e._kv);}_table.swap(newtable._table);}//找到要插入的位置int hashi = hs(kv.first) % _table.size();//线性探测while (_table[hashi]._state == EXIST){if (_table[hashi]._kv.first == kv.first){return false;}//可能越界,需要回绕hashi++;hashi %= _table.size();}//插入,单参数的构造函数支持隐式类型转换_table[hashi] = kv;_table[hashi]._state = EXIST;n++;return true;
}//删除
bool Erase(const K key)
{//将要删除结点的状态改为deleteint hashi = key % _table.size();//复用findHashNode* ret = Find(key);if (ret){ret->_state = DELETE;n--;return true;}else{return false;}
}
  1. 迭代器相关接口
iterator begin()
{for (size_t i = 0; i < _table.size(); i++){HashNode* cur = _table[i];if (cur){return iterator(cur, this);}}return end();//补
}iterator end()
{return iterator(nullptr, this);
}
  1. key指出,类型转换仿函数
//仿函数
template<class K>//数字类型
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//string类型全特化,常用
template<>
struct HashFunc<string>
{size_t operator()(string str){size_t key = 0;for (auto e : str){key += e;key *= 131;}return key;}
};//其他类型,自定义类型
struct Date
{int _year;int _month;int _day;
};struct HashDate
{size_t operator()(const Date& d){size_t key = 0;key += d._day;key *= 131;//科学建议值key += d._month;key *= 131;key += d._year;key *= 131;return key;}
};struct Person
{int name;int id;//有唯一项用唯一项,无唯一项,乘权值拼接int add;int tel;int sex;
};

2.3 开散列的哈希桶

2.3.1 结构描述

在这里插入图片描述

  1. 除留余数法后线性探测的存储方式会导致数据的拥堵踩踏,随着数据存储数量的增加,踩踏与拥挤的现象会越来越频繁,二次探测的优化也仅仅只是饮鸩止渴。
  2. 由此,我们来学习一种新的哈希结构也是使用最广泛的一种,其存储方式为:
    顺序表中存储链表指针,相同key值的数据构造成链表结构的数据结点,挂入同一链表中,此种数据结构就被称为哈希桶

2.3.2 开散列哈希桶实现

  1. 哈希桶结构
//数据结点
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, hash> HashNode;
public://构造HashTable(size_t n = 10){_table.resize(n, nullptr);_n = 0;}//析构~HashTable(){for (size_t i = 0; i < _table.size(); i++){HashNode* cur = _table[i];while (cur){HashNode* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}private:vector<HashNode*> _table;size_t _n;//插入数据个数,计算负载因子与扩容hash hs;//非数字类型,key值处理friend struct iterator;//迭代器会需要访问存储数据的vector
};
  1. 操作实现
//插入
bool Insert(const pair<K, V>& kv)
{//不支持键值冗余if (Find(kv.first))return false;//何时扩容,负载因子到1就扩容,插入数据个数if (_n == _table.size()){vector<HashNode*> newtable(2 * _table.size());//不再重新申请创建结点,而是搬运for (size_t i = 0; i < _table.size(); i++){HashNode* cur = _table[i];while (cur){HashNode* next = cur->_next;size_t hashi = hs(cur->_kv.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}//计算插入位置size_t hashi = hs(kv.first) % _table.size();//头插HashNode* newnode = new HashNode(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return true;
}//查找
HashNode* Find(const K& key)
{for (size_t i = 0; i < _table.size(); i++){HashNode* cur = _table[i];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}}return nullptr;
}//删除
bool Erase(const K& key)
{size_t hashi = hs(key) % _table.size();HashNode* cur = _table[hashi];HashNode* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev){prev->_next = cur->_next;}else{_table[hashi] = cur->_next;}delete cur;_n--;return true;}prev = cur;cur = cur->_next;}return false;
}

2.3.3 哈希桶的迭代器与key值处理仿函数

  1. 迭代器结构
//将迭代器代码写于哈希桶之前
//迭代器与哈希桶存在互相引用,添加前置声明
template<class K, class V, class hash>
class HashTable;template<class K, class V, class hash = HashFunc<K>>
struct Hash_iterator
{typedef HashNode<K, V> HN;typedef HashTable<K, V, hash> HT;typedef Hash_iterator Self;HN* _node;HT* _ht;hash hs;Hash_iterator(HN* node, HT* ht):_node(node),_ht(ht){}//前置++Self& operator++();V& operator*();pair<K, V>* operator->();bool operator!=(const Self& it);};
  1. 操作实现
//前置++
Self& operator++()
{if (_node->_next){_node = _node->_next;}else{size_t hashi = hs(_node->_kv.first) % _ht->_table.size() + 1;_node = nullptr;//注while (hashi < _ht->_table.size()){if (_ht->_table[hashi]){_node = _ht->_table[hashi];break;}hashi++;}//后续没有元素,越界//_node = _ht->_table[hashi];}return *this;
}V& operator*()
{return _node->_kv.second;
}pair<K, V>* operator->()
{return &_node->_kv;
}bool operator!=(const Self& it)
{return _node != it._node;
}
  1. 缺省的key值处理仿函数
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//特化,常用string类型
template<>
struct HashFunc<string>
{size_t operator()(const string& str){size_t key = 0;for (auto e : str){key += e;key *= 131;}return key;}
};

3. unordered_set与unordered_map的封装

3.1 哈希桶的细节调整

  1. 使用哈希桶unordered_set与unordered_map的封装方式与红黑树封装map,set相似,调整模板参数,使得仅用一套模板即可封装出u_map与u_set,具体操作如下:
  1. 数据结点结构的调整
template <class T>//改
struct HashNode
{T _kv;HashNode<T>* _next;HashNode(const T& kv):_kv(kv),_next(nullptr){}
};
  1. 迭代器结构的调整
template<class K, class T, class KeyOfT, class hash = HashFunc<K>>
struct Hash_iterator
{typedef HashNode<T> HN;typedef HashTable<K, T, KeyOfT, hash> HT;typedef Hash_iterator Self;HN* _node;HT* _ht;hash hs;KeyOfT kot;//其后细节随之调整	
};
  1. 哈希桶结构的调整
//将hash模板参数的缺省值提维
template <class K, class T, class KeyOfT, class hash>
class HashTable
{typedef HashNode<T> HashNode;typedef Hash_iterator<K, T, KeyOfT, hash> iterator;
private:vector<HashNode*> _table;size_t _n;hash hs;KeyOfT kot;friend struct iterator;	public://其他内部方法细节随之调整//为适配上层unordered_map的operator[],返回值与实现细节做调整pair<iterator, bool> Insert(const T& kv);iterator Find(const K& key);
};

3.2 具体封装

  1. unordered_set
//缺省提维的原因
//并非直接使用哈希桶,而是通过us,um来间接使用**
template<class K, class hash = HashFunc<K>>
class myordered_set
{struct KeyOfT{K operator()(const K& key){return key;}};typedef Hash_iterator<K, K, KeyOfT, hash> iterator;typedef HashNode<K> HashNode;
public:iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> Insert(const K& key){return _ht.Insert(key);}iterator Find(const K& key){return _ht.Find(key);}bool Erase(const K& key){return _ht.Erase(key);}
private:HashTable<K, K, KeyOfT, hash> _ht;
};
  1. unordered_map
template<class K, class V, class hash = HashFunc<K>>
class myordered_map
{struct KeyOfT{K operator()(const pair<K, V>& kv){return kv.first;}};typedef Hash_iterator<K, pair<K, V>, KeyOfT, hash> iterator;typedef HashNode<pair<K, V>> HashNode;
public:iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> Insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator Find(const K& key){return _ht.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key, V()));return (ret.first)->second;}bool Erase(const K& key){return _ht.Erase(key);}private:HashTable<K, pair<K, V>, KeyOfT, hash> _ht;
};

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

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

相关文章

Spring框架概述

目录 1. Spring框架的起源 2. Spring框架的构成 3. Spring的发展历程 4. Spring的开发环境 4.1. Maven安装与配置 &#xff08;1&#xff09;Maven的下载与安装 &#xff08;2&#xff09;配置Maven的环境变量 &#xff08;3&#xff09;本地仓库的配置 &#xff08;4…

WIFI模块的AT指令联网数据交互--第十天

1.1.蓝牙&#xff0c;ESP-01s&#xff0c;Zigbee, NB-Iot等通信模块都是基于AT指令的设计 初始配置和验证 ESP-01s出厂波特率正常是115200, 注意&#xff1a;AT指令&#xff0c;控制类都要加回车&#xff0c;数据传输时不加回车 1.2.上电后&#xff0c;通过串口输出一串系统…

如何使用dockerfile文件将项目打包成镜像

要根据Dockerfile文件来打包一个Docker镜像&#xff0c;你需要遵循以下步骤。这里假设你已经安装了Docker环境。 1. 准备Dockerfile 确保你的Dockerfile文件已经准备就绪&#xff0c;并且位于你希望构建上下文的目录中。Dockerfile是一个文本文件&#xff0c;包含了用户可以调…

绘制一个单级放大电路原理图过程,保姆级教程

新手在学习pads的使用最好最快的方法就是实际上手去画原理图&#xff0c;画PCB图&#xff0c;在这个过程中&#xff0c;就能够更快速得掌握PADS软件的使用。 本篇就是对于实际画原理图过程的一个记录&#xff0c;手把手教学&#xff0c;如果有纰漏或者有更好的一些技巧&#xf…

thinkphp6使用layui分页组件做分页效果

博主用的是layui2.9.8的版本&#xff0c;但这个版本的分页组件是动态效果的&#xff0c;但我需要的是静态分页&#xff0c;所以我自己封装了一个生成layui的分页代码生成代码。代码如下&#xff1a; 1、先创建文件&#xff0c;路径是extent/layui/LayuiPage.php&#xff0c;加…

R语言:GSEA分析

#安装软件包 > if (!requireNamespace("BiocManager", quietly TRUE)) install.packages("BiocManager") > BiocManager::install("limma") > BiocManager::install("org.Hs.eg.db") > BiocManager::install("…

检测服务器环境,实现快速部署。适用于CRMEB_PRO/多店

运行效果如图&#xff1a; 最近被好多人问&#xff0c;本来运行的好好的&#xff0c;突然swoole就启动不了了。 本工具为爱发电&#xff0c;如果工具正好解决了您的需求。我会很开心 代码如下&#xff1a; """本脚本为爱发电by:网前雨刮器 """…

四川汇昌联信:拼多多网点怎么开?大概需要多少钱?

想要开一家拼多多网点&#xff0c;你肯定很关心需要准备多少资金。下面&#xff0c;我们就来详细解答这个问题&#xff0c;并从多个角度分析开设网点的要点。 一、 开设拼多多网点&#xff0c;首要任务是确定启动资金。根据不同的经营模式和地区差异&#xff0c;成本会有所不同…

基于SpringBoot + Vue的兼职网站管理系统设计与实现+毕业论文+答辩PPT

系统介绍 本系统包含管理员、用户、企业三个角色。 管理员角色&#xff1a;前台首页、个人中心、用户管理、企业管理、兼职信息管理、职位申请管理、留言板管理、系统管理。 用户角色&#xff1a;前台首页、个人中心、职位申请管理。 企业角色&#xff1a;前台首页、个人中心、…

COMSOL粗略估算计算时间

COMSOL粗略估算模型计算时间 针对反复修改调试的有限元模型&#xff0c;需要大致估算有限元模型的计算时间。经查阅&#xff0c;模型求解的自由度数和求解时间密切相关。 测试条件 测试模型为声-固耦合模型&#xff0c;电脑内存32G&#xff0c;CPU-i7-10700K&#xff0c;核显…

【算法】滑动窗口——最小覆盖子串

本节博客是对“最小覆盖子串”题目由暴力求解到滑动窗口的思路解析&#xff0c;有需要借鉴即可。 目录 1.题目2.滑动窗口解法3.总结 1.题目 题目链接&#xff1a;LINK 这个题目是困难难度&#xff0c;感觉是一个中等题目的感觉。 首先我肯定想到的是暴力求解的方法&#xff…

STM32(GPIO)

GPIO简介 GPIO&#xff08;General Purpose Input Output&#xff09;通用输入输出口 引脚电平&#xff1a;0V~3.3V&#xff0c;部分引脚可容忍5V 输出模式下可控制端口输出高低电平&#xff0c;用以驱动LED、控制蜂鸣器、模拟通信协议输出时序等 输入模式下可读取端口的高低电…

Java特性之设计模式【享元模式】

一、享元模式 概述 享元模式&#xff08;Flyweight Pattern&#xff09;主要用于减少创建对象的数量&#xff0c;以减少内存占用和提高性能。这种类型的设计模式属于结构型模式&#xff0c;它提供了减少对象数量从而改善应用所需的对象结构的方式 享元模式尝试重用现有的同类对…

OS复习笔记ch5-4-2

引言 承接上文我们介绍了信号量机制和应用信号量机制实现的进程同步和互斥&#xff0c;这一节我们将围绕一些经典问题对信号量机制展开更深入地探讨。 读者/写者问题 读者/写者问题与我们之前遇到的问题类型不同&#xff0c;它描述的是&#xff1a; 有读者和写者两组进程&am…

C++初阶学习第七弹——探索STL奥秘(二)——string的模拟实现

标准库中的string&#xff1a;C初阶学习第六弹——string&#xff08;1&#xff09;——标准库中的string类-CSDN博客 前言&#xff1a; 在前面我们已经学习了如何使用标准库中的string类&#xff0c;但作为一个合格的程序员&#xff0c;我们不仅要会用&#xff0c;还要知道如…

网络库-libevent介绍

1.简介 libevent是一个事件驱动的网络库&#xff0c;主要用于构建可扩展的网络服务器。它提供了跨平台的API&#xff0c;支持多种事件通知机制&#xff0c;如select、poll、epoll、kqueue等。 主要组件 event: 表示一个具体的事件&#xff0c;包括事件类型、事件回调等。eve…

房屋出租管理系统需求分析及功能介绍

房屋租赁管理系统适用于写字楼、办公楼、厂区、园区、商城、公寓等商办商业不动产的租赁管理及租赁营销&#xff1b;提供资产管理&#xff0c;合同管理&#xff0c;租赁管理&#xff0c; 物业管理&#xff0c;门禁管理等一体化的运营管理平台&#xff0c;提高项目方管理运营效率…

如何查看centos7是否安装nginx

要查看 CentOS 7 系统上是否安装了 Nginx&#xff0c;您可以使用多种方法来检查。以下是一些常见的方法&#xff1a; 通过 RPM 包管理器查询 在 CentOS 系统上&#xff0c;可以使用 RPM 包管理器来查询已安装的软件包。要查看是否安装了 Nginx&#xff0c;您可以在终端中运行以…

【C++】学习笔记——继承_1

文章目录 十一、模板进阶5. 模板的优缺点 十二、继承1. 继承的概念及定义2. 基类和派生类对象赋值转换3. 继承中的作用域4. 派生类的默认成员函数 未完待续 十一、模板进阶 5. 模板的优缺点 优点&#xff1a; 模板复用了代码&#xff0c;节省资源&#xff0c;更快的迭代开发&a…

某银行软件测试笔试题,满分一百你能得多少分?

时间90分钟&#xff0c;满分100分&#xff09; 考试要求&#xff1a;计算机相关专业试题 一、填空题&#xff08;每空1分&#xff0c;共10分&#xff09; 1. ______验证___是保证软件正确实现特定功能的一系列活动和过程。 2. 按开发阶段分&#xff0c;软件测试可分为&#x…