【数据结构】哈希表的开散列和闭散列模拟

哈希思想

在顺序和树状结构中，元素的存储与其存储位置之间是没有对应关系，因此在查找一个元素时，必须要经过多次的比较。

顺序查找的时间复杂度为0(N)，树的查找时间复杂度为log(N)。

我们最希望的搜索方式：通过元素的特性，不需要对比查找，而是直接找到某个元素。

这一个通过key与存储位置建立一一的思想就是hash思想。

哈希表就是基于哈希思想的一种具体实现。哈希表也叫散列表，是一种数据结构。无论有多少条数据，插入和查找的时间复杂度都是O(1),因此由于其极高的效率，被广泛使用。

建立映射关系：
例如集合{8，5，6，3，7，2，1，0}

key为每个元素的值，capaticy为哈希表元素的容量。

357801d7e27342f283f999b121998957.png

映射过程：
元素8   key=8  8%10=8 映射在数组下标为第8的位置上

元素7   映射在下标为7的位置上

  1. 直接定值法：（关键数范围集中，量不大的时候）关键字和存储位置是一一对应，不存在哈希冲突
  2. 除留余数法：（关键字很分散，量很大）关键字和存储位置是一对多的关系，存在哈希冲突

哈希冲突

对于两个数据元素的关键字 eq?k_%7Bi%7D 和 eq?k_j%7B%7D (i != j)，有 eq?k_%7Bi%7D != eq?k_j%7B%7D ，但有：Hash(eq?k_%7Bi%7D) == Hash(eq?k_j%7B%7D)，即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

例如上述的举例：
key的值为 18  15的时候

hashi计算的方法得出 需要映射到8 和5的位置上，但是8 和5的位置已经存在·其它值。这就产生了冲突

哈希冲突的解决

1.开放定址法(闭散列)

a:线性探测

        如果发生冲突，就往后一次一步寻找为空的位置。

b:二次探测

        发生冲突，每次往后走俩步，寻找没有冲突的位置。

线性探测的缺点：容易产生成片的冲突

二次探测的缺点：虽然解决了容易产生成片冲突，但是空间利用率也不高

2.开散列

又称开链法、哈希桶，计算如果产生了哈希冲突，就以链表的形式将冲突的值链接起来。

dee00f98d1f640ae8b8c56f3fb446b5e.png

哈希表的闭散列实现

闭散列哈希中的，每个位置不仅需要存储数据，还需要标注状态，方便查找删除。

enum State { EMPTY, EXIST, DELETE };

标记状态的意义？

在一个哈希表中，如果需要存放，我们会计算出key映射位置。如果key映射位置被占走，会往后继续寻找到删除/空的位置放置。

在查找时，在映射位置找不到时，需要往后寻找，我们不可能一直往后寻找O(N).,那就失去哈希表的价值，当我们遇到存在/删除位置时继续往后寻找，直到找到空位置，说明没有该元素。

因此在存储时，每个位置都必须有状态和数据

		struct Elem{pair<K, V> _val;State _state;};

框架

哈希表还需要维持容量的问题。因此需要_size表示实际存放，来维持负载因子

template<class K,class V> //k—v结构
class HashTable	
{
public:
//...
private:vector<Elem> _ht;size_t _size;		//实际存储size_t _totalSize;  // 哈希表中的所有元素：有效和已删除, 扩容时候要用到
};

哈希表的插入

  1. 根据K查找是为空，是则返回false
  2. 计算负载因子，是否需要扩容
  3. 插入新元素
  4. 更新位置状态，有效数目增加

扩容的方法

  • 开新的哈希表（默认空间为原来的2倍）
  • 遍历旧表，调用哈希表的插入。
  • 交换俩个表。

		// 插入bool Insert(const pair<K, V>& val){if (Find(val.first) != -1)return false;//负载因子为7时，扩容if ((_size * 10) / _ht.size() == 7){size_t newsize = _ht.size() * 2;HashTable<K, V>newht;newht._ht.resize(newsize);//遍历旧表for (size_t i = 0; i < _ht.size(); i++){if (_ht[i]._state == EXIST)newht.Insert(_ht[i]._val);}_ht.swap(newht._ht);}//出入新元素size_t hashi = HashFunc(val.first);while (_ht[hashi]._state == EXIST){++hashi;hashi %= _ht.size();}_ht[hashi]._val = val;_ht[hashi]._state = EXIST;++_size;++_totalSize;return true;}

