可拓展哈希

可拓展哈希

借CMU 15445的ppt截图来说明问题。

我们传统静态hash的过程是hash函数后直接将值存入对应的bucket,但是在可扩展hash中,得查询Directory(左),存入directory指向的bucket(右)。

在这里插入图片描述

下面我们存放key=B,哈希值为hash(B),查询directory知道要放到第二个bucket中。

在这里插入图片描述

然后再放一个key=C(hash( C)的值被老师的视频挡住了,就不放图片了),哈希值为hash( C),并且hash( C)高两位也是10,查询directory也要放到第二个bucket,但此时bucket满了,就将该bucket分裂,其他bucket不用变动,那么directory应该怎么变动呢?分为两种情况(先说明此时hash( C)对应第2种情况)

  1. bucket的local depth < global depth:分裂bucket,改变directory中指向该bucket的指针,让他们分别指向分裂出来的两个bucket,并且这两个bucket的local depth+1
  2. bucket的local depth = global depth:分裂bucket,将directory的大小*2,并且重新分配directory中的指针(这里不知道怎么描述比较好,可以结合下面的图来理解),并且分裂后的两个bucket的local depth+1,global depth+1

很明显hash©对应上面的情况2,因此结果如下:
在这里插入图片描述

第一种情况在课件中没有提到,我也做一下说明(懒得画图了)。我们先回到这张图,基于现在这个状态分析第一种情况:

在这里插入图片描述

假设现在第一个bucket是满的(我们这里假设bucket中第三个为01…),然后hash©=00…,要插入第一个bucket,那么根据情况1,我们将bucket分裂为两个bucket,directory不用增长,但是00…和01…指针分别要指向第一个分裂的bucket和第二个分裂的bucket,第一个分裂桶存放了两个01…,第二个分裂桶存放了两个00…

如果还是不懂的话,可以多看几遍上述操作过程或者看下面的参考链接

简单的体会总结:可拓展哈希好处在于某个桶分裂的时候,不用移动其他桶的元素,减少开销。存在的问题很明显,如果多次插入的hash值相同,分裂肯定是不可行的,因为无论怎么分裂,这几个相同hash值都在同一个bucket中,因此需要用overflow bucket的方式来“打补丁”了,所以最基本的可拓展哈希算法不能直接拿来用,得做点变种吧,不过思想值得学习。

参考链接:

https://blog.csdn.net/qq_37026934/article/details/125368237

https://www.bilibili.com/video/BV1xa41137S4?p=7&vd_source=65dfb8ffc4e0d60f317dcde5b6ceb9fd

https://zhuanlan.zhihu.com/p/375039823

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ASEMI代理ADI亚德诺LTC6992IS6-1#TRMPBF车规级芯片

编辑-Z LTC6992IS6-1#TRMPBF参数描述&#xff1a; 型号&#xff1a;LTC6992IS6-1#TRMPBF 输出频率&#xff1a;3.81Hz 工作电源电压范围&#xff1a;2.25 - 5.5V 通电复位电压&#xff1a;1.95V 电源电流&#xff1a;105-365A SET引脚处的电压&#xff1a;1V 频率设置电…

物联网|IAR集成开发环境简介|cc254核心板硬件资源|物联网之蓝牙4.0 BLE基础-学习笔记(3)

文章目录 4、IAR集成开发环境简介5、 cc254核心板硬件资源 4、IAR集成开发环境简介 完整稳定的专业嵌入式开发环境&#xff0c;对不同的处理器有统一的用户界面&#xff0c;支持35种以上的MCU&#xff0c;包括8&#xff0c;16&#xff0c;32位&#xff0c; 完全兼容C语言的 高…

FPN和PAN的内容及区别

FPN和PAN都是用于解决在目标检测中特征金字塔网络(FPN)在多尺度检测任务上的不足的方法。下面分别详细介绍一下它们的原理和区别。 FPN FPN全称Feature Pyramid Network&#xff0c;是由FAIR在2017年提出的一种处理多尺度问题的方法。FPN的主要思路是通过构建金字塔式的特征图…

【CSS系列】第四章 · CSS字体属性

写在前面 Hello大家好&#xff0c; 我是【麟-小白】&#xff0c;一位软件工程专业的学生&#xff0c;喜好计算机知识。希望大家能够一起学习进步呀&#xff01;本人是一名在读大学生&#xff0c;专业水平有限&#xff0c;如发现错误或不足之处&#xff0c;请多多指正&#xff0…

人机智能中几个困难问题浅析

1、人机之间与人人之间信任的区别人机之间的信任与人人之间的信任存在以下异同&#xff1a;①信任对象。人机之间的信任的对象是计算机系统、算法、机器人等&#xff0c;而人人之间的信任的对象是其他人。②信任方式。人机之间的信任是基于技术、安全协议等建立的&#xff0c;例…

【Linux网络】传输层中UDP和TCP协议

文章目录 1、再谈端口号2、UDP协议3、TCP协议3.1 TCP协议段格式3.2 TCP的三次握手和四次挥手&#xff08;连接管理机制&#xff09;3.3 TCP的滑动窗口3.4 TCP的流量控制3.5 拥塞控制3.6 延迟应答和捎带应答3.7 面向字节流和粘包问题3.8 TCP总结 1、再谈端口号 端口号port标识一…

2023年前端面试题汇总-代码输出篇

