【 C++ 】闭散列哈希表的模拟实现

哈希节点状态

我们都很清楚数组里的每一个值无非三种状态：

  1. 如果某下标没有值，则代表空EMPTY。
  2. 如果有值在代表存在EXIST。
  3. 如果此位置的值被删掉了，则表示为DELETE。

而这三种状态我们可以借助enum枚举来帮助我们表示数组里每个位置的状态。这里我们专门封装一个类来记录每个位置的状态，以此汇报给后续的哈希表。

enum State
{EMPTY,EXIST,DELETE
};//哈希节点
template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//记录每个位置的状态，默认给空
};//哈希表
template<class K, class V, class HashFunc = DefaultHash<K>>//添加仿函数便于把其他类型的数据转换为整型数据
class HashTable
{typedef HashData<K, V> Data;
public://相关功能的实现……
private:vector<Data> _tables;size_t _n = 0;//记录存放的有效数据的个数
};

实现好了哈希节点的类，就能够很好的帮助我们后续的查找，示例：

在这里插入图片描述

  • 查找50：

50%10=0，下标0的值不是50，继续++下标往后查找，直至下标3的下标为止。

  • 查找60：

60%10=0，下标0不是，往后++下标继续查找，找到下标4发现状态为EMPTY空，此时停止查询，因为往后就不可能出现了

  • 删除10，再查找50：

50%10=0，下标0的值不是，++下标到下标1，发现状态为DELETE删除，继续++下标直至下标3的值为50，找到了。

哈希表的扩容

  • 散列表的载荷因子定义为：α = 填入表中的元素个数 / 散列表的长度。
  • α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。
  • 对于开放定址法（闭散列），载荷因子是特别重要因素，应严格限制在0.7 ~ 0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照质数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了载荷因子为0.75，超过此值将resize散列表。

综上，我们在后续的插入操作中，必然要考虑到扩容的情况，我们直接把负载因子控制在0.7，超过了就扩容。具体操作见下文哈希表的插入操作。

构建仿函数把所有数据类型转换为整型并特化

在我们后续的插入操作中，插入的数据类型如果是整数，那么可以直接建立映射关系，可若是字符串，就没那么容易了，因此，我们需要套一层仿函数，来帮助我们把字符串类型转换成整型的数据再建立映射关系。主要分为以下三类需要写仿函数的情况：

  1. key为整型，为默认仿函数的情况。
    此时的数据类型为整型，直接强转size_t随后返回。

  2. key为字符串，单独写个字符串转整型的仿函数。
    针对于字符串转整型，我们推出下面两种方法，不过都是会存在问题的：

    • 只用首字母的ascii码来映射，此法不合理，因为"abc"和"axy"本是俩不用字符串，经过转换，会引发冲突。
    • 字符串内所有字符ASCII码值之和，此法也会产生冲突，因为"abcd"和"bcad"在此情况就会冲突。

为了避免冲突，几位大佬推出多种算法思想，下面我取其中一种算法思想来讲解：

BKDR哈希算法：
hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..

为了能够让我们的哈希表能够自动识别传入数据的类型，不用手动声明，这里我们可以借助特化来解决，仿函数+特化总代码如下：

//利用仿函数将数据类型转换为整型
template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDR哈希算法size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;//把所有字符的ascii码值累计加起来}return hash;}
};

哈希表的插入

哈希表的插入主要是三大步骤：

  • 去除冗余
  • 扩容操作
  • 插入操作

下面分开来演示。

1、去除冗余：

  1. 复用Find查找函数，去帮助我们查找插入的值是否存在 。
  2. 若存在，直接返回false 。
  3. 不存在，再进行后续的插入操作。

2、扩容操作：

  1. 如果哈希表一开始就为空，则要扩容。
  2. 如果填入表中的元素个数*10 再 / 表的大小>=7，就扩容（*10是为了避免出现size_t的类型相除不会有小数的情况）。
  3. 扩容以后要重新建立映射关系。
  4. 创建一个新的哈希对象，扩容到先前旧表扩容的大小。
  5. 遍历旧表，把旧表每个存在的元素插入到新表，此步骤让新表自动完成映射关系，无序手动构建。
  6. 利用swap函数把新表交换到旧表那，此时的旧表就是已经扩好容且建立号映射关系的哈希表。

