x-fast 与 y-fast Trie

X-fast 为所有深度建立哈希入口，把逐位导航变成对长度的二分；代价是每个键可能贡献 $w$ 个前缀。Y-fast 让约 $w$ 个相邻键共享一个代表，再到小桶中完成最后的比较，从而用少量索引加桶内存储覆盖全部键。

这两层分担不同职责。代表层定位区间，桶内树查真实记录；分隔值即使刚从数据中被删除，也可以继续担当原来的区间边界。这样才不会因每次删除一个边界记录，都立即重写其 $w$ 个哈希前缀。

最长存在前缀 ​

查询八位键 ${10110100}_2$，若前缀 $1011$ 存在、$10110$ 不存在，则不存在的更长前缀也不必再试。最长前缀节点说明下一位想走0支，但该支缺失；从它的最小叶及前一叶就可定位相邻键。这里查的是前缀集合，不是对各层哈希表的物理桶号二分。

路由边界与真实答案 ​

设两个桶覆盖 $[0,15]$ 与 $(15,31]$，当前分别含 $\{3,8,15\}$ 与 $\{20,27\}$。删除记录15后，可以仍保留路由边界15；查询15进入第一桶并返回8，查询18进入第二桶，但桶中没有不大于18的键，于是返回前桶最大值8。

若直接把边界15当作前驱答案，就会返回一个已经删除的键。边界身份、桶的实际成员及叶链次序必须分别维护。

成本的概率与参数 ​

$\log w$ 也可写成 $\log \log U$，但只有明确 $U$ 与 $n$ 的关系后，才可改写成 $\log \log n$。本页使用随机哈希，所以查询是期望界；桶分裂、合并及哈希扩容又使更新采用期望摊还界。观察种子或结构后自适应选择键的对手，需要另外的随机性分析。

分裂、合并与摊还账本 ​

插入先定位桶并作树更新。桶超过 $2w$ 时按中位数分成两个约 $w$ 的桶，并新增中间分隔值。删除使桶少于约 $w/2$ 时，与邻桶一起重组：总数不超过 $3w/2$ 就合成一桶，超过时重新平均分成两个桶。这个阈值让重组后的桶远离下一次分裂与欠载边界。小字长及整数取整按常数大小基例处理。

新建或重新均衡的桶与触发阈值之间留有 $\mathrm{\Theta }(w)$ 次更新的余量。一次结构重组至多改变常数个代表，各自更新 $O(w)$ 个前缀；即使把桶树重建保守计为 $O(w\log (w+1))$，也可用摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。分散到引起重组的一段更新上，得到每次更新期望摊还 $O(1+\log w)$。这里的账本要求边界在普通桶内更新期间保持稳定。

X-fast 代表数为 $O(n/w)$ 时，前缀索引占 $O((n/w)w)=O(n)$ 空间，桶内树合计也为 $O(n)$。仅剩一桶时直接使用该树，不建立代表层；直到它再次超过 $2w$ 才分桶并恢复索引。这样既覆盖 $n<w$ 的小集合，也避免在 $n=w$ 附近反复建立和拆除 $w$ 层索引。

与抽样代表版本的区别 ​

另一条经典路线以约 $1/w$ 的概率抽取代表，并在相邻代表间维护桶。它控制的是桶大小和代表更新频率的期望，而本页阈值方案用明确的分裂/合并与稳定分隔值记账。两者共享两层设计，但不能把随机桶大小、确定大小阈值和单次最坏更新混成一张无条件成本表。

代表层的叶链、跳指针及桶邻接关系要同时维护。只更新前缀哈希而保留旧邻接链接，会使查询得到正确的前缀位置，却进入错误的相邻桶。