Learned Hash 与高级哈希变体

• 公式的来源与最优性条件
• 取整与字节对齐的工程处理
• 双哈希派生的实现技巧

给定 n、p：m=-n·ln p/(ln 2)²（向上取整），k=(m/n)·ln 2（取整）。推导：假阳率 p=(1-e^{-kn/m})^k，令最优 k=(m/n)·ln 2 得 p=(1/2)^k → k=-log2 p，回代 m=kn/ln 2 = -n·ln p/(ln 2)²。例：n=10^6、p=0.01 → k≈6.64 取 7，m≈9.58×10^6 位≈1.2MB；验算 p_actual=(1-e^{-7×9.58e6/1e6})^7 的精确值约 0.8%-1.1%，接近目标。

工程注意：k 取整后实际假阳率略高于理论最优，可把 m 上调 10% 补偿；哈希函数用双哈希派生（h1(x)+i·h2(x)，i=1..k）替代 k 个独立哈希以省计算；m 对齐缓存行与字节边界提升访问效率。

反推公式的锚点是"p=(1/2)^k 最优关系"；先定 k=-log2 p 再定 m=kn/ln 2 比硬背公式更不容易错，面试按这个顺序推导即可。

• 学习 CDF 预测 key 的排序位置
• 等分 CDF 的量化边界选择
• 桶内哈希探测与溢出兜底

BOOM（Bucket-Optimized Learned Hash）把"学习数据分布 + 桶化哈希"结合：先用训练数据学习 key 的 CDF（如线性回归或分段模型），预测 key 在排序空间中的位置，据此把 key 分成 B 个桶，使每个桶内 key 数量近似均匀；查询时先由模型定位桶，再在桶内做标准哈希探测（或桶内小哈希表）。bucket 边界选择的目标是负载均衡：边界取 CDF 的等分点（quantile），使模型误差落在桶内的概率高，减少跨桶溢出（overflow 链）。

相比普通哈希：学习分布使"热区间"的桶边界更密、相邻 key 更可能同桶，缓存命中率提高；相比纯 Learned Index：仍保留哈希的随机性处理模型误差（fallback），"模型加速 + 哈希兜底"是核心组合。工程难点：CDF 模型对动态插入的漂移、桶数与重哈希成本。

BOOM 的识别特征是"CDF 分桶 + 桶内哈希"两层；回答强调边界选择（等分 CDF）与溢出兜底，再点出动态漂移的工程难点即完整。

• 探测距离公平化的抢劫交换
• 期望探测 O(1) 与最坏 O(log n)
• 对比线性探测的极值行为

Robin Hood Hashing 在线性探测基础上加入"公平性"：插入时若新元素的探测距离 d 大于当前槽位元素的探测距离 d'，则"抢劫"——把槽内元素取出放入新元素，被抢元素继续向前探测；每步都使"最长探测距离"最小化。效果：期望插入/查找探测数 O(1)，且分布更集中——最坏情况探测 O(log n)，而普通线性探测在最坏（高负载）下探测 O(√n) 甚至更高。

expected probe length 推导：均匀哈希下插入位置均匀，探测距离分布近似几何分布 P[probe>t]≈α^t（α 为负载因子），E=1/(1-α)；Robin Hood 的"向后偏移"使距离分布被压平，方差显著下降——插入总成本不变，但把"少数长探测"转嫁到插入、让查询距离更集中。

RH 的卖点是"把方差转移到插入成本、查询更稳定"；回答对比线性探测的极值行为（√n vs log n）即可，推导给出几何分布直觉更好。

• 标量时间戳粗判 + BF 细判
• 集合包含关系的近似判定
• 以可分析误判率换 O(1) 空间

Bloom Clock 把逻辑时钟与 Bloom Filter 结合：每个节点维护"时间戳 + 布隆过滤器"，BF 记录该节点"已见的事件/消息 ID 集合"；比较两个时钟的因果顺序时，先用时间戳粗判（时间戳不同直接定序），时间戳相同或相近时用 BF 判断集合包含关系（BF⊆ 判定），从而在向量时钟基础上压缩存储——向量时钟 O(n) 空间（n 节点），Bloom Clock 每节点只需 O(1) 大小的 BF + 标量时间戳。

