详解哈希,理解及应用
全文目录
- 概念
- 哈希冲突及原因
- 解决哈希冲突的方法
- 闭散列
- 线性探测
- 二次探测
- 扩容
- 开散列
- 扩容
- 哈希的应用
- 位图
- 布隆过滤器
概念
通过映射关系将关键字映射到存储位置,并实现增删改查操作。

通过上面的方法构造出来的结构就叫哈希表(散列表),其中的映射关系叫做哈希函数
哈希冲突及原因
不同的关键字映射到同一个位置称为哈希冲突
原因:
哈希函数设计得不够合理
哈希函数设计原则:
- 哈希函数的定义域包括所有关键码,散列表的空间位 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: 轻…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
