线性哈希：分裂指针与溢出链

形式陈述

同一阶段有些桶已拆，有些还没拆

哈希表需要把键映到候选桶并处理碰撞；线性哈希让主桶数一次只增加1。采用外存页模型，每个主桶页最多放C条定长记录，额外记录串入该主桶专属的溢出页，每溢出页容量同为C。单线程完成更新，无并发、事务版本和崩溃；精确同键put覆盖，只有不同键插入才增加记录数。

设初始主桶数 $N_0\ge1$ ，当前阶段号 $\ell\ge0$ ，阶段基数 $N=N_0 2^\ell$ ，分裂指针 $s\in[0,N)$ 。当前主桶编号恰为 $0,1,\ldots,N+s-1$ ，共 $N+s$ 个。固定非负哈希值H(k)，先计算

a=H(k)\bmod N.

若 $a<s$ ，该基础桶本阶段已经拆过，再令 $a=H(k)\bmod2N$ ；否则沿用a。于是 $[0,s)$ 的旧桶与 $[N,N+s)$ 的新桶用模2N寻址， $[s,N)$ 尚未分裂的桶仍用模N。[1, §2.1]

一次增长只拆指针指向的桶

每次增长选中的都是桶s，未必是刚发生溢出的桶。处理过程如下：

新建主桶 $N+s$
读取桶s的整个主桶与溢出链，按模2N把记录分到s或 $N+s$ ，重新装入各自分页链
令 $s\leftarrow s+1$ ；若变成N，则本阶段全部拆完，令 $\ell\leftarrow\ell+1,s\leftarrow0$ ，新阶段基数为2N

哈希恒等式 $x\bmod2N\in\{x\bmod N,(x\bmod N)+N\}$ 保证桶s中的记录只会去这两个位置；其他桶无需全表搬迁。本文的触发策略固定为：新记录插入后若落在主桶容量以外的溢出部分，就执行一次上述分裂。负载阈值或其他增长时机也可选，但会得到不同轨迹。[1, §§2.1、2.3.1]

收缩是一次分裂的逆操作

删除记录本身不强制收缩。若另有策略要求收缩且主桶数大于初始 $N_0$ ，可以逆转最后一次分裂：s>0时，将最后桶 $N+s-1$ 的整个链合入桶 $s-1$ ，再令s减一；s=0时，先把阶段退一层，基数变N/2，并按上一阶段的最后一次分裂逆向合并。

合并可能重新形成溢出链，并不要求所有记录塞回一个主桶页。释放的是最后主桶的身份与相应整理后的空页，不能把仍有记录的溢出页直接丢掉。增长和收缩阈值应分开，避免少量插删反复触发同一拆合；本页只规定一次结构变换，不给工作负载无关的自动最优阈值。

直觉

用顺序分裂省下一张大目录

可扩展哈希让哪个桶拥挤就拆哪个桶，因此要用目录记住各块已经看到了几位。线性哈希按0、1、2……的固定顺序拆，一个指针就能记住进度。

省下目录的代价是：发生溢出的桶可能暂时轮不到。新记录先留在它的溢出链里，系统去拆别的桶；以后轮到它时，再把整个链重新分配。因此“执行了一次分裂”和“这次碰撞马上消失”没有必然等号。

N为4且s为1时，0已经分为0与4，1仍按模4寻址并保留四条记录的溢出链 — 分裂进度与两个取模范围

例子与边界

同一组键，溢出桶和被拆桶并不同

取 $N_0=2,C=2,H(k)=k$ ，依次插入5、9、1、3、7、13。桶内保持插入顺序，分页时每两条一页；这只是方便复算的桶内布局。

新插入	寻址后的目标	是否进入溢出部分	本次拆桶	更新后N、s	关键内容
5	1	否	—	2、0	桶1=[5]
9	1	否	—	2、0	桶1=[5,9]
1	1	是	0	2、1	0拆成0/2，均空；桶1仍[5,9,1]
3	1	是	1	4、0	模4重分：桶1=[5,9,1]，桶3=[3]
7	3	否	—	4、0	桶3=[3,7]
13	1	是	0	4、1	0拆成0/4，均空；桶1=[5,9,1,13]

最终有5个主桶0至4。桶1主页面[5,9]，溢出页[1,13]；桶3一页[3,7]；其余主桶为空。记录总数6，实际数据页是5个主桶加1个溢出页，共6页。不能只按“6条/每页2条=3页”忽略空主桶与哈希分布。