组合原理：向量时钟 V[i] 记录"节点 i 的消息数"，因果比较 = 逐分量比较；Bloom Clock 用"时间戳 + BF（消息 ID 的近似集合）"编码同一信息，代价是可能误判（BF 假阳导致的"疑似因果"），错误率可用概率模型分析（BF 假阳率公式）并调节位宽控制。适用于节点多、消息 ID 空间大的分布式系统。

Bloom Clock 是"把集合型逻辑时钟压缩进 BF"的两级判定结构；回答抓住"时间戳粗判 + BF 细判"两段与误判率可调即可。

• 模型预测位置 + 页内精定位
• fallback B-tree/二分兜底模型误差
• ε 决定页宽与查找成本

Learned Index 用机器学习模型拟合"key → 排序数组下标"的映射：训练模型（如线性回归、RMI 层级结构）预测 key 的近似位置，预测误差 ≥ε 的部分用 fallback 结构兜底——最常用 fallback 是 B-tree 或页内插值查找：先取模型预测位置附近的页（页宽 2ε），在页内做二分/线性搜索。模型提供"宽到页"的粗定位、页内用小索引，形成"模型 + 传统索引"的组合。

工程组合要点：ε 决定页宽与内存——模型误差大则页宽大、查找变慢、内存增加；每层模型可独立训练与并行；动态插入需要写缓冲（模型是静态拟合，插入用 delta buffer 或周期性重训）。收益：比 B-tree 少多层缓存未命中；局限：对分布漂移敏感、构建成本高。

Learned Index 的正确理解是"模型粗定位 + fallback 精确定位"的混合结构；面试必须提 fallback 与 ε 的权衡，只讲模型不讲兜底是常见失分点。

• set 随事件数线性增长 vs BF 常数位
• 合并操作的按位或常数时间
• 误判率与位宽的权衡

传统"timestamp + set"实现：每个节点维护 (时间戳, 已见事件 ID 集合)，集合随事件数线性增长——空间 O(事件总数)，消息 ID 需完整存储；Bloom Clock 用固定 m 位 BF + 标量时间戳：空间 O(m)（常数，与事件数无关），且比较/合并操作按位运算 O(m/64)。代价：BF 假阳引入误判（"可能见过"），错误率 p 由 m 与事件数决定，需按业务选 m。

量化对比：设事件 10^6、ID 16 字节，set 需 16MB+；Bloom Clock 选 p=1% 需 m≈1.44×10^6×6.6≈9.5×10^6 位≈1.2MB，十倍以上差距，且事件更多时 set 线性增长、Bloom 不变。合并操作（两个时钟合并 = 时间戳取 max + BF 按位或）同样是常数时间。

对比维度是"空间随事件数增长 vs 常数、精确 vs 概率"；回答给出位数公式（m≈1.44n·log2(1/p)）更专业，量化数字能加分。

• BF 负判定直接处理、正判定二次确认
• 代际滚动 BF 实现去重窗口
• 去重 ID 的"已发目录"角色

Bloom Clock 的事件去重：把"已处理的事件 ID"插入本地 BF（时钟的时间戳记录逻辑进度），新事件到达先查 BF：判定"一定没见过"则处理并插入 BF；判定"可能见过"则进入确认流程（查精确存储或上游）避免重复处理。debounce（防抖）场景：对同一 ID 的重复触发在 BF 命中后抑制，直到 BF 过期/重建窗口，实现"去重窗口"语义。

去重 ID 生成：节点用"时间戳 + 本地序列"生成全局唯一 ID 并插入自己的 BF，作为"已发 ID 目录"供对端去重校验；对端用同一 BF 判定重复。工程注意：BF 假阳使"可能见过"必须二次确认、不能直接丢弃；BF 需按时间窗滚动（如双缓冲代际）防止无限增长，代际切换时新旧 BF 并存过渡。

BF 在去重里的角色是"廉价负判定 + 概率正判定"；回答强调"负判定直接处理、正判定二次确认"的流程与代际滚动两点即完整。

• 邻域 bitmap 与顺移机制
• 查找确定性 O(H) 与负载无关
• H 与负载因子的工程配置

