首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >磁盘哈希结构-Linear Hashing

磁盘哈希结构-Linear Hashing

作者头像
Orlion
发布于 2024-09-02 08:38:48
发布于 2024-09-02 08:38:48
16300
代码可运行
举报
文章被收录于专栏:我的独立博客我的独立博客
运行总次数:0
代码可运行

1. Linear Hashing

最近在思考一个问题,如果一个存储引擎不需要支持范围查询,那么使用hashtable这样的数据结构是否更合适?恰好看到了lotusdb中使用了一个diskhash的库,从源码看是使用了一种Linear Hashing的哈希表数据结构,由于磁盘与内存的特性不同,因此磁盘哈希结构与常见的内存hashtable不太一样,特意研究了下。

2. 数据结构

通过primaryFile文件来存储hash桶,每个桶上有slotsPerBucket个槽,每个槽存储一个KV对,桶的数量为2 ^ Level个。当所有槽都用完时,在overflowFile中创建溢出桶,并通过nextOverflow记录新创建的溢出桶在文件中的offset。

初次创建时,会将Level初始化为0,SplitBucketIndex为0,然后创建出primaryFile并初始出一个桶

3. Put

写入过程如下: * 计算key的hash,然后hash对桶数量取模计算出key所在的桶

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
bucketIndex := keyHash & ((1 << t.meta.Level) - 1)
  • 遍历bucketIndex对应的桶以及该桶所有溢出桶上的所有slot,寻找key对应的槽
    • 如果找到则原地更新
    • 如果没有找到说明这是一个新key,则在第一个空槽上插入
    • 如果是新key且没有空槽,这时就需要创建一个溢出桶出来
  • 如果是新增key,需要判断下当前的负载因子是否超过阈值,超过阈值需要进行扩容

3.1 创建溢出桶

一般情况下溢出桶的创建是通过调用File.Truncate()扩容实现的,这里还有个逻辑是在hashtable进行扩容时,有些溢出桶不再使用可以被释放,这些溢出桶会被缓存下来,在创建溢出桶复用这些被释放的溢出桶。

4. 扩容

Linear Hashing的扩容是其核心部分,与内存hashtable常见的扩容策略有所不同,这里重点解释下

4.1 扩容时机

每当新增key之后都会重新计算当前的负载因子,负载因子的计算公式如下

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
keyRatio := float64(t.NumKeys) / float64(t.NumBuckets*slotsPerBucket) // slotsPerBucket是一个常量

即KV对的数量除以槽的数量。当负载因子超过阈值(默认是0.7)时触发扩容

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
if keyRatio > t.options.LoadFactor {
	t.split()
}

4.2 扩容过程

Linear Hashing维护一个指针SplitBucketIndex,每次扩容时就拆分这个指针指向的桶。

拆分前会将存储桶的文件扩大一个桶的大小,即增加一个桶。拆分时遍历旧桶所有槽,重新计算槽所在的位置,然后迁移到新桶上。

然后将SplitBucketIndex加1指向下一个桶,加完之后如果溢出了则将SplitBucketIndex归零,这时还要将Level+1,即标识桶数量翻倍。

5. 删除

删除过程比较简单,首先计算key的hash,然后取模计算出所在的桶,遍历桶上所有槽,如果找到槽则将槽置为空,然后写回磁盘

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-08-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——14.哈希(2)(模拟实现)
开散列(Open Hashing),也叫链地址法,是一种解决哈希冲突的方法。每个哈希表槽位保存一个链表,所有散列到同一位置的元素都存储在该链表中。当插入元素发生冲突时,将新元素添加到相应槽位的链表末尾。
hope kc
2024/10/22
1340
移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——14.哈希(2)(模拟实现)
Java集合详解4:一文读懂HashMap和HashTable的区别以及常见面试题
《Java集合详解系列》是我在完成夯实Java基础篇的系列博客后准备开始写的新系列。
Java技术江湖
2019/10/11
9140
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
十一、为什么我们需要hash()函数 (n-1)\&hash,而不是直接用key的hashcode直接计算下标
寻求出路的程序媛
2024/10/17
9410
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
Golang map 三板斧第三式:实现原理
Go map 底层实现方式是 Hash 表(C++ map 基于红黑树实现,而 C++ 11 新增的 unordered_map 则与 Go map 类似,都是基于 Hash 表实现)。Go map 的数据被置入一个由桶组成的有序数组中,每个桶最多可以存放 8 个 key/value 对。key 的 Hash 值低位用于在该数组中定位到桶,而高 8 位则用于在桶中区分 key/value 对。
恋喵大鲤鱼
2020/11/12
7.4K0
Golang map 三板斧第三式:实现原理
剖析Java中HashMap数据结构的源码及其性能优化
存储结构 首先,HashMap是基于哈希表存储的。它内部有一个数组,当元素要存储的时候,先计算其key的哈希值,根据哈希值找到元素在数组中对应的下标。如果这个位置没有元素,就直接把当前元素放进去,如果有元素了(这里记为A),就把当前元素链接到元素A的前面,然后把当前元素放入数组中。所以在Hashmap中,数组其实保存的是链表的首节点。下面是百度百科的一张图:
凯哥Java
2019/06/30
5680
文心一言 VS 讯飞星火 VS chatgpt (242)-- 算法导论17.4 1题
一、假定我们希望实现一个动态的开地址散列表。为什么我们需要当装载因子达到一个严格小于 1 的值 a 时就认为表满?简要描述如何为动态开地址散列表设计一个插入算法,使得每个插入操作的摊还代价的期望值为 O(1) 。为什么每个插入操作的实际代价的期望值不必对所有插入操作都是 O(1) ? 如果要写代码,请用go语言。
福大大架构师每日一题
2024/04/25
2010
文心一言 VS 讯飞星火 VS chatgpt (242)-- 算法导论17.4 1题
【C++进阶】hash表的封装
哈希表是一种数据结构,它通过将键映射到存储桶或槽来快速查找数据。它的核心思想是通过一个哈希函数(Hash Function)将输入数据(键)转换为数组中的索引,以便在常数时间内进行查找、插入和删除操作。
用户11305458
2024/10/09
1660
【C++进阶】hash表的封装
【C++进阶学习】第十弹——哈希的原理与实现——链地址法的原理与讲解
开放地址法:【C++进阶学习】第九弹——哈希的原理与实现——开放寻址法的讲解-CSDN博客
GG Bond1
2024/08/05
4610
【C++进阶学习】第十弹——哈希的原理与实现——链地址法的原理与讲解
Java数据结构-------Map
    1)无序; 2)访问速度快; 3)key不允许重复(只允许存在一个null Key);