3、插入操作：

  1. 借助仿函数把插入的数据类型转为整型并定义变量保存插入键值对的key。
  2. 用此变量%=哈希表的size()，不能是capacity()，因为[ ]运算符会判断下标是否小于size，且对于哈希表，应该尽量控制size和capacity一样大。
  3. 遍历进行线性探测 / 二次探测，如果这个位置的状态为EXIST存在，说明还要往后遍历查找。
  4. 遍历结束，说明此位置的状态为空EMPTY或删除DELETE，可以放值。
  5. 把插入的值放进该位置，更新状态为EXIST，有效数据个数++。
//插入
bool Insert(const pair<K, V>& kv)
{//1、去除冗余if (Find(kv.first)){//说明此值已经有了，直接返回falsereturn false;}//2、扩容//负载因子超过0.7，就扩容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;//扩容以后，需要重新建立映射关系HashTable<K, V, HashFunc> newHT;newHT._tables.resize(newSize);//遍历旧表，把旧表每个存在的元素插入newHTfor (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射关系后交换}//3、插入HashFunc hf;size_t starti = hf(kv.first);//取出键值对的key，并且避免了负数的情况，借用仿函数确保是整型数据starti %= _tables.size();size_t hashi = starti;size_t i = 1;//线性探测/二次探测while (_tables[hashi]._state == EXIST){hashi = starti + i;//二次探测改为 +i^2++i;hashi %= _tables.size();//防止hashi超出数组}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;
}

哈希表的查找

查找的核心逻辑就是找到key相同，就返回此对象的地址，找到空就返回nullptr，具体细分规则如下：

  1. 先去判断表的大小是否为0，为0直接返回nullptr。
  2. 按照线性探测 / 二次探测的方式去遍历，遍历的条件是此位置的状态不为空EMPTY。
  3. 如果遍历到某哈希表中的对象的值等于要查找的值（前提是此位置的状态不为DELETE删除），返回此对象的地址。
  4. 当遍历结束后，说明此位置的状态为空EMPTY，哈希表没有我们要查找的值，返回nullptr。
//查找
Data* Find(const K& key)
{//判断表的size是否为0if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t starti = hf(key);//通过仿函数把其它类型数据转为整型数据starti %= _tables.size();size_t hashi = starti;size_t i = 1;//线性探测/二次探测while (_tables[hashi]._state != EMPTY)//不为空就继续{if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];//找到了就返回此对象的地址}hashi = starti + i;//二次探测改为 +i^2++i;hashi %= _tables.size();//防止hashi超出数组}return nullptr;
}

哈希表的删除

删除的逻辑很简单，遵循下面的规则：

  1. 复用Find函数去帮我们查找删除的位置是否存在。
  2. 若存在，把此位置的状态置为DELETE即可，此时表中的有效数据个数_n需要减减，最后返回true。
  3. 若不存在，直接返回false。
//删除
bool Erase(const K& key)
{//复用Find函数去帮助我们查找删除的值是否存在Data* ret = Find(key);if (ret){//若存在，直接把此位置的状态置为DELETE即可ret->_state = DELETE;return true;}else{return false;}
}

完整代码

#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;//利用仿函数将数据类型转换为整型
template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDR哈希算法size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;//把所有字符的ascii码值累计加起来}return hash;}
};//闭散列哈希表的模拟实现
namespace CloseHash
{enum State{EMPTY,EXIST,DELETE};//哈希节点状态的类template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;//记录每个位置的状态，默认给空};//哈希表的类template<class K, class V, class HashFunc = DefaultHash<K>>//添加仿函数便于把其他类型的数据转换为整型数据class HashTable{typedef HashData<K, V> Data;public://插入bool Insert(const pair<K, V>& kv){//1、去除冗余if (Find(kv.first)){//说明此值已经有了，直接返回falsereturn false;}//2、扩容//负载因子超过0.7，就扩容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;//扩容以后，需要重新建立映射关系HashTable<K, V, HashFunc> newHT;newHT._tables.resize(newSize);//遍历旧表，把旧表每个存在的元素插入newHTfor (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射关系后交换}//3、插入HashFunc hf;size_t starti = hf(kv.first);//取出键值对的key，并且避免了负数的情况，借用仿函数确保是整型数据starti %= _tables.size();size_t hashi = starti;size_t i = 1;//线性探测/二次探测while (_tables[hashi]._state == EXIST){hashi = starti + i;//二次探测改为 +i^2++i;hashi %= _tables.size();//防止hashi超出数组}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;}//查找Data* Find(const K& key){//判断表的size是否为0if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t starti = hf(key);//通过仿函数把其它类型数据转为整型数据starti %= _tables.size();size_t hashi = starti;size_t i = 1;//线性探测/二次探测while (_tables[hashi]._state != EMPTY)//不为空就继续{if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];//找到了就返回此对象的地址}hashi = starti + i;//二次探测改为 +i^2++i;hashi %= _tables.size();//防止hashi超出数组}return nullptr;}//删除bool Erase(const K& key){//复用Find函数去帮助我们查找删除的值是否存在Data* ret = Find(key);if (ret){//若存在，直接把此位置的状态置为DELETE即可ret->_state = DELETE;return true;}else{return false;}}private:vector<Data> _tables;size_t _n = 0;//记录存放的有效数据的个数};
}

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Oracle ADG相关介绍