Hopscotch Hashing 为每个桶定义长度为 H 的邻域（连续槽），插入冲突时在邻域内寻找空位，并把阻挡元素沿"顺移链"移到空位，最终保证每个元素都落在其初始桶的 H 邻域内；查找只需扫描 H 个槽，最坏确定性 O(H)，与负载无关。bitmap 记录邻域槽的归属，顺移是常数次指针搬移。

邻域 H 与负载：H 越小缓存越好（邻域可装进一个缓存行）但插入失败率越高；负载因子 1/2 附近时 H 取 4~16 即可保持极低失败率与 O(1) 期望性能，负载升到 0.9 需要 H 显著增大或接受偶发 rehash。工程上在 0.5~0.7 负载、H=8~32 是最常见配置，兼顾缓存局部性与插入成功概率。

Hopscotch 的定位是"确定性查找界 + 缓存局部性"；回答抓住邻域 bitmap 与顺移机制，再给出 H 与负载因子的配置关系即完整。

• d 子表间选负载最小插入
• 最大负载从 log n/log log n 降到 log log n
• 与 Cuckoo 逐出式的互补

d-left hashing 把哈希表分成 d 个子表，插入时在 d 个子表的候选槽中选"负载最小"者；查询只需检查 d 个候选位置。相比单哈希表，负载分布大幅改善：单表最大桶负载 ≈Θ(log n/log log n)，d-left 降到约 Θ((log log n)/d)——"rich get richer"（越满的桶越容易被再次选中）被"选最小"策略抑制，这是"多选一"随机化的威力。

工程：d 通常取 2-4；每个元素固定占用"左侧子表"的顺序结构可支持删除（需标志位）；d-left 与 Cuckoo（逐出式）互补——d-left 无逐出、插入快、实现简单，但负载接近 1-1/d 时性能退化，需配合 rehash；Cuckoo 则靠逐出支撑更高负载。

d-left 的要点是"最小负载选择打破正反馈"；回答给出最大负载对比（log n/log log n vs log log n）即完整，与 Cuckoo 的对比能体现选型思维。

• 查询成本 = cache miss 次数 × 延迟
• 模型一次计算换多次 miss
• 小索引场景的模型开销劣势

Learned Index 的胜出场景是 DRAM-bound（内存访问受限）：查询成本 = 多次随机内存访问（cache miss，约 100ns 级）。B-tree 每层一次 cache miss（高度 4-5 层）；Learned Index 用模型一次预测 + 页内扫描，通常 1-2 次 cache miss——省掉的正是"层数 × miss 延迟"。compute-bound 场景（模型推理时间 > 省下的内存访问时间）反而更慢：模型是乘加运算，若数据规模小、B-tree 已在缓存中，模型计算纯属开销。

工程依据：CPU 与 DRAM 延迟差约 100 倍，一次模型计算（约 1-3ns）换来一次 cache miss 的节省（约 100ns）在大索引上净赚；线性模型参数只有两个，可在 L1 缓存命中。结论：索引越大、层数越多，Learned 收益越大；索引小则传统结构（甚至数组线性扫描）胜出。

回答框架"成本模型 = miss 次数 × miss 延迟 vs 模型计算延迟"；抓住"DRAM-bound 才值得"与"100 倍延迟差"两个数字即完整。

• 位清空概率的泊松近似
• 对 k 求导的完整求解过程
• 置位概率 1/2 的最优性

推导从位清空概率出发：插入 n 个元素、每元素置 k 位（哈希独立均匀），某特定位在单次置位后仍为 0 的概率 1-1/m，n 个元素共 kn 次置位后仍为 0 的概率 (1-1/m)^{kn} ≈ e^{-kn/m}（泊松近似，m 大时成立）。查询不在集合的元素 x：其 k 个哈希位全被置 1 才是假阳，各位置 1 概率近似独立（哈希独立性），故 p=(1-e^{-kn/m})^k。

最优 k 的求解：令 m/n=r 固定，p(k)=(1-e^{-k/r})^k；对 ln p 求导并令为 0：ln(1-e^{-k/r}) + k·(e^{-k/r}/r)/(1-e^{-k/r}) = 0，设 u=e^{-k/r}，整理得 (1-u)·ln(1-u) = -u·ln u，数值解 u=1/2，即 e^{-k/r}=1/2 → k=(m/n)·ln 2；此时每位被置位概率恰为 1/2，最小假阳率 p_min=(1/2)^k。置位概率 1/2 是"信息熵最大化"的体现——每位携带最多信息。

