可扩展哈希目录与局部分裂

形式陈述

目录有多少项，不等于实际有多少桶

沿用哈希表的精确键值查询：哈希只定位候选，桶内仍比较完整键。这里改用按页传输的模型，每个物理桶是一页，可放最多 $C\ge1$ 条定长记录。单线程完成每次操作，无并发和崩溃；唯一键的重复put覆盖原值，不增加条数。

固定哈希 $H(k)$ 给出 $w$ 位非负整数。本文读取低位，全局深度 $g\in[0,w]$ ，目录D有 $2^g$ 个页指针，查询目录下标

j=H(k)\bmod2^g.

每个桶有局部深度 $d\le g$ 和低d位签名s；当d=0时签名为0。该桶恰由所有满足 $j\bmod2^d=s$ 的目录项指向，因此拥有 $2^{g-d}$ 个目录别名。桶内每个键也须满足 $H(k)\bmod2^d=s$ 。目录别名复制的是指针，不是多份记录。[1, §5.2]

溢出时只拆被命中的桶

对目标桶先检查同键覆盖；如果新记录放不下，设原局部深度为d：

若 $d=g$ ，先将目录翻倍并把g加一。低位约定下，新目录满足 $D'[j]=D'[j+2^g]=D[j]$ ，这里右边g是翻倍前的值
分配一个新桶，把原桶和新桶的局部深度改成 $d+1$ ，签名分别为s与 $s+2^d$
按哈希第d位（最低位编号0）重分原桶记录，修正原先指向它的所有目录别名，再重新定位待插入键
若所需桶仍满，继续分裂；一次分裂未必把记录均分，也未必立刻腾出空间

在有限w位模型中，不能让d超过w。若超过C个不同键拥有完全相同的w位哈希值，本页拒绝无法安置的新记录并保留原字典；溢出链、改变哈希或重建是需要另行选择的扩展，不能靠无限增加目录位数解决。

删除后的合并要找真正的同伴

删除精确键后，可以尝试合并局部深度同为 $d>0$ 的两个同伴桶：它们的签名只在第 $d-1$ 位不同，且合计记录数不超过C。合并后深度减一，所有别名都指向保留桶；旧桶不再有引用才能释放。深度不同或合并后超过容量，均不得执行这一合并。

如果g>0且全部桶局部深度都小于g，则目录上、下两半的对应指针相同，可以去掉一半并令 $g\leftarrow g-1$ ，反复缩到不能再缩。本页允许一直缩到g=0的一项目录。合并和缩目录是不同动作：先让桶的划分变粗，目录才能省略不再区分任何桶的最高一位。

直觉

多看一位，是为了只拆热点的一小块

目录像一张按哈希尾号查询的表。某个桶只需要看一位即可区分时，其他更高位的不同目录项仍可以指向它。只有拥挤的那一块需要再看下一位，才增加该桶的局部深度。

局部深度已经追上全局深度时，现有目录没有足够的下标容纳新区别，因此必须加倍目录。加倍不会让所有桶都分裂：冷桶只是多出同一页的别名，热点桶才重新分配记录。

全局深度3的八个目录项指向四个物理桶，其中四项指向同一个深度1的空偶桶 — 目录深度与桶别名数

例子与边界

三个同尾号键连续触发两次分裂

取C=2、w=4、 $H(k)=k\bmod16$ ，初始g=1：下标0指空偶桶，1指空奇桶，二者d=1。依次插入5、9，奇桶装满[5,9]。再插1：

奇桶d=g=1，目录先变成四项。按第二低位拆成签名01和11，但5、9、1的低两位全是01，11桶为空，01仍装不下三条
01桶d=g=2，目录再变成八项。按第三低位拆：5进入101；9、1进入001。这次才全部可放下

原来的偶桶始终没有拆，仍d=1。随后插入3、7、13：3和7进入低两位为11的桶，13进入101桶，得到下表。

目录项（三位）	物理桶签名/深度	完整记录键
000、010、100、110	0 / d=1	空
001	001 / d=3	9、1
101	101 / d=3	5、13
011、111	11 / d=2	3、7