Oracle ADG相关介绍

文章目录 一、ADG原理1、ADG介绍2、ADG搭建流程 二、ADG相关参数三、增量修复 一、ADG原理 1、ADG介绍 Oracle ADG&#xff08;Advanced Data Guard&#xff09;是Oracle数据库的一项高可用和灾难恢复技术&#xff0c;它通过将数据保持在物理备库中来提供数据保护和容灾能力。…
阅读更多...
每日五道java面试题之spring篇（七）

每日五道java面试题之spring篇（七）

目录&#xff1a; 第一题. 什么是Spring beans&#xff1f;第二题. 一个 Spring Bean 定义 包含什么&#xff1f;第三题. 如何给Spring 容器提供配置元数据&#xff1f;Spring有几种配置方式?第四题. Spring基于xml注入bean的几种方式?第五题&#xff1a;你怎样定义类的作用域…
阅读更多...
POST参数里加号+变成空格的问题处理

POST参数里加号+变成空格的问题处理

今天遇到个这样的问题&#xff0c;从前端传到后端的加密报文&#xff0c;里面包含了号&#xff0c;但在后端日志输出看出&#xff0c;变成空格。这个是由于经过RSA加密后引起的 解决办法&#xff1a; 1.前端转码&#xff1a;使用encodeURIComponent对参数进行转码 2.后端解码…
阅读更多...
【自然语言处理四-从矩阵操作角度看 自注意self attention】

【自然语言处理四-从矩阵操作角度看 自注意self attention】

自然语言处理四-从矩阵操作角度看 自注意self attention 从矩阵角度看self attention获取Q K V矩阵注意力分数softmax注意力的输出再来分析整体的attention的矩阵操作过程从矩阵操作角度看&#xff0c;self attention如何解决问题的&#xff1f;W^q^ W^k^ W^v^这三个矩阵怎么获…
阅读更多...
OpenCV 16 - Qt使用opencv视觉库

OpenCV 16 - Qt使用opencv视觉库

1 下载好opencv视觉库 不知道怎么下载和编译opencv视觉库的可以直接使用这个 : opencvcv_3.4.2_qt 2 解压opencv包 3 打开opencv的安装目录 4.打开x86/bin 复制里面所有的dll文件&#xff0c;黏贴到C/windows/syswow64里面 5 新建Qt项目 6 修改pro文件:添加对应的头文件和库文件…
阅读更多...
【GameFramework框架内置模块】4、内置模块之调试器（Debugger）

【GameFramework框架内置模块】4、内置模块之调试器（Debugger）

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址QQ群&#xff1a;398291828 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 【GameFramework框架】系列教程目录&#xff1a;…
阅读更多...
matlab批量替换txt文本文件的特定行的内容

matlab批量替换txt文本文件的特定行的内容

1.下图所示&#xff0c;我想要替换第14行。 2.运行代码后&#xff0c;第14行已经更改为需要的内容。 clc,clear; %%----------------------需要更改的地方------------------------------------ % 设置要操作的文本文件路径&#xff0c;替换为你自己的文件路径 path D:\paper_…
阅读更多...
Linux Nginx SSL 证书配置正确，扔展示不安全

Linux Nginx SSL 证书配置正确，扔展示不安全

Nginx SSL 配置 首先我能够确定自己的Nginx SSL是配置正确的&#xff1a; 问题展示 通过浏览器访问自己域名&#xff0c;点击不安全后查看证书&#xff0c;展示的证书并不是自己所配置的证书&#xff0c;如下&#xff1a; 通过curl -vvv https://域名访问返回的证书是过期…
阅读更多...
60V耐压降压恒流芯片SL6015B替代PT4115

60V耐压降压恒流芯片SL6015B替代PT4115