完整推导链路"位清空概率 → 泊松近似 → 对 k 求导 → 置位概率 1/2"；面试能写出求导式并指出 u=1/2 的数值解即满分，这是布隆参数化的理论根基。

• 数据库查询前先查 BF 的部署链
• 负判定短路（假阴率为 0）的依据
• 正判定回源与 BF 同步维护

部署位置：数据库查询之前（也可在缓存之前）——所有请求先查 BF。BF 判定"不存在"的 key：一定不存在（假阴率 0），直接短路返回，不查询缓存、不压数据库；BF 判定"存在"的 key 进入正常链路（缓存→DB）。BF 中"存在"但 DB 也没有（假阳）的 key：与普通未命中同样处理（回源后不写缓存或写短期空值缓存），不影响正确性，只是多一次 DB 查询。

工程要点：BF 内容 = 已知合法 key 集合，需随数据写入同步更新（写路径插入 BF）；BF 的"存在"判定受假阳率 p 控制，p 按"可容忍的多余 DB 查询比例"设定（如 1%）；BF 定期重建（数据淘汰导致 BF 过期失真）；内存 m≈1.44n·log2(1/p)。

部署的骨架是"负判定短路、正判定回源"；与"缓存空值"方案相比 BF 内存更省、不污染缓存，但无法区分"假阳 vs 真实 key"，面试对比两方案更完整。

• 桶内指纹匹配删除机制
• 半排序的存储编码优化
• 与 BF 位共享不可删除的对比

Cuckoo Filter 的"半排序"（semi-sorting）：每个桶存 b 个指纹（如 4 个 4 位指纹 = 16 位），插入/删除/查询都在桶内进行。删除操作：在候选桶中线性扫描找匹配指纹，找到则清除；为减少误删其他元素指纹（指纹碰撞），可加计数或使用更长指纹。半排序的实质是把桶内指纹存储与"已用/空闲"状态压缩编码（如每桶用 b 个指纹 + 位置位图），使空间利用率接近信息论下界（约 1.05×）。

对比 Bloom：BF 无删除概念（位共享，删除会误清他人位造成假阴）；Cuckoo 删除 = 定位候选桶（2 次访问）+ 桶内精确指纹匹配，删除后查询正确性不受影响——指纹精确匹配不存在位共享误伤，除非指纹碰撞。半排序删除让 CF 成为"可删除 + 高负载 + 近最优空间"的实用过滤器。

删除安全的来源是"指纹精确匹配而非位共享"；半排序是空间优化细节，回答区分"删除机制"与"空间压缩"两层即完整。

• 每层对应一个前缀长度的分层结构
• 从最长前缀逐层否定剪枝
• 多级缓存/路由查找中的应用

分层 Bloom Filter（Hierarchical BF）：用多个 BF 层，每层对应一个"前缀长度"（如 IP 的 /24、/25 或字符串的前缀位数），第 i 层只插入"前缀长度为 i"的 key 集合。查询时从最长前缀层开始逐层判断：某层判定"不存在"则该前缀下所有 key 都不存在，直接剪枝返回；逐层向上直到找到"可能存在"的最长层，完成"最长前缀匹配/路由查找"的近似判定。

合并查询：对目标 key 的前缀 p，在第 i 层查该前缀是否"可能存在"；多层结果合并——路由查找要最长前缀，从长到短检查，首个"可能存在"的层即答案，其余层不必再查。工程应用：多级缓存按前缀分流（L1/L2）、路由表 IP 前缀匹配的快速否定、内容寻址网络。空间 = Σ 各层 BF 大小，可用"共享位数组 + 层掩码"优化。

分层 BF 的要点是"层 = 前缀粒度，否定剪枝"；回答给出"长到短逐层判定"的流程即完整，能提共享位数组优化更好。

• 删除支持的有无与代价
• 空间倍数 1.05× vs 1.44×
• 查询延迟 2 次 vs k 次