在周末
2019/09/11
1.4K0
真希望你也明白runtime.Map和sync.Map
One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.
面向加薪学习
2022/12/13
4090
真希望你也明白runtime.Map和sync.Map
穿越数据迷宫:C++哈希表的奇幻旅程
在C++的世界中,哈希表是一种高效、独特的数据结构,被广泛应用于需要快速查找、插入、删除的场景。通过哈希函数将数据映射到表中,它不仅提高了操作效率,还在解决冲突时展现了精巧的设计。哈希表在算法的应用中尤为重要,无论是缓存、字典处理还是集合操作,都离不开它的身影。本篇博客将带你一步步深入理解哈希表的实现原理及其应用,让你在编码之路上更上一层楼。
suye
2024/11/19
2590
哈希表
哈希表的英文叫 “Hash Table”,我们平时也叫它 “散列表” 或者 “Hash 表”。
硬件开源小站
2023/04/07
1.2K0
哈希表
go哈希
哈希查找表一般会存在“碰撞”的问题,就是说不同的 key 被哈希到了同一个 bucket。一般有两种应对方法:链表法和开放地址法。链表法将一个 bucket 实现成一个链表,落在同一个 bucket 中的 key 都会插入这个链表。开放地址法则是碰撞发生后,通过一定的规律,在数组的后面挑选“空位”,用来放置新的 key。
Michel_Rolle
2023/11/06
3.1K1
初识C++ · 哈希表
哈希,部分说法叫散列,在编程里面哈希是一种思想,即一种映射,像数学函数一样,每个不同的值对应每个不同的值,数学里面使用函数来实现哈希,即值映射,但是在C++里面,我们可以使用不同的对象来映射不同的值,今天介绍的是用整型 自定义类型(string)来介绍哈希。
_lazy
2024/10/16
1380
数据结构之哈希表
哈希表的英文叫“Hash Table”,我们平时也叫它“散列表”或者“Hash 表”,是一种常用的数据结构。Java中的HashMap、HashTable就是基于哈希表实现的。
端碗吹水
2021/01/22
7470
看完这篇 HashMap ,和面试官扯皮就没问题了
「如果你没有时间细抠本文,可以直接看 HashMap 概述,能让你对 HashMap 有个大致的了解」。
cxuan
2020/06/28
5910
看完这篇 HashMap ,和面试官扯皮就没问题了
哈希
我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个数组,为每个可能的关键字保留一个位置,就可以应用直接寻址技术。 哈希表(Hash Table)是普通数组概念的推广。当实际存储的的关键字数比可能的关键字总数较小时,这时采用哈希表就会比使用直接数组寻址更为有效。因为哈希表通常采用的数组尺寸与所要存储的关键字数是成比例的。 哈希表是一种动态集合数据结构,在一些合理的假设下,在哈希表中查找一个元素的期望时间是 O(1) 。
对弈
2019/09/04
1.2K0
哈希
【数据结构进阶】哈希表
之前我们学习了红黑树,其虽然通过自平衡机制提供了高效的查找、插入和删除操作,但其操作仍依赖于树的高度,最坏情况下的时间复杂度为O(log n)。当我们希望能够实现常数时间复杂度的查找操作时,哈希表便成为了一个更优的选择。哈希表虽然不再像红黑树的元素一样默认有序,但其通过 “ 哈希 ” 将数据进行映射,从而在理想情况下实现O(1)时间复杂度的操作,在某些需要高效查找的场景非常实用。本篇文章,我们将深入学习哈希表的相关知识,并尝试实现。
ephemerals__
2025/02/25
1840
【数据结构进阶】哈希表
迟到一年HashMap解读
HashMap和List这两个类是我们在Java语言编程时使用的频率非常高集合类。“知其然,更要知其所以然”。HashMap认识我已经好多年了,对我在工作中一直也尽心尽力的提供帮助。我从去年开始就想去它家拜访来着,可是经常因为各种各样的原因让其遗忘在路过的风景中。(文章大部分源码基于jdk1.7)。
静默加载
2020/05/29
4430
C++寻位映射的奇幻密码:哈希
哈希,用于将任意大小的数据映射为固定长度的数值(哈希值),这个过程通过哈希函数实现,其核心目标是高效地存储、查找和验证数据
DARLING Zero two
2025/05/20
1270
C++寻位映射的奇幻密码:哈希
相关推荐
移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——14.哈希(2)(模拟实现)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验