# 1. 如何为给定元素数 n 与可接受假阳率 p 计算所需位数组大小 m=-n·lnp/(ln2)² 与哈希数 k=(m/n)·ln2 A m 与 p 成正比 B 最优参数 k=-log2 p、m=kn/ln2，即 m=-n·lnp/(ln2)²，验算公式 p=(1-e^{-kn/m})^k ✓ 正确答案 C k 取任意整数均可 D 双哈希派生态增加假阳率
# 2. BOOM（Bucket-Optimized Learned Hash）的 CDF 模型与 bucket 边界选择。 A BOOM 不学习数据分布 B BOOM 用学习到的 CDF 等分桶边界使负载均衡，桶内再用哈希探测，模型误差由哈希兜底 ✓ 正确答案 C BOOM 桶边界随机选取 D BOOM 无法处理插入
# 3. Robin Hood Hash 的方差分析与 expected probe length 推导。 A Robin Hood 插入时与探测距离更大的槽位交换，使探测距离分布更集中，期望 O(1)、最坏 O(log n) ✓ 正确答案 B Robin Hood 增加平均探测数 C Robin Hood 只优化删除 D Robin Hood 最坏探测 O(√n)
# 4. Bloom Clock 的时间戳 + Bloom filter 双结构组合原理。 A Bloom Clock 用时间戳 + 布隆过滤器压缩向量时钟的集合语义，牺牲可分析的误判率换 O(1) 空间 ✓ 正确答案 B Bloom Clock 与向量时钟空间相同 C Bloom Clock 是精确的 D Bloom Clock 不记录因果关系
# 5. Learned Index 的 model fitting 与 fallback B-tree 的工程组合。 A Learned Index 不需要 fallback B Learned Index 完全替代索引结构 C Learned Index 用模型粗定位到页、页内 fallback（B-tree/二分）精定位，ε 控制页宽与查找成本 ✓ 正确答案 D 模型误差与页宽无关
# 6. Bloom Clock 与传统 timestamp + set 的空间复杂度对比。 A 两者空间同阶 B Bloom Clock 空间 O(m) 与事件数无关、合并按位或 O(m/64)，传统 set 随事件数线性增长 ✓ 正确答案 C Bloom Clock 合并需逐事件比较 D set 方案空间常数
# 7. Bloom Clock 在事件去重（debounce）与去重 ID 生成中的实现。 A BF 去重是精确的 B 正判定可直接丢弃事件 C Bloom Clock 去重时负判定直接处理、正判定二次确认，配合代际滚动 BF 实现去重窗口 ✓ 正确答案 D BF 无需滚动重建
# 8. Hopscotch Hash 的邻域大小 H 与 1/2 负载上限。 A 邻域 H 越大缓存越好 B Hopscotch 查找是 O(log n) C Hopscotch 保证元素在其初始桶的 H 邻域内，查找确定性 O(H)，1/2 负载附近 H=8~32 即可高效 ✓ 正确答案 D Hopscotch 不支持高负载
# 9. d-left hashing 的 rich get richer 偏置缓解。 A d-left 随机选择子表 B d-left 在 d 个子表间选负载最小者插入，把最大桶负载从 Θ(log n/log log n) 降到 Θ(log log n)/d ✓ 正确答案 C d-left 会加剧 rich get richer D d-left 最大负载与单表相同
# 10. 为什么 Learned Index 在 DRAM-bound 而非 compute-bound 的场景中胜出。 A cache miss 与模型计算无关 B Learned Index 在任何场景都更快 C Learned Index 用一次模型计算换掉 B-tree 的多次 cache miss，在大索引（DRAM-bound）场景净赚，小索引反而有计算开销 ✓ 正确答案 D B-tree 层数与 cache miss 无关
# 11. 标准 Bloom Filter 的假阳率公式 (1-e^{-kn/m})^k 如何从独立哈希假设推导？最优哈希数 k=(m/n)·ln2 与对应最小假阳率 (1/2)^k 的求解过程 A 最优 k 与 m/n 无关 B 位清空概率是 e^{-kn/m} 的倒数 C 假阳率推导为 p=(1-e^{-kn/m})^k，对 k 求导得最优 k=(m/n)·ln2、置位概率 1/2、最小假阳率 (1/2)^k ✓ 正确答案 D 假阳率随 k 单调递减
# 12. Bloom Filter 在缓存穿透防护中的部署中数据库查询前先用 BF 过滤不存在 key，BF 本身'不存在'的 key 如何处理（BF 不存在=一定不存在） A BF 正判定一定存在 B BF 部署在 DB 之前，负判定直接短路（一定不存在），正判定回源，假阳只多一次查询、不影响正确性 ✓ 正确答案 C BF 假阳会造成错误数据 D BF 需精确记录所有 key
# 13. Cuckoo Filter 的半排序删除支持 vs Bloom Filter 的不可删除。 A Cuckoo Filter 删除靠候选桶内指纹匹配清除，无位共享误伤（指纹碰撞用计数缓解），半排序压缩桶内编码接近信息论下界 ✓ 正确答案 B Cuckoo 删除会误清他人位 C 半排序指按值排序指纹 D Cuckoo 不支持删除
# 14. 分层 Bloom Filter（Hierarchical BF）在多级缓存/路由查找中的应用中每层对应一个前缀长度，如何合并查询 A 每层独立存储互不相关 B 分层 BF 只有一层 C 分层 BF 不能做前缀匹配 D 分层 BF 每层对应一个前缀长度，查询从最长前缀逐层否定剪枝，实现近似最长前缀匹配 ✓ 正确答案
# 15. Bloom Filter 与 Cuckoo Filter 在删除支持、空间效率（Cuckoo ~1.05×理论下界 vs Bloom ~1.44×）、查询延迟（Cuckoo 确定性 2 次 vs Bloom k 次）上的对比 A CF 空间比 BF 大 B CF 支持删除、约 1.05× 空间下界、确定 ≤2 次桶访问、负载 95%+；BF 约 1.44×、k 次访问、不可删除 ✓ 正确答案 C CF 查询是 k 次哈希 D BF 支持删除
# 16. Bloom Filter 的并集/交集能否通过位运算近似？OR 合并后假阳率如何变化 A OR 后假阳率不变 B BF 的 OR 近似并集、AND 近似交集，位图单调性保证无假阴，但假阳率上升（OR 后约 1-(1-p_A)(1-p_B)） ✓ 正确答案 C AND 会引入假阴 D 不同参数 BF 可直接合并
# 17. Counting Bloom Filter 如何支持删除？计数位宽如何选取以避免溢出（4 位计数器在负载高时的溢出概率分析） A 删除不需先确认插入过 B 计数器不会溢出 C CBF 用计数器 +1/-1 删除，溢出概率按 Poisson(nk/m) 估计，负载高时 4 位不足需 8 位或重建 ✓ 正确答案 D CBF 空间与 BF 相同
# 18. Cuckoo Hash 的 2-choice 通用化与 cycle detection 实现。 A Cuckoo Hash 插入永不会失败 B Cuckoo Hash 插入沿两候选桶逐出旧元素，用步数上限/位置记录检测循环，超限触发 rehash，负载 <50% 时插入期望 O(1) ✓ 正确答案 C 逐出链无需检测 D 负载 90% 仍保证 O(1) 插入
# 19. Quotient Filter 相比 Bloom 的优势中支持删除、合并、有序遍历，但空间略大 A QF 空间比 BF 小很多 B QF 不支持删除 C QF 无法遍历元素 D Quotient Filter 用 quotient 分桶 + remainder 游程，支持删除、合并、有序遍历，但实现复杂、空间略大 ✓ 正确答案
# 20. RMI（Recursive Model Index）的层次模型在 Updatable Learned Index 的工程难点。 A RMI 不需要兜底结构 B RMI 只有一层模型 C RMI 插入直接改写模型 D RMI 用多层模型递归粗-细定位 key，动态更新靠写缓冲 + 周期重训，模型误差由叶页内结构兜底 ✓ 正确答案
# 21. 布谷鸟过滤器（Cuckoo Filter）的 partial-key cuckoo hashing 中指纹存储与候选桶 b=h(x) 和 b⊕h(fingerprint) 的两个候选位置 A partial-key cuckoo hashing 用 i2=i1⊕h(fingerprint) 派生第二候选桶，逐出时凭指纹即可定位，只存指纹实现近最优空间 ✓ 正确答案 B 逐出需要原始 key C 指纹不参与桶计算 D 候选桶只有一个