1. 异步 & 事件循环 1. 代码输出结果 const promise new Promise((resolve, reject) > {console.log(1);console.log(2); }); promise.then(() > {console.log(3); }); console.log(4); 输出结果如下&#xff1a; 1 2 4 promise.then 是微任务&#xff0c;它…

1、防刷限流实现1

1、本章诉求 限流的需求出现在许多常见的场景中&#xff1a; 秒杀活动&#xff0c;有人使用软件恶意刷单抢货&#xff0c;需要限流防止机器参与活动某api被各式各样系统广泛调用&#xff0c;严重消耗网络、内存等资源&#xff0c;需要合理限流 2、流程设计 3、方案实现 3.1…

使用 spring 的 IoC 的实现账户的CRUD(2)双层实现

spring实现service和dao的数据的查找 dao层设置接口实现dao层的接口service设置接口通过注入dao层&#xff0c;来实现接口 //dao层的接口&#xff0c;定义了根据id查询的方法 public interface Accountdao {Account findByid(int id); }实现接口&#xff1a;实现了查询的方法 …

项目创建第一天 搭建前端环境

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、环境是什么&#xff1f;二、使用步骤1.前台搭建方式1.创建项目2.目录结构3. 安装elementui4. 创建路由5.使用axios6.bug记录6.1出现跨域问题6.2 解决方式6.…

2023年会展服务研究报告

第一章 行业概况 会展行业是指一系列与会议、展览、展示相关的服务和经济活动的总称&#xff0c;是加强企业间交流、促进合作和推动经济发展的重要手段。该行业涉及广泛&#xff0c;包括会议和展览的组织、场地租赁和设计、活动策划和执行、展品运输和咨询服务等各个环节。随着…

tiechui_lesson03_缓冲读写与自定义控制

学习了与应用层通过缓冲区方式的交互&#xff0c;包括读写&#xff0c;自定义控制等。小坑比较多&#xff0c;大部分是是头文件和设置上的错误&#xff0c;跟着视频敲想快进就跳过了一些细节。包括&#xff1a; <windef.h> 头文件的引用 //使用DWORD等类型switch语句…

基于标签的协同过滤算法实现与个人兴趣相关的文章推荐

一、前言 在当前信息爆炸的时代&#xff0c;每天都会涌现出大量的文章&#xff0c;人们有时候会感到信息的获取难度比筛选更大。而作为信息的提供者&#xff0c;我们应当为用户提供依据个人兴趣的文章推荐。 本项目中的文章标签相似度推荐功能使用了一种基于标签的协同过滤算…

Java版本的工程项目管理系统源代码之工程项目管理系统面临的挑战

​ ​工程项目管理系统是指从事工程项目管理的企业&#xff08;以下简称工程项目管理企业&#xff09;受业主委托&#xff0c;按照合同约定&#xff0c;代表业主对工程项目的组织实施进行全过程或若干阶段的管理和服务。 ​系统定义 工程项目管理企业不直接与该工程项目的总承包…

易视腾iS-E5-NGH_3798MV100_MT7601_卡刷固件包_当贝纯净桌面

易视腾iS-E5-NGH_3798MV100_MT7601_卡刷固件包_当贝纯净桌面 特点&#xff1a; 1、适用于对应型号的电视盒子刷机&#xff1b; 2、开放原厂固件屏蔽的市场安装和u盘安装apk&#xff1b; 3、修改dns&#xff0c;三网通用&#xff1b; 4、大量精简内置的没用的软件&#xff0…

产品经理 - 原型图设计软件

原型图设计软件哪个好用&#xff1f;6款好用软件推荐&#xff01; - 知乎 原型图都可以用什么软件做&#xff1f;11款好用软件分享&#xff01; 摩客, 墨刀 2014 墨刀是A股上市公司万兴科技旗下的在线一体化产品设计协作平台 即时设计是一款支持在线协作的专业级 UI 设计工…

回首来路多感概,最是奋斗动人心。

我们必需要在不同的时代有不同的领悟&#xff0c;才能充满生机地去迎接生命中每个新的开始。 文章目录 前言 初心 成长 收获 憧憬 出发 前言 今天是我成为csdn创作者一周年纪念日&#xff0c;我非常开心能够和大家分享我的写作之旅。在这一年里&#xff0c;我经历了许多挑…

QT QGraphicsView 提升到 QChartView报错 解决方案

QT QGraphicsView 提升到 QChartView报错 解决方案 本文主要描述, 使用QT提供的QChartView来绘制图表,提升QGraphicsView控件继承QChartView后,然后将QGraphicsView提升到我们自己写的类,怎么才能确保提升后编译不报错. [问题描述] 使用QGraphicsView显示图表的时候,我们需要将…

基于 TiDB + Flink 实现的滑动窗口实时累计指标算法

作者&#xff1a;李文杰 前言 在不少的支付分析场景里&#xff0c;大部分累计值指标可以通过 Tn 的方式计算得到 。随着行业大环境由增量市场转为存量市场&#xff0c;产品的运营要求更加精细化、更快速反应&#xff0c;这对各项数据指标的实时性要求已经越来越高。产品如果能…

WRF模式

随着生态文明建设和“碳中和”战略的持续推进&#xff0c;我国及全球气候变化及应对是政府、科学界及商业界关注的焦点。气候是多个领域&#xff08;生态、水资源、风资源及碳中和等问题&#xff09;的主要驱动因素&#xff0c;合理认知气候变化有利于解释生态环境变化机理及过…