查询13时，先 $13\bmod4=1$ ，而 $1\not< s=1$ ，所以保留桶1。若无条件改用 $13\bmod8=5$ ，会访问尚未建立的主桶5。查询4则先 $4\bmod4=0<s$ ，需要第二次取模得到4，不能仍去旧桶0。

下次拆到热点，也未必消灭全部溢出

继续插17，先进入桶1的溢出部分，触发拆s=1。按模8重分整条链：9、1、17进入桶1；5、13进入新桶5。更新为N=4、s=2。原溢出记录13这次终于搬到自己的新主桶，桶1却仍有3条，依然需要一个溢出页。

如果只重分桶1主页[5,9]而忘掉链中的1、13、17，查询会依据新地址去桶5找13，却找不到。扩展寻址规则时，必须一起处理原桶承担的全部记录，而不是只处理第一页。

撤回一次增长不等于删除记录

在六键终态N=4、s=1，执行一次受控收缩会把最后桶4合回0，回到N=4、s=0，字典不变。再收缩一次，就逆转上一阶段最后拆桶1的动作：基数退为2，s设为1，把桶3合入桶1，留下0、1、2三个主桶。桶1此时有全部六个奇数键，需要3页；查找正确，但长链成本变大。

这种结构收缩可以在没有删除任何记录时执行，只是通常不利于性能。自动策略必须看自己的容量、负载或延迟目标，不能把“逆操作存在”当成“此时应该执行”。

推论与应用

两级取模为什么总指向已存在桶

设 $a=H(k)\bmod N$ 。如果 $a\ge s$ ，它落在尚未拆的主桶区间 $[s,N)$ ，一定存在。若 $a<s$ ，模2N只能得到a或a+N：前者是已经拆过的旧桶，后者小于 $N+s$ ，也是已经分配的新桶。因此合法元数据不会算出未来桶。

分裂桶s只改变基础余数等于s的键，并使新地址 $N+s$ 刚好成为下一个存在的主桶；随后指针推进扩大“已拆”区间。阶段结束时s=N，所有基础桶都使用模2N；把基数加倍、s归0，恰好表达同一分区，不会突然改变任何记录的归属。

小元数据不等于最坏常数访问

N与s可以放在常驻元数据中，寻址至多两次取模；但找到主桶后仍须比较键并遍历溢出页。若某桶共有q条记录，紧凑分页链最多需 $\max(1,\lceil q/C\rceil)$ 页访问来证明缺失，找到目标可能提前停止。对抗性哈希或完整哈希碰撞可让q很大，不能无条件声称一次页读或最坏常数查找。

一次分裂重分的是桶s的q条记录，读取原链、写两个新链，记录处理为 $O(1+q)$ ，数据页工作为 $O(1+q/C)$ ，另计分配与元数据持久化。它避免了每次都搬全部记录，但并没有保证被拆链永远很短。检查器额外排序快照和全表核对不变量，成本另计，不属于这份局部核心界。

主桶编号仍需映射到实际文件页或缓冲页；“没有哈希目录”只指不保存逐哈希前缀的 $2^g$ 份路由指针，不意味着页分配和物理地址转换免费。原论文§2.2也专门区分连续分配与分块地址映射。

选结构时先看查询任务

这两种动态哈希都适合按完整键等值定位，哈希桶编号没有键序含义。按键范围输出仍可复用B+树的有序叶链；也不能把本页按固定次序拆桶的“线性”，误读为开放定址的线性探测。

参考资料

[1] Witold Litwin，Linear Hashing: A New Tool for File and Table Addressing，VLDB 1980，pp.212–223，§2.1在pp.213–215定义分裂函数、固定分裂顺序及寻址；§2.2在pp.215–216讨论物理页地址；§2.3.1在p.216讨论触发策略与逆向合并。链接为原刊扫描副本，本文整数例及容量账为自编。

[2] Andy Pavlo，CMU 15-445/645 Fall 2025，Lecture 07: Hash Tables，§5.3，p.4：分裂指针与已拆桶的第二次哈希。本文明确一次触发与溢出分页，避免把策略差异省成同一条轨迹。

形式陈述 ​

同一阶段有些桶已拆，有些还没拆 ​

一次增长只拆指针指向的桶 ​

收缩是一次分裂的逆操作 ​

用顺序分裂省下一张大目录 ​

同一组键，溢出桶和被拆桶并不同 ​

下次拆到热点，也未必消灭全部溢出 ​

撤回一次增长不等于删除记录 ​

两级取模为什么总指向已存在桶 ​

小元数据不等于最坏常数访问 ​

选结构时先看查询任务 ​

反向链接