详解哈希,理解及应用
全文目录
- 概念
- 哈希冲突及原因
- 解决哈希冲突的方法
- 闭散列
- 线性探测
- 二次探测
- 扩容
- 开散列
- 扩容
- 哈希的应用
- 位图
- 布隆过滤器
概念
通过映射关系将关键字映射到存储位置,并实现增删改查操作。
通过上面的方法构造出来的结构就叫哈希表(散列表),其中的映射关系叫做哈希函数
哈希冲突及原因
不同的关键字映射到同一个位置称为哈希冲突
原因:
哈希函数设计得不够合理
哈希函数设计原则:
- 哈希函数的定义域包括所有关键码,散列表的空间位 n,其值域为 [ 0 , m − 1 ] [0,m - 1] [0,m−1]
- 计算出来的地址均匀分布在整个散列表中
- 比较简单
其他类型哈希:
哈希函数需要将关键码进行取模操作,这就表示了当其他类型哈希时需要先将关键字转换为整型 —— 可以通过仿函数进行转换。
解决哈希冲突的方法
解决哈希冲突两种常见的方法是:闭散列和开散列
闭散列
闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。
寻找“下一个”空位置的方法:线性探测和二次探测
线性探测
从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
缺点:
冲突连在一起容易发生数据堆积,不同的关键字占用了可利用的空位置,使得同一个效率下降,影响效率
二次探测
线性探测造成数据堆积的原因是寻找空位置的方式,为了避免数据堆积,二次探测寻找下一个位置的方式为:
: H i = ( H 0 + i 2 ) % m H_i = (H_0 + i^2 ) \% m Hi=(H0+i2)%m, 或者: H i = ( H 0 − i 2 ) % m H_i = (H_0 - i^2 ) \% m Hi=(H0−i2)%m。其中: i = 1 , 2 , 3 … i = 1,2,3… i=1,2,3… , H 0 H_0 H0 是通过散列函数 H a s h ( x ) Hash(x) Hash(x) 对元素的关键码 k e y key key 进行计算得到的位置, m m m 是表的大小。
扩容
当哈希表的载荷因子达到一定大是进行扩容
开散列
开散列法又叫链地址法(开链法),将相同地址的关键字分为一个集合称为桶,通过单链表将桶中的元素链接起来。
扩容
随着插入的增加,冲突的可能性越来越大即一个桶中节点越来越多,影响哈希表的性能。开散列最好的情况是每个哈希桶都只有一个节点,所以当 元素个数 = = 桶的个数 元素个数 == 桶的个数 元素个数==桶的个数 时进行扩容较为合理
哈希的应用
位图
用一个比特位来存放某种状态,用来快速判断某个数据在不在。
模拟实现:
template<size_t N = 100>
class bitset
{
public:bitset(size_t n = N){_bit.resize(N / 8 + 1, 0);}bitset& set(size_t x, bool val = true){size_t i = x / 8;size_t j = x % 8;if (val){_bit[i] |= 1 << j;}else{_bit[i] &= ~(1 << j);}return *this;}bitset& set(){vector<char> tmp(N / 8 + 1, 1);_bit.swap(tmp);return *this;}bitset& reset(){vector<char> tmp(N / 8 + 1, 0);_bit.swap(tmp);return *this;}bitset& reset(size_t x){size_t i = x / 8;size_t j = x % 8;_bit[i] &= ~(1 << j);return *this;}bool test(size_t x) const{size_t i = x / 8;size_t j = x % 8;return _bit[i] & (1 << j);}private:vector<char> _bit;size_t _size;
};
缺点:
一般只能处理整型
布隆过滤器
用来快速检索数据是否存在,弥补位图只能处理整型的缺憾。
原理:
通过多个哈希函数,将一个数据映射到位图结构中。
但是可能对存在的情况存在一定的误判,误判概率取决于哈希函数的个数和空间的大小:参考文档
相关文章:
详解哈希,理解及应用
全文目录 概念哈希冲突及原因解决哈希冲突的方法闭散列线性探测二次探测扩容 开散列扩容 哈希的应用位图布隆过滤器 概念 通过映射关系将关键字映射到存储位置,并实现增删改查操作。 通过上面的方法构造出来的结构就叫哈希表(散列表)&#x…...
解决js加减乘除精度丢失问题
公共类, 将科学计数法的数字转为字符串(以下加减乘除依赖该方法) var toNonExponential (num)> {if(num null) {return num;}if(typeof num "number") {var m num.toExponential().match(/\d(?:\.(\d*))?e([-]\d)/);return num.toFixed(Math.max(0, (m[1] …...
八股——const 关键字
1.const作用 作用:const用于保护指针指向数据不被修改 测试代码1 显示数组的函数不小心修改了指针指向的值,这时候没有加const关键字,编译器不会报错 #include <stdio.h> void showar(int ar[]);int main(void) {int ar[4]{2,3,4,5…...
QT object元对象
qt中的元对象系统提供了对象间通信的信号和槽机制、运行时类型 信息和动态属性系统; 1.该类必须继承自QObject类; 2.必须在类的私有声明区声明Q_OBJECT宏(在类定义时,如果没有指定,public或private,则默认为private&a…...
互斥锁,条件变量,信号量的三个小demo
仨demo 一、 一个线程读文件,另一个线程将读取的内容输出到终端 1.1 要求 创建两个线程,其中一个线程读取文件中的数据,另外一个线程将读取到的内容打印到终端上,类似实现cat一个文件。 cat数据完毕后,要结束两个线…...
【UE 材质】力场护盾和冲击波效果
目录 效果 步骤 一、制作力场护盾材质 二、制作冲击波材质效果 三、制作冲击波粒子效果 四、制作震动效果 效果 步骤 一、制作力场护盾材质 1. 首先新建一个第一人称角色游戏模板 2. 新建一个材质,用于作为力场护盾的材质,这里命名为“Mat_for…...
类和对象三大特性之多态
全文目录 虚函数虚函数的重写接口继承和实现继承重载、重写(覆盖)、隐藏(重定义)C11 override 和 final抽象类 多态的概念多态原理虚函数表 单继承和多继承的虚函数表打印虚函数表单继承的虚函数表多继承的虚函数表 常见面试问答题…...
为何红黑树在B/B+树之上仍然占据重要地位?
为何红黑树在B/B树之上仍然占据重要地位? 引言二、红黑树和B/B树的基本原理2.1、红黑树的特点和性质2.2、B/B树的特点和性质2.3、红黑树和B/B树的比较 三、B/B树相对于红黑树的优势四、红黑树仍然占据重要地位的原因总结 博主简介 💡一个热爱分享高性能服…...
【算法专题突破】滑动窗口 - 水果成篮(13)
目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 1. 题目解析 题目链接:904. 水果成篮 - 力扣(Leetcode) 题目有很长一段话,但是我们读一遍题目可以提炼转化出题目的要求 : 其实就是找出一个最长…...
Peppercontent.io:人工智能驱动的内容生成工具
【产品介绍】 名称 Peppercontent.io 成立时间 成立于2017年 具体描述 Peppertype.ai 是一种基于GPT-3的AI辅助工具,而GPT-3则是一种深度学习自回归语言模型。这一技术潜藏着巨大的潜力,可以立刻为企业和创作者提供创意内容&…...
docker镜像管理-实操
一.docker镜像管理 1.拉取镜像 docker image pull <repository>:<tag> 镜像名称和标签使用 : 进行分隔,如果省略了标签,则默认为 latest docker image pull nginx:latest 或者docker pull nginx:latest 拉取下来的镜像默认保存在࿱…...
SpringMVC-----JSR303以及拦截器
目录 JSR303 什么是JSR303 JSR303的作用 JSR303常用注解 入门使用 拦截器是什么 拦截器的工作原理 拦截器的作用 拦截器的使用 JSR303 什么是JSR303 JSR303是Java为Bean数据合法性校验提供给的标准框架,已经包含在JavaEE6.0中1。 JSR303通过在Bean属性中标…...
基于若依框架实现markdown在线编辑
基于若依框架实现markdown在线编辑 1. 下载mavon-editor npm install mavon-editor --save2. 打开main.js文件, 添加如下 // markdown组件 import { mavonEditor } from "mavon-editor"; import "mavon-editor/dist/css/index.css";// markdown组件 Vue…...
CentOS7上从0开始搭建Zookeeper集群
CentOS7上搭建Zookeeper集群 环境准备安装jdk安装zookeeper下载zookeeper解压zookeeper修改zookeeper配置文件 搭建zookeeper集群修改zoo.cfg文件添加myid文件启动zookeeper集群 环境准备 首先你需要准备三台zookeeper(待会会讲zookeeper的安装流程)&am…...
康耐视读码器DataMan软件详细使用步骤
1、 点击桌面已经安装好的 dataman 软件并打开 2、 打开之后,点击刷新,刷出来读码器的图标,双击进行连接,或者选中后,点击右下角 的连接。(也可先进行第 9—(2)步更改读码器的 IP,对应的连接对象也更改到同一网 段)如图 3、 连接之后,在设置 快速设置下面把实时显…...
408强化(番外)文件管理
有点看不下去书,408,哎好久没看了,死磕数学时完全不想看其他科目,数学分数也尚未质变。 突然想到一个好点子,只看大纲尝试回忆一下这章的内容。 文件就是为了方便用户使用,按名访问而提出的,从…...
iptables 防火墙配置
文章目录 iptables 防火墙配置规则链的分类–五链处理的动作iptables 常用参数和作用iptables 防火墙配置查看规则链清空规则链设置默认规则将流入的流量丢弃允许ICMP协议流量通过删除默认策略允许所以流量通过设置将所有流入22端口的流量全部拒绝允许指定网段的22端口通过设置…...
面试官:我们深入聊聊Java虚拟机吧
哈喽!大家好,我是奇哥,一位专门给面试官添堵的职业面试员 文章持续更新,可以微信搜索【小奇JAVA面试】第一时间阅读,回复【资料】更有我为大家准备的福利哟! 文章目录 前言面试Java虚拟机内存模型垃圾收集器…...
【电源专题】案例:异常样机为什么只在40%以下电量时与其他样机显示电量差异10%,40%以上电量差异却都在5%以内。
本案例发生在一个量产产品的测试中,因为产品带电池,所以需要测试产品对于电池电量显示的精确程度。产品使用的是最简单的开路电压查表法进行设计。 案例测试报告的问题在于不同样机之间电量百分比存在差异,大部分是在3%~4%之间。但在7.2V电压时,能够差异10%左右。 在文章:…...
React 全栈体系(七)
第四章 React ajax 一、理解 1. 前置说明 React本身只关注于界面, 并不包含发送ajax请求的代码前端应用需要通过ajax请求与后台进行交互(json数据)react应用中需要集成第三方ajax库(或自己封装) 2. 常用的ajax请求库 jQuery: 比较重, 如果需要另外引入不建议使用axios: 轻…...
NVIDIA 显卡硬件支持的精度模式
很多炼丹师不知道自己英伟达显卡支持哪些精度模式,本文整理了NVIDIA官网的数据,为你解开疑惑。 1. 首先了解CUDA计算能力及其支持的精度模式; 2. 查看自己显卡(或其它NVIDIA硬件)的计算能力值为多少。 表1 CUDA计算…...
【Java|golang】210. 课程表 II---拓扑排序
一、拓扑排序的定义: 先引用一段百度百科上对于拓扑排序的定义: 对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序,是将 G 中所有顶点排成一个线性序列,使得图中任意一对顶点 u 和 v ,若边 <…...
STM32CubeMX systick bug?
发觉用新版(V6.9.1)的它生成代码,会有问题。可能是 BUG。具体如下: 一个简单的点灯程序,用 Keil MDK 5.38a(compiler version 6)编译。 如果在变量前,不加上关键字“volatile”&am…...
徐亦达机器学习:Kalman Filter 卡尔曼滤波笔记 (一)
P ( x t P(x_t P(xt| x t − 1 ) x_{t-1}) xt−1) P ( y t P(y_t P(yt| x t ) x_t) xt) P ( x 1 ) P(x_1) P(x1)Discrete State DM A X t − 1 , X t A_{X_{t-1},X_t} AXt−1,XtAny π \pi πLinear Gassian Kalman DM N ( A X t − 1 B , Q ) N(AX_{t-1}B,Q)…...
Java和vue的包含数组组件contains、includes
List<String> tempList Arrays.asList("10018","1007","10017","1012"); if(tempList.contains(initMap.get("asset_type_id").toString())){// todo 计算运营终点桩号-起点桩号BigDecimal diffSum collectNum(col…...
OpenCV_CUDA_VS编译安装
一、OpenCV 我这里是下载的OpenCV4.5.4,但是不知道到在vs里面build时一直报错,后面换了4.7.0的版本测试,安装成功。 Release OpenCV 4.5.4 opencv/opencv GitHub 这个里面有官方预编译好的OpenCV库,可以直接食用。 扩展包&am…...
基于减法优化SABO优化ELM(SABO-ELM)负荷预测(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
记录第一个启动代码的诞生
核使用R52,参考汇编模板,一步一步来实现。 首先是ld文件,这个没啥好说的,主要是关注给vector_table划一块地址、stack地址,如下: .text.intvec :{_vectors_start .;KEEP(*(.text.intvec))_vectors_end .;…...
基于STM32的简化版智能手表
一、前言 本文的OLED多级菜单UI为一个综合性的STM32小项目,使用多传感器与OLED显示屏实现智能终端的效果。项目中的多级菜单UI使用了较为常见的结构体索引法去实现功能与功能之间的来回切换,搭配DHT11,RTC,LED,KEY等器…...
揭秘弹幕游戏制作
最近好多人问弹幕游戏,甚至是招人的也要DOTS做弹幕游戏... 实际上目前的弹幕游戏绝大多数应该和DOTS没有半点关系,别忘了DOTS这项技术渲染问题还没能够被合理解决呢 所以目前用的全都是GPU Instance这项技术,于是乎我决定下场写这篇帖子&am…...
做静态网站怎样让图片自己切换/b站推广网站2022
这边我们使用的到的知识点是 线程加锁、等待、通知执行 一、synchronized来实现 synchronized (lock) 给代码块加锁 lock.notifyAll(lock) 通知其他线程执行 lock.wait(lock)当前线程等待 // notify, notifyAll 需要和synchronized联合使用 Testpublic void method9() {/…...
长沙疫情最新情况通报/seo短期课程
C语言基础课程 第一课 Linux环境配置小实战httpserver首先环境需要的是redhat虚拟机操作系统打开redhat 防火墙2.将WWW(HTTP)勾选上3.点击apply 点击是4.切换到root用户输入正确的root密码5. 启动http服务6.输入ifconfig 查看当前ip痛7.通过分析我们知…...
剑三做月饼活动网站/关键词三年级
Binding context binding context是一个保存数据的对象,你可以在你的绑定中引用它。当应用绑定的时候,knockout自动创建和管理binding context的继承关系。这种层次结构的根引用你指定的viewModel参数(ko.applyBindings(viewModel)࿰…...
wordpress网站有多大/举出最新的网络营销的案例
Windows设置静态ip 2018-07-17 09:02:49 ViJayThresh 阅读数 1401更多 分类专栏: 计算机相关 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.…...
网站开发 教学目标/网络营销方案策划论文
在许多用户呼吁多年后微软终于要为网页版的Outlook邮箱服务提供SMTP 邮件代发让用户可以以别名发送邮件。邮件代发是许多企业级用户可能经常使用的功能,这个功能可以让对外发送的邮件统一使用某个特定的邮箱地址。当用户点击发件人邮箱地址时通常会显示代发地址和实…...
企业形象网站怎么做/武汉抖音seo搜索
高德地图开发申请KEY的时候需要开发者提供SHA1证书指纹数据,在eclipse很容易就找到了,但是Android Studio很久也没找到,只能使用在网上看到的方法了,在Android Studio中的Terminal中使用keytool获取了,具体如下图所示&…...