哈希表——闭散列表

该哈希表实现是闭散列实现法。

闭散列表:

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

        那如何寻找下一个空位置呢?

线性探测:

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

注意:除了线性探测,你还可以进行二次探测等,看个人实现策略。

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

比如2.1中的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4,
因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。

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

// 哈希表每个空间给个标记
// EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};

线性探测实现插入:

		bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 负载因子0.7就扩容if (_n*10 / _tables.size() == 7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newSize);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hf;// 线性探测size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._s == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}

什么是负载因子?

        负载因子是关键词key的存储个数与哈希表内存大小之比,一般取0.75左右,这样做是为了提高存储效率,(只有百分之75的内存可以用,剩余的百分之25,是不存储的)减少哈希冲突。

如何扩展内存?

        定义一个新的对象,开好想要的内存,将旧表的数据重新查到新的哈希表中,旧表的数据分布与新表的数据分布不一样,将旧表数据插入完之后,再将新表的哈希表数据与旧表的数据进行交换。

哈希表的查找:

		HashData<K, V>* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();while (_tables[hashi]._s != EMPTY){if (_tables[hashi]._s == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return NULL;}

数据有三种状态:存在,删除,为空。

存在和删除的状态下如果没有找到要查找的数据就要向后继续查找,因为插入时进行的是线性插入,只有为空和删除的位置才进行插入,所以有可能想要的数据会出现在,删除状态的后面。

注意:如果是二次探测就进行二次查找

哈希表的删除:

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

将要删除的数据状态进行标记就行了,如果标记为空,就会影响查找函数的进行,就可能会出现查找错误的情况。

完整代码及其测试代码:

#include<vector>template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}//cout << key << ":" << hash << endl;return hash;}
};namespace open_address
{enum Status{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;Status _s;          //状态};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 负载因子0.7就扩容if (_n*10 / _tables.size() == 7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newSize);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hf;// 线性探测size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._s == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();while (_tables[hashi]._s != EMPTY){if (_tables[hashi]._s == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return NULL;}// 伪删除法bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_s = DELETE;--_n;return true;}else{return false;}}void Print(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){//printf("[%d]->%d\n", i, _tables[i]._kv.first);cout << "[" << i << "]->" << _tables[i]._kv.first <<":" << _tables[i]._kv.second<< endl;}else if (_tables[i]._s == EMPTY){printf("[%d]->\n", i);}else{printf("[%d]->D\n", i);}}cout << endl;}private:vector<HashData<K, V>> _tables;size_t _n = 0; // 存储的关键字的个数};void TestHT1(){HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.Erase(3);ht.Print();if (ht.Find(3)){cout << "3存在" << endl;}else{cout << "3不存在" << endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();}void TestHT2(){string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };//HashTable<string, int, HashFuncString> ht;HashTable<string, int> ht;for (auto& e : arr){//auto ret = ht.Find(e);HashData<string, int>* ret = ht.Find(e);if (ret){ret->_kv.second++;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair("apple", 1));ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("abc", 1));ht.Insert(make_pair("acb", 1));ht.Insert(make_pair("aad", 1));ht.Print();}
}

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

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

相关文章

96.STL-遍历算法 transform

目录 transform 语法&#xff1a; 功能描述&#xff1a; 函数原型&#xff1a; 代码示例&#xff1a; transform 是 C 标准模板库&#xff08;STL&#xff09;中的一个算法&#xff0c;用于对一个范围内的元素进行转换并将结果存储到另一个范围。以下是简要解释和一个示例…

【开源】基于JAVA的衣物搭配系统

项目编号&#xff1a; S 016 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S016&#xff0c;文末获取源码。} 项目编号&#xff1a;S016&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容2.1 衣物档案模块2.2 衣物搭配模块2.3 衣…

成为AI产品经理——TPR、FPR、ROC、AUC

目录 一、PR图、BEP 1.PR图 2.BEP 二、灵敏度、特异度 1.灵敏度 2.特异度 三、真正率、假正率 1.真正率 2.假正率 三、ROC、AUC 1.ROC 2.AUC 四、KS值 一、PR图、BEP 1.PR图 二分类问题模型通常输出的是一个概率值&#xff0c;我们需要设定一个阈值&#xff…

手机爬虫用Fiddler详细教程

如果你正在进行手机爬虫的工作&#xff0c;那么一款强大而又实用的网络调试工具Fiddler将会是你的好帮手。今天&#xff0c;我将和大家分享一份详细的Fiddler教程&#xff0c;教你如何使用它来轻松捕获和分析手机App的网络请求。让我们一起来探索Fiddler的功能和操作&#xff0…

IntelliJ IDEA 16创建Web项目

首先要理解一个概念&#xff1a;在IntelliJ IDEA中“new Project”相当于eclipse中的工作空间&#xff08;Workspace&#xff09;&#xff0c;而“new Module”相当于eclipse中的工程&#xff08;Project&#xff09;。以下均采用Intellij的说法&#xff0c;请自行对照转换理解…

opencv-图像平滑

高斯平滑 高斯平滑即采用高斯卷积核对图像矩阵进行卷积操作。高斯卷积核是一个近似服从高斯分布的矩阵&#xff0c;随着距离中心点的距离增加&#xff0c;其值变小。这样进行平滑处理时&#xff0c;图像矩阵中锚点处像素值权重大&#xff0c;边缘处像素值权重小。 import cv2 …

PTA-6-48 使用面向对象的思想编写程序描述动物

题目&#xff1a; 使用面向对象的思想编写程序描述动物&#xff0c;说明&#xff1a; &#xff08;1) 分析兔子和青蛙的共性&#xff0c;定义抽象的动物类&#xff0c;拥有一些动物共有的属性&#xff1a;名字、颜色、类别&#xff08;哺乳类、非哺乳类&#xff09;&#xff0c…

在Windows WSL (Linux的Windows子系统)上运行的Ubuntu如何更改主机名

在Windows 安装的Ubuntu&#xff0c;如何修改主机名。有列了两种方法&#xff0c;提供给大家参照。 文章目录 方法一&#xff1a;hostname指令修改方法二&#xff1a;修改配置文件修改hostnanmewsl.conf 文件配置选项推荐阅读 方法一&#xff1a;hostname指令修改 hostname指…

第 373 场 LeetCode 周赛题解

A 循环移位后的矩阵相似检查 模拟 class Solution { public:bool areSimilar(vector<vector<int>> &mat, int k) {int m mat.size(), n mat[0].size();k % n;auto g mat;for (int i 0; i < m; i)if (i & 1)rotate(mat[i].begin(), mat[i].begin() …

MySQL学习day03

一、SQL图形化界面工具 常用比较常用的图形化界面有sqlyog、mavicat、datagrip datagrip工具使用相当方便&#xff0c;功能比前面两种都要强大。 DataGrip工具的安装和使用请查看这篇文档&#xff1a;DataGrip 安装教程 DML-介绍 DML全称是Data Manipulation Language(数据…

什么是高级语言、机器语言、汇编语言?什么是编译和解释?

1、高级语言 计算机程序是一种让计算机执行特定任务的方法。程序是由程序员用一种称为编程语言的特殊语言编写的。编程语言有很多种&#xff0c;例如 C、C、Java、Python 等。这些语言被称为高级语言&#xff0c;因为它们更接近人类的自然语言&#xff0c;而不是计算机能够直接…

电脑便签功能在哪里找?电脑桌面便签怎么添加?

很多上班族在使用电脑办公的时候&#xff0c;都需要随手记录工作事项&#xff0c;例如记录共同工作时的想法、会议笔记、常用工作资料、每天待办的工作任务等事项&#xff0c;这时候使用纸质的笔记本来记录工作&#xff0c;不仅不方便随时查看和使用&#xff0c;而且在修改、删…

final关键字-Java

final关键字 一、使用场景1、当不希望类被继承时&#xff0c;可以用final修饰。2、当不希望父类的某个方法被子类覆盖/重写(override)时&#xff0c;可以用final修饰。3、当不希望类的的某个属性的值被修改&#xff0c;可以用final修饰。4、当不希望某个局部变量被修改&#xf…

Kibana部署

服务器 安装软件主机名IP地址系统版本配置KibanaElk10.3.145.14centos7.5.18042核4G软件版本&#xff1a;nginx-1.14.2、kibana-7.13.2-linux-x86_64.tar.gz 1. 安装配置Kibana &#xff08;1&#xff09;安装 [rootelk ~]# tar zxf kibana-7.13.2-linux-x86_64.tar.gz -C…

第十五届蓝桥杯(Web 应用开发)模拟赛 1 期-大学组(详细分析解答)

目录 1.动态的Tab栏 1.1 题目要求 1.2 题目分析 1.3 源代码 2.地球环游 2.1 题目要求 2.2 题目分析 2.3 源代码 3.迷惑的this 3.1 题目要求 3.2 题目分析 3.3 源代码 4.魔法失灵了 4.1 题目要求 4.2 题目分析 4.3 源代码 5.燃烧你的卡路里 5.1 题目要求 5.2…

SpectralGPT: Spectral Foundation Model 论文翻译1

遥感领域的通用大模型 2023.11.13在CVPR发表 原文地址&#xff1a;[2311.07113] SpectralGPT: Spectral Foundation Model (arxiv.org) 摘要 ​ 基础模型最近引起了人们的极大关注&#xff0c;因为它有可能以一种自我监督的方式彻底改变视觉表征学习领域。虽然大多数基础模型…

VAE模型及pytorch实现

VAE模型及pytorch实现 VAE模型推导部分最小化KL散度推导代码部分损失函数Encoder部分Decoder部分VAE整体架构 VAE问题参考资料 VAE&#xff08;变分自编码器&#xff09;是一种生成模型&#xff0c;结合了自编码器和概率图模型的思想。它通过学习数据的潜在分布&#xff0c;可以…

人工智能|机器学习——机器学习如何判断模型训练是否充分

一、查看训练日志 训练日志是机器学习中广泛使用的训练诊断工具&#xff0c;每个 epoch 或 iterator 结束后&#xff0c;在训练集和验证集上评估模型&#xff0c;并以折线图的形式显示模型性能和收敛状况。训练期间查看模型的训练日志可用于判断模型训练时的问题&#xff0c;例…

【Android知识笔记】性能优化专题(四)

App 线程优化 线程调度原理 任意时刻,只有一个线程占用CPU,处于运行状态多线程并发:轮流获取CPU使用权JVM负责线程调度:按照特定机制分配CPU使用权线程调度模型 分时调度模型:轮流获取、均分CPU时间抢占式调度模型:优先级高的获取,JVM采用Android线程调度 nice值:Proc…

Linux Nmap命令解析(Nmap指令)(功能:主机发现、ping扫描、arp扫描、端口扫描、服务版本检测、操作系统识别等)

文章目录 Linux Nmap 命令解析简介Nmap 的核心功能主机发现端口扫描服务版本检测OS 指纹识别&#xff08;操作系统指纹识别&#xff09;脚本扫描 安装 NmapNmap 命令结构Nmap 命令文档英文中文 主机发现Ping 扫描ARP 扫描关于nmap -PR&#xff08;ARP Ping Scan&#xff09;和n…