SL6015B是一款耐压60V的降压恒流芯片&#xff0c;可用于替代PT4115。它具有以下特点&#xff1a; 1. 耐压60V&#xff0c;适用于高电压应用场景&#xff1b; 2. 恒流输出&#xff0c;能够提供稳定的电流输出&#xff1b; 3. 内部集成软启动功能&#xff0c;有效减小启动电流&am…
阅读更多...
html5盒子模型

html5盒子模型

1.边框的常用属性 border-color 属性 说明 示例 border-top-color 上边框颜色 border-top-color:#369; border-right-color 右边框颜色 border-right-color:#369; border-bottom-color 下边框颜色 border-bottom-color:#fae45b; border-left-color 左边框颜色…
阅读更多...
BUUCTF crypto做题记录（9）新手向

BUUCTF crypto做题记录（9）新手向

一、rsa2 得到题目代码如下&#xff1a; N 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170…
阅读更多...
探究前端路由hash和history的实现原理（包教包会）

探究前端路由hash和history的实现原理（包教包会）

今天我们来讲一讲前端中很重要的一个部分路由&#xff08;router&#xff09;&#xff0c;想必前端小伙伴对‘路由’一词都不会感到陌生。但是如果哪天面试官问你&#xff0c;能大概说一说前端路由的实现原理吗&#xff1f; 你又会如何应对呢&#xff1f; 今天勇宝就带着大家一…
阅读更多...
41.仿简道云公式函数实战-数学函数-SUMIF

41.仿简道云公式函数实战-数学函数-SUMIF

1. SUMIF函数 SUMIF 函数可用于计算子表单中满足某一条件的数字相加并返回和。 2. 函数用法 SUMIF(range, criteria, [sum_range]) 其中各参数的含义及使用方法如下&#xff1a; range&#xff1a;必需&#xff1b;根据 criteria 的条件规则进行检测的判断字段。支持的字段…
阅读更多...
RC4算法

RC4算法

RC4 RC4是Ron Rivest为RSA设计的序列密码，RC4算法简单、速度快、容易用软硬件实现，因此应用广泛。比如WEP、WPA、SSL/TLS应用了RC4；Windows、Lotus notes、Apple APCE等软件系统也应用了RC4。 1. RC4算法 RC4具体算法如下： 第一步：密钥调度算法（The Key-Scheduling Alg…
阅读更多...
3. Java中的锁

3. Java中的锁

文章目录 乐观锁与悲观锁乐观锁(无锁编程,版本号机制)悲观锁两种锁的伪代码比较 通过 8 种锁运行案例,了解锁锁相关的 8 种案例演示场景一场景二场景三场景四场景五场景六场景七场景八 synchronized 有三种应用方式8 种锁的案例实际体现在 3 个地方 从字节码角度分析 synchroni…
阅读更多...
排序（9.17）

排序（9.17）

1.排序的概念及其运用 1.1排序的概念 排序 &#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性 &#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的记…
阅读更多...
OSI参考模型和TCP/IP网络参考模型

OSI参考模型和TCP/IP网络参考模型

1、OSI参考模型 1.1 产生背景 为了解决网络之间的兼容性问题，实现网络设备间的相互通讯，国际标准化组织ISO于1984年提出了OSIRM(Open System Interconnection Reference Model,开放系统互连参考模型）。OSI参考模型很快成为计算机网络通信的基础模型。由于种种原因，并没有…
阅读更多...
Redis高可用三主三从集群部署

Redis高可用三主三从集群部署

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容使用宝塔面板搭建集群规划配置验证 使用docker搭建使用脚本搭建&#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博…
阅读更多...
聊一聊bpmn-js中的elementFactory模块

聊一聊bpmn-js中的elementFactory模块

上一篇文章里我们了解了bpmn-js使用palette模块进行左侧小工具区域（也可以理解为调色板区域）的功能扩展，今天这个话题则是延续上期的palette进行开展的。 从上篇文章《聊一聊bpmn-js中的Palette》我们知道，PaletteProvider通过getPaletteEntries方法提供小工具Map对象，而单…
阅读更多...
Python 实现 CR 指标计算 (带状能量线）：股票技术分析的利器系列（13）

Python 实现 CR 指标计算 (带状能量线）：股票技术分析的利器系列（13）

Python 实现 CR 指标计算 (带状能量线&#xff09;&#xff1a;股票技术分析的利器系列&#xff08;13&#xff09; 介绍算法公式 代码rolling函数介绍核心代码计算MID计算CR计算移动平均 完整代码 介绍 CR指标&#xff0c;又称带状能量线&#xff0c;通过计算股价的动能和变化…
阅读更多...
最新文章

Copyright @ 2022~2023