哈希表的查找

通过hash函数映射到hashi，往后一直比对，遇到存在比对，不是要找的val就往后需要，遇到删除也往后对比。直到遇到空返回。

		// 查找size_t Find(const K& key){size_t hashi = HashFunc(key);while (_ht[hashi]._state != EMPTY){if (_ht[hashi]._state == EXIST&& _ht[hashi]._val.first == key){return hashi;}++hashi;hashi %= _ht.size();}return -1;}

哈希表的删除

删除是比较简单，是一种伪删除，不需要对数据清楚，只需要修改状态为删除，减少有效个数

  1. 调用find，没有则返回flase
  2. 修改为状态
  3. 减少个数
		bool Erase(const K& key){int hashi = Find(key);if (hashi == -1)	return false;_ht[hashi]._state = DELETE;--_size;return true;}

这三部分就是闭散列的主体结构。需要维持负载因子和状态。

Gitee: 闭散列哈希代码

哈希桶

开散列哈希表就不要需要状态的使用，是由一个链表的数组构成。

就是一排一排的桶。想要查找数据，只需要映射位置，在桶中寻找，是O(1)的放法.

特别极端情况下可能达到O(N)。

框架

底层可以依赖单链表，只需要简单的头插即可。

链表的结点：需要包含下一个位置的指针，需要包含pair键值对

	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){}};

同样需要记录表中有效元素的个数，但是一般情况下，负载因子在80%-90%效率最大

我们为了简单实现，在100%时才扩容。 

template<class K, class V>
class HashTable
{
public://...
private:vector<Node*> _table; //哈希表size_t _n = 0; //哈希表中的有效元素个数
};

哈希桶的插入

  1. 检查是否为已经存在的Key
  2. 检查负载因子，为1就扩容
  3. 往hashi位置头插插入
  4. 修改个数

