原文来自Extendible Hashing。
Extendible Hashing是一个动态哈希算法,利用一个目录(directories)和许多buckets(类似page,页,下面统称为叶结点,叶)被用来hash映射数据。这是一种灵活的方式,hash函数,hash表都经历了动态变化。
Extendible Hashing 有两个主要的部分
- 目录(Directories): 即我们的哈希数组,目录的一个slot(即一个元素,下标)存储一个指向叶的地址的指针。还有一个id被分配给每个目录项,当目录扩张的时候,id就会发生改变。
- 叶(bucket): 桶用来存储散列后的数据(hash(key)和对应的value)
算法的组成结构(Basic Structure of Extendible Hashing):
该算法主要组成部分:
- 目录(Directories): 用来存储指向叶的指针。每个目录项都有一个独特的id(被拆分为位运算的形式),id会在目录扩张的时候发生改变(详解在下方)。哈希函数会返回一个目录项的id,被用来导向到合适的叶节点中。目录项的总数 = 2^Global Depth;
- 叶(Buckets): 用来存储hash(key)。目录项会指向这些叶。叶由两部分组成
- 头节点(header): 用来存储Local Depth。
- 记录(tuple): 叶结点中包含了多个指针,用来存储数据:hash(key)和value
- 全局计数器(Global Depth): 和目录相关。目录项的id被表示为位运算的形式,位运算的最大可用位数 = Global Depth。通过hash(key)的前Global Depth位来找到对应的目录项,并放入对应的叶中。
- 局部计数器(Local Depth): 和全局计数器的概念相同,但是局部计数器和叶相关而不是和目录相关。局部计数器 = max(1,最后一次分裂时的全局计数器)。当叶发生溢出时,且局部计数器 = 全局计数器,此时目录就发生了扩张。
- 叶分裂(Bucket Splitting): 当叶中的元素个数超过了给定的元素个数,发生叶溢出和叶分裂(叶已经满了,仍然还要往里面插入,此时叶结点分裂,局部计数器++)。
- 目录扩张(Directory Expansion): 当叶结点溢出时且Local Depth = Global Depth,发生了目录扩张。
算法的工作流程(Basic Working of Extendible Hashing: ):
- 分析数据类型: key可能有多种数据类型。integer,string,float,etc…。对于不同的数据类型,哈希映射的方式不同。
- 转化为二进制: 将hash(key)转化为二进制的形式,对于string来说,会考虑他的acsii码值
- 检查Global Depth: 检查目录的全局计数器。
- 目录项id转化为二进制形式: 根据Global Depth,生成
0 ~ 2^(Global Depth) - 1所有的值,例如Global Depth = 3, 此时hash(key) = 9,9转化为2进制 = 1001,我们只会看前三位,即100,通过100找到对应的目录项id - 找到目录项id: 根据位运算表示的前Global位,找到对应的目录项id
- 插入并检查溢出: 通过找到的目录项,得到指针后,进入对应的叶,插入数据,检查是否溢出,如果溢出了,执行步骤7和8,否则的话,只需要执行9
- 解决溢出情况: 许多情况下,在叶中插入一个数据,可能会发生叶的溢出。在这种情况下,需要核实的步骤来防止数据的丢失和出错。首先,检查局部计数器,分为两种情况进行讨论
- 局部计数器 = 全局计数器: 那么将发生 页面扩张 和 叶分裂。让 全局计数器++ 和 局部计数器++,重新分配页目录指针(这里重新分配是局部的,只会重新分配出现叶溢出的部分,在实例中分析。)
- 局部计数器 < 全局计数器: 让局部计数器++,并且重新分配页目录指针
- 重新哈希映射叶元素: 局部重新构建。将发生溢出的叶结点中的元素,全部重新hash映射,并分配到对应的叶结点中。只对于发生溢出的才需要重新构建,没有发生溢出的叶不会发生改变,
- 所有元素重新哈希完毕。
实例
这个实例来自于cmu15-445的课上案例。
此时global = 2,插入A,A的前两位 = 01,因此插入到01对应的叶结点中。
global = 2,插入B,B的前两位 = 10,因此插入到10对应的叶结点中。
global = 2,插入C,C的前两位 = 10,因此插入到10对应的叶结点中,可以看到此时发生了叶溢出,global = local,所以需要 目录扩张 + 叶分裂
我们只需要重新构建发生溢出的叶结点,原来的叶结点变为两个,其中100,101分配映射到两个不同的叶结点,这时候就可以插入C了(如果此时还发生溢出,就需要继续分裂)