这是8个目录项、4个物理桶、6条记录，不是8个桶。别名数分别为4、1、1、2，恰为 $2^{3-d}$ 。查询13取低三位101，在含5、13的桶中再比较完整键。

哪次删除才能缩目录

先删13，101桶只剩5，但其同伴001还有9、1，合计3条，超过容量2，不能合并。再删9，两个同伴只剩1和5，可以合并为d=2、签名01的桶；此时没有d=3桶，目录从8项缩到4项，g=2。

再删7、3后，11桶为空，可与含1、5的01桶合并成d=1的奇桶；又可与空偶桶合并为d=0。目录最终只剩1项，仍保存键1、5。这里每次合并都核对容量与同伴深度，不能看见一个空桶就任意接到相邻目录项指向的页。

相同哈希和低位偏斜是不同边界

仍取w=4，键1、17、33的完整哈希值都等于1。容量2时第三条无法在本模型中放入，不论目录扩展到哪一位。判断的是完整哈希相同，不是“目前目录下标相同”：前面的5、9、1在低两位相同，但第三位已经可以分开5。

若不同键直到很高位才出现区别，目录可能被少量记录撑得很大。目录规模是 $2^g$ ，并不由“每桶至少有一条”控制，因为某些分裂会产生空桶。不能仅凭桶页数量就承诺目录始终很小。

推论与应用

为什么局部分裂后仍能唯一定位

分裂前，一个签名s覆盖所有低d位等于s的目录项。它们按下一位0/1恰好分成两个互斥、合起来仍完整的集合，对应新签名s和 $s+2^d$ 。记录与目录用同一位分配，原桶内每条记录仍被它自己的目录下标指向；其他桶的记录和指针都无需改变。重复这个局部论证即可处理连续分裂。

目录缩减是反方向：当最高位不再区分不同桶，去掉它不会改变任意键最终命中的页。哈希映射只保证候选桶唯一，最后的键比较仍不能省。

两次页读有明确的地址条件

假定g、哈希参数和目录数组位置已驻留，目录可按下标直接找到一个页指针，桶内记录完整位于一页。冷缓存点查至多读“含目标目录槽的页+桶页”两页；目录已缓存时只需桶页。即使整个目录跨许多页，一次点查也只需目标槽所在页，但前提是这份数组地址可直接定位。[2]

这不是更新成本：目录翻倍要复制 $2^g$ 个指针，若一页容p个指针，就另有 $O(1+2^g/p)$ 目录页传输。一次桶分裂还须读写该桶及新桶、修改受影响的别名。若实现扫描整张目录找这些别名，CPU就要 $O(2^g)$ ；本单元检查器为清楚展示别名，采用这份全目录扫描并另计，不声称恒定插入时间。

线性哈希选择另一条增长路线：用一个分裂指针代替这份幂二目录，但允许溢出链等待轮到自身被拆。两者都必须面对哈希偏斜，不能把某个小输入的均匀结果当成最坏性能保证。

参考资料

[1] Andy Pavlo，CMU 15-445/645 Fall 2025，Lecture 07: Hash Tables，§5.2，p.4：全局/局部深度、分裂与目录翻倍。讲义使用高位表述；本文明确采用低位约定，并逐项推导相应下标、同伴合并与别名不变量。

[2] Ronald Fagin、Jürg Nievergelt、Nicholas Pippenger、H. Raymond Strong，Extendible Hashing—A Fast Access Method for Dynamic Files，ACM TODS 4(3)，1979，pp.315–344，DOI 10.1145/320083.320092。原始方法及其两级访问目标；本文低位算例与明确的页地址条件按教学模型列出，未引用该文未展开的概率界。

形式陈述 ​

目录有多少项，不等于实际有多少桶 ​

溢出时只拆被命中的桶 ​

删除后的合并要找真正的同伴 ​

多看一位，是为了只拆热点的一小块 ​

三个同尾号键连续触发两次分裂 ​

哪次删除才能缩目录 ​

相同哈希和低位偏斜是不同边界 ​

为什么局部分裂后仍能唯一定位 ​

两次页读有明确的地址条件 ​

反向链接