扩容的方法

  1. rasize一个二倍数量的原表
  2. 遍历旧表，将一个元素从链表的头取下，插入到新表中的hashi位置上。注意保存下一个位置！
  3. 交换俩张表

		bool Inset(const pair<K, V>& kv){if (Find(kv.first)){return false;}hash hf;//扩容if (_tables.size() == _n){size_t newsize = _tables.size() * 2;vector<Node*> newtable;newtable.resize(newsize, nullptr);for (size_t i = 0; i < (_tables.size()); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first % newtable.size());//头插cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);}size_t hashi = hf(kv.first) % _tables.size();Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}

哈希桶的查找

  • 计算hashi
  • 遍历单链表
  • 为空则返回flase
		Node* Find(const K& key){hash fc;size_t hashi = fc(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;cur=cur->_next;}return nullptr;}

哈希桶的删除

删除需要主要是删除的中间结点还是首结点

需要保存父亲结点

和单链表的删除基本一致

		bool Erase(const K& key){hash fc;size_t hashi = fc(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){//找到了if (cur->_kv.first == key){//头删if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}}return false;}

Gitee: 开散列哈希桶代码

关于仿函数HashFunc

仿函数是一种回调，可以定义出函数对象。

是对不同类型转化为key，之前在位图就已经介绍，本文用的是BDK算法

对于string字符串类型会有存在冲突，但是可以通过不同的算法映射到不到的位置上，通过几个值的比对能减少失误的概率。

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){//BKDRsize_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}
};

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

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

相关文章

STM32 新建寄存器版本MDK工程简要步骤

STM32 新建寄存器版本MDK工程简要步骤

新建工程文件夹 新建一个工程根目录文件夹&#xff0c;并在该文件夹里新建D/M/O/P/U文件夹。 Drivers&#xff1a;存放与硬件相关的驱动层文件Middlewares&#xff1a;存放正点原子提供的中间层组件文件和第三方中间层文件Output&#xff1a;存放工程编译输出文件Projects&am…
阅读更多...
linux系统下vscode portable版本的python环境搭建003：venv

linux系统下vscode portable版本的python环境搭建003：venv

这里写自定义目录标题 python安装方案一. 使用源码安装&#xff08;有[构建工具](https://blog.csdn.net/ResumeProject/article/details/136095629)的情况下&#xff09;方案二.使用系统包管理器 虚拟环境安装TESTCG 本文目的&#xff1a;希望在获得一个新的系统之后&#xff…
阅读更多...
Vue核心基础4：绑定样式、条件渲染、列表渲染

Vue核心基础4：绑定样式、条件渲染、列表渲染

1 绑定样式 【代码】 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>绑定样式</title><s…
阅读更多...
FL Studio版本升级-FL Studio怎么升级-FL Studio升级方案

FL Studio版本升级-FL Studio怎么升级-FL Studio升级方案

已经是新年2024年了&#xff0c;但是但是依然有很多朋友还在用FL Studio12又或者FL Studio20&#xff0c;今天这篇文章教大家如何升级FL Studio21 FL Studio 21是Image Line公司开发的音乐编曲软件&#xff0c;除了软件以外&#xff0c;我们还提供了FL Studio的升级服务&#…
阅读更多...
C++11中的简化声明

C++11中的简化声明

auto 用于自动类型推断&#xff0c;显示定义变量&#xff1a; typeid typeid推导出来的是字符串&#xff0c;只能看不能用&#xff0c;通过打印来查看变量的类型&#xff0c;用法如上。 decltype 同样是用来自动推导类型&#xff0c;与auto的区别是&#xff0c;auto在定义时必…
阅读更多...
MySQL篇----第十四篇

MySQL篇----第十四篇

系列文章目录 文章目录 系列文章目录前言一、MySQL 数据库作发布系统的存储，一天五万条以上的增量，预计运维三年,怎么优化？二、锁的优化策略三、索引的底层实现原理和优化四、什么情况下设置了索引但无法使用前言 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽…
阅读更多...
PKI - 借助Nginx实现_客户端使用自签证书供服务端验证

PKI - 借助Nginx实现_客户端使用自签证书供服务端验证

文章目录 Pre概述在 Nginx 中实现客户端使用自签名证书供服务器验证1. 生成客户端密钥对2. 生成自签名客户端证书3. 配置 Nginx4. 重启 Nginx 修5. 验证 在浏览器中安装客户端证书以便进行访问 Pre PKI - 借助Nginx 实现Https 服务端单向认证、服务端客户端双向认证 PKI - 数…
阅读更多...
线性代数的本质——1 向量

线性代数的本质——1 向量

向量是线性代数中最为基础的概念。 何为向量&#xff1f; 从物理上看&#xff0c; 向量就是既有大小又有方向的量&#xff0c;只要这两者一定&#xff0c;就可以在空间中随便移动。 从计算机应用的角度看&#xff0c;向量和列表很接近&#xff0c;可以用来描述某对象的几个不同…
阅读更多...
人力资源智能化管理项目（day05:角色管理）

人力资源智能化管理项目（day05:角色管理）

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/humanResourceIntelligentManagementProject 搭建页面结构 分页组件&#xff1a;设置layout&#xff0c;表示需要显示的内容&#xff0c;用逗号分隔&#xff0c;布局元素会依次显示。prev表示上一页&#xff0c;next为…
阅读更多...
HP Pavilion Laptop 15-cs3xxx原装出厂Win10.20H1系统

HP Pavilion Laptop 15-cs3xxx原装出厂Win10.20H1系统

惠普笔记本HP Pavilion - 15-cs3030tx原厂Windows10系统镜像下载 链接&#xff1a;https://pan.baidu.com/s/1LmdJoN7F3BGvt49ovq-eww?pwdzgmt 提取码&#xff1a;zgmt 适用型号&#xff1a; 15-cs3001tx&#xff0c;15-cs3030tx&#xff0c;15-cs3031tx&#xff0c;15-cs…
阅读更多...
数据结构：并查集讲解

数据结构：并查集讲解

并查集 1.并查集原理2.并查集实现3.并查集应用4.并查集的路径压缩 1.并查集原理 在一些应用问题中&#xff0c;需要将n个不同的元素划分成一些不相交的集合。开始时&#xff0c;每个元素自成一个单元素集合&#xff0c;然后按一定的规律将归于同一组元素的集合合并。在此过程中…
阅读更多...
寒假作业2024.2.11

寒假作业2024.2.11

请使用递归实现n! #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <unistd.h> int fun(int n) {if (n0) {return 1;} else {return n*fun(n-1);} } int main(int argc, const char *argv[]) {int n…
阅读更多...
Vue核心基础3：计算属性和监视属性

Vue核心基础3：计算属性和监视属性

1 计算属性 这边以姓名案例&#xff0c;来介绍计算属性 <body><div id"root"><!-- 姓&#xff1a;<input type"text" v-model:value"firstName"><br>名&#xff1a;<input type"text" v-model:value&…
阅读更多...
《CSS 简易速速上手小册》第10章：未来的 CSS（2024 最新版）

《CSS 简易速速上手小册》第10章：未来的 CSS（2024 最新版）

文章目录 10.1 CSS 的新特性和趋势10.1.1 基础知识10.1.2 重点案例&#xff1a;使用 CSS Grid 创建响应式图库10.1.3 拓展案例 1&#xff1a;利用 CSS 变量实现主题切换10.1.4 拓展案例 2&#xff1a;使用 lab() 颜色和 layer 规则优化样式 10.2 CSS Houdini&#xff1a;魔法般…
阅读更多...
C++进阶（十四）智能指针

C++进阶（十四）智能指针

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、为什么需要智能指针&#xff1f;二、内存泄漏1、 什么是内存泄漏&#xff0c;内存泄漏的危…
阅读更多...
STM32 7-8

STM32 7-8

目录 ADC AD单通道 AD多通道 DMA DMA转运数据 DMAAD多通道 ADC AD单通道 AD.c #include "stm32f10x.h" // Device header/*** brief 初始化AD所需要的所有设备* param 无* retval 无*/ void AD_Init(void) {RCC_APB2PeriphClockCmd(RCC_AP…
阅读更多...
在程序中使用日志功能

在程序中使用日志功能

在应用中&#xff0c;需要记录程序运行过程中的一些关键信息以及异常输出等。这些信息用来排查程序故障或者其他用途。 日志模块可以自己实现或者是借用第三方库&#xff0c;之前写过一个类似的使用Qt的打印重定向将打印输出到文件&#xff1a;Qt将打印信息输出到文件_qt log输…
阅读更多...
【JavaEE】_HTML常用标签

【JavaEE】_HTML常用标签

目录 1.HTML结构 2. HTML常用标签 2.1 注释标签 2.2 标题标签&#xff1a;h1~h6 2.3 段落标签&#xff1a;p 2.4 换行标签&#xff1a;br 2.5 格式化标签 2.6 图片标签&#xff1a;img 2.7 超链接标签&#xff1a;a 2.8 表格标签 2.9 列表标签 2.10 表单标签 2.10…
阅读更多...
C++继承(二)：菱形继承、virtual菱形虚拟继承

C++继承(二)：菱形继承、virtual菱形虚拟继承

目录 一、了解菱形继承 二、菱形继承的问题 三、虚拟继承virtual 3.1virtual 3.2虚拟继承解决数据冗余和二义性的原理 四、总结/继承和组合 一、了解菱形继承 单继承&#xff1a;一个子类只有一个直接父类时称这个继承关系为单继承 多继承&#xff1a;一个子类有两个或…
阅读更多...
C++重新入门-C++ 函数

C++重新入门-C++ 函数

函数是一组一起执行一个任务的语句。每个 C 程序都至少有一个函数&#xff0c;即主函数 main() &#xff0c;所有简单的程序都可以定义其他额外的函数。 您可以把代码划分到不同的函数中。如何划分代码到不同的函数中是由您来决定的&#xff0c;但在逻辑上&#xff0c;划分通常…
阅读更多...
最新文章

Copyright @ 2022~2023