四维对比：删除——BF 不可删除（位共享误清），CF 可删除（指纹匹配 + 计数）；空间效率——CF 每元素约 1.05× 信息论下界（4-8 位指纹 + 桶开销），BF 约 1.44×（m=1.44n·log2(1/p)），同 n、p 下 CF 更省；查询延迟——CF 确定性最多 2 次桶访问（i1、i2，桶内小扫描），BF 需 k 次哈希与 k 次位访问（k≈7-14）；负载因子——CF 可达 95%+，BF 需按峰值 n 预先分配否则假阳率恶化。

代价：CF 插入可能触发循环驱逐（最坏需 rehash/扩容）、删除对"同指纹不同元素"存在假删除率（用计数或更长指纹降低）、实现复杂度高；BF 实现简单、无删除、参数化成熟。选型：可删除/高负载/低延迟选 CF；简单稳定/固定容量选 BF。

对比答案的骨架是"删除、空间倍数、访问次数、负载"四指标 + 代价；1.05×/1.44× 与 2 次/k 次是高频考点数字，回答时务必点出。

• 按位 OR/AND 的位图单调性
• OR/AND 保持无假阴、放大假阳率
• 假阳率变化的量化公式

BF 的并集：A∪B 的近似 = BF_A OR BF_B（按位或）：插入过任一集合的元素其 k 位在两图中都置 1，OR 后仍在 → 无假阴（成员查询不漏）；假阳率上升——某元素不在并集但 A、B 各自的假阳位 OR 后恰好全 1 的概率 ≈ 1-(1-p_A)(1-p_B)（两图独立时），高于单图。交集：BF_A AND BF_B：同时属于两集合的元素位都在 → 无假阴；但"位都在"也可能是两集合各自的假阳位重叠，故有假阳。关键：AND/OR 保持"无假阴"，只放大假阳率——这是"位图单调性"的直接推论。

工程注意：不同参数（m、k）的 BF 不能直接 OR/AND；哈希函数需一致；假阳率放大需按公式重算（OR 后 p 上升，若需维持 p 需增大 m）。计数布隆的 OR/AND 对计数求和/取 min 也有类似语义。

回答锚点"位图单调 ⇒ 无假阴、假阳率可算"；给出 OR 后假阳率公式（1-(1-p_A)(1-p_B)）即显专业，参数一致性提示体现工程感。

• 计数器 +1/-1 的删除机制
• 溢出概率的泊松近似估计
• 位宽与负载的工程权衡

Counting Bloom Filter 把位换成计数器：插入时 k 个计数器 +1、删除时 -1（归零才算清空该位）、查询检查 k 个计数器是否全 >0。删除的正确性：计数器记录多位共享的"重叠次数"，-1 到 0 才清除，与普通 BF 的"位共享误清"相比只减少自己的贡献。前提：只能删除确实插入过的元素（否则计数器下溢），可用"先查询后删除"或维护删除集合。

计数器位宽：b=4 常见（0-15）。溢出分析：某计数器被命中的次数 X 近似二项分布 B(nk, 1/m)，期望 λ=nk/m；负载高（λ 大）时 P[X>15] 显著：λ=8 时 P≈P(Poisson(8)>15)≈1% 量级，λ=10 时约 4%。因此工程上把 λ 控制在 ≤4 左右，或用 8 位计数器、或周期性重建（扫描重置）。位宽与负载的权衡是 CBF 设计的第一考量。

溢出概率的量化用泊松近似 P[Poisson(nk/m)>2^b-1]；回答给出"λ=nk/m 控制 + 4/8 位选择 + 周期重建"即完整。

• 两候选桶的逐出链与 d 路推广
• cycle detection 的步数上限与位置记录
• 负载 50% 附近的复杂度保证

Cuckoo Hash 插入：计算两个候选桶（两表各一，或用指纹派生），若其一有空位直接放入；否则逐出该位旧元素，旧元素去它的另一个候选桶，形成"逐出链"（2-choice 的通用化可推至 d 路：d 个候选选一逐出）。cycle detection：逐出可能无限循环（两个元素互相逐出或回到起点），实现用步数上限（如 512 或 n 的常数倍）或记录访问过的位置（位图），超限则触发 rehash（换哈希种子重建表）。

2-choice 的理论收益：d=2 时插入期望 O(1)（负载 <50% 时），最大桶占用 O(log log n) 量级；负载 50% 是"无循环逐出"的常见保证阈值，超载后失败率陡增。工程实现：两表大小取素数、哈希独立、逐出时随机化选择（随机踢哪个）降低循环概率。

Cuckoo 的复杂度保证依赖"两选择 + 低负载 + 随机逐出"；cycle detection 是工程必需的熔断器，回答要同时给出触发条件（步数上限）与恢复（rehash）。

• quotient 分桶 + remainder 游程结构
• 三个标志位的删除与合并机制
• 空间开销与实现复杂度的代价

Quotient Filter（QF）把哈希值分成 quotient（高位）与 remainder（低位），按 quotient 落桶，桶内用"元数据标志位 + 有序 remainder 游程"存储：每个槽有 3 个标志位（is_occupied、is_continuation、is_shifted）支持有序遍历。优势：支持删除（removal 时按游程逻辑清除并前移后续元素）、支持合并（两个 QF 按有序游程 merge，O(大小) 一次遍历）、支持有序遍历（按哈希值顺序枚举所有元素——Bloom/Cuckoo 没有）、负载可达 90%+。空间：约 2-3 位/元素级别，通常比 BF 大 10-30%（BF 可预先分配位数组，QF 需存 remainder + 标志位）。

代价：实现复杂（标志位与游程维护）、查询需沿游程扫描（比 CF 的固定 2 次访问慢）、删除后需"repair"游程保持不变量。适用：需要枚举/合并/删除的集合场景（数据库布隆替代、基因 k-mer 集合）。

QF 的卖点是"有序性"带来的衍生能力（合并、遍历、删除）；回答给出三个标志位与游程结构即显深度，与 BF/CF 的三方对比更完整。

• 递归粗-细定位的层次模型
• 写缓冲 + 周期重训的动态更新
• 分布漂移与错误传播

RMI（Recursive Model Index）是分层模型：第一层模型把 key 空间粗分到第二层模型集合，第二层再细分，直到叶子模型输出"排序数组中的预测位置"。每层模型是一个简单函数（线性/分段/小神经网络），层层递归把"全序 key → 位置"映射分解，降低单模型拟合难度，同时每层可用独立数据训练，支持并行训练。

Updatable Learned Index（动态插入）的难点：模型是静态拟合的——插入 key 后预测位置偏移，若直接写入会打乱顺序；方案：写缓冲（delta buffer）吸收近期插入，周期性与模型合并重训；或"模型输出页 + 页内 B-tree/数组"结构，插入落在页内结构。其他难点：分布漂移后模型陈旧（需监测并重训）、错误传播（上层模型误差进入下层放大）、并发更新与持久化。

RMI 回答的层次是"递归粗-细分解 + 叶页兜底"；动态化的核心是"缓冲 + 周期重训"，答出即覆盖工程难点，错误传播是加分项。

• 指纹存储与候选桶派生公式
• 异或对称性支持逐出定位
• 近最优空间与 2 次桶访问

partial-key cuckoo hashing 的动机：布谷鸟逐出时需知道"被踢元素"的另一个候选桶，若只存指纹（而非整个 key），可用 i2 = i1 ⊕ h(fingerprint) 派生：设元素 x 的桶 i1=h(x)、指纹 f=hash(x) 截断，另一个候选 i2=i1⊕h(f)，则从 i2 出发同样可得 i1=i2⊕h(f)（异或对称性）——逐出时仅凭指纹就能算出对方桶，无需原始 key。这就是"partial-key"（部分 key：只用指纹参与桶派生）。

好处：桶里只存指纹（4-8 位），空间接近信息论下界（约 1.05×）；查询定位 2 个候选桶（b 与 b⊕h(f)），最多 2 次桶访问。注意：h(f) 需与 h(x) 独立设计，指纹位数影响"同一指纹出现在两桶"的碰撞率与假删除率。这是 Cuckoo Filter（CF）的核心构造，也是其删除、高负载、近最优空间三大特性的底层机制。

partial-key 的巧妙在"异或自反性让指纹携带桶信息"；回答给出 i2=i1⊕h(f) 公式即抓住本质，再补指纹位长与碰撞率的权衡即完整。