# 1. Merging Digest 的 two-by-two merging 策略。 A 两两合并会把误差放大到 O(1) B Merging Digest 合并需要全量数据 C Merging Digest 用按中心排序后两两配对的方式合并质心，保持 ε-分位数近似界 ✓ 正确答案 D Merging Digest 不支持分布式合并
# 2. Jump Consistent Hash 的 O(log n) 映射与单调性保证推导。 A Jump Consistent Hash 映射复杂度 O(1) 最坏 B Jump Consistent Hash 需要维护哈希环 C Jump Consistent Hash 迁移量是 O(1/2) D Jump Consistent Hash 对固定 key 的桶号随 n 单调，节点增删迁移 O(1/N) 数据，单次映射期望 O(log n) ✓ 正确答案
# 3. 如何根据可接受假阳率反推所需位数与哈希个数 A 最优参数 m=-n·lnp/(ln2)²、k=(m/n)·ln2，此时假阳率约 (1/2)^k ✓ 正确答案 B k 越大假阳率越低，无最优值 C m 与 p 无关 D 假阳率公式是 (1-e^{-kn/m})^n
# 4. 布隆过滤器如何用 k 个哈希位判断"可能在/一定不在" A 位全 1 即元素一定在集合中 B 布隆过滤器存在假阴率 C 布隆查询任一哈希位为 0 则一定不在；全为 1 则可能在，假阴率为 0 ✓ 正确答案 D 布隆过滤器支持删除
# 5. Sliding HyperLogLog 在时间窗口上的合并策略。 A Sliding HLL 把窗口分成多代 HLL，查询时逐寄存器取 max 合并、过期丢弃，保持约 1.04/√m 误差 ✓ 正确答案 B Sliding HLL 需要全量数据重算 C HLL 合并会破坏基数估计 D 滑动窗口只能用精确集合
# 6. 一致性哈希在节点增删时的数据迁移量分析中仅影响相邻节点间的 O(1/N) 数据，虚拟节点数越多负载越均衡但内存开销越大 A 虚拟节点不改变负载均衡 B 一致性哈希增删节点需迁移全部数据 C 一致性哈希节点增删只迁移相邻节点数据（约 1/N），虚拟节点越多负载越均衡但内存越大 ✓ 正确答案 D 取模哈希的迁移量也是 O(1/N)
# 7. Greenwald-Khanna 算法在小数据集上保持 1% 误差的内存优势。 A GK 支持高效合并 B GK 空间与 n 线性相关 C GK 用 (v,g,Δ) 元组链维护分位数，空间 O((1/ε)log(εn))，小数据上即可保持 1% 误差且无需随机化 ✓ 正确答案 D GK 的误差是概率性的
# 8. Maglev Hash 的 lookup table 大小与平衡性取舍。 A Maglev 不保证构建后负载均匀 B Maglev 查询需要 O(log n) C Maglev 的 m 取任意值均可 D Maglev 用排位表确定性构建 m 大小的 lookup table，查询 O(1)，m 越大越均匀但构建与内存越大 ✓ 正确答案
# 9. MinHash 的 Jaccard 估计原理与 (1/ε^2) 哈希函数数下界。 A MinHash 用最小哈希相等概率估计 Jaccard，误差 O(1/√k)，达到 ε 相对误差需 k=O(1/ε²) 个哈希 ✓ 正确答案 B MinHash 估计的是集合基数 C 一个哈希函数即可精确估计 Jaccard D MinHash 误差与 k 无关
# 10. SimHash 的汉明距离与余弦相似度的对偶关系。 A SimHash 指纹的汉明距离与夹角无关 B SimHash 指纹的汉明距离期望与向量夹角成正比（P[符号不同]=θ/π），可近似反推余弦相似度 ✓ 正确答案 C SimHash 是精确相似度算法 D 汉明距离无法用位运算加速
# 11. Weighted Consistent Hash（HRW）在 partition assignment 中的工程案例。 A HRW 查询 O(1) 与节点数无关 B HRW 需要维护哈希环 C HRW 不支持权重 D HRW 对每个 key 与节点计算随机权重取最大，零内存、支持加权，查询 O(n) ✓ 正确答案
# 12. b-bit MinHash 的偏差修正与字节级优化。 A b-bit MinHash 无偏差 B b-bit MinHash 截断低 b 位并用 J≈(F-2^-b)/(1-2^-b) 修正偏差，存储降至 k·b 位 ✓ 正确答案 C b 越大偏差越大 D b-bit 截断不影响存储
# 13. p-stable LSH 在 Euclidean LSH 的构造与 LSH Forest。 A p-stable LSH 用随机投影 + 量化使碰撞概率随距离单调递减，LSH Forest 用多棵前缀树免去桶宽调参 ✓ 正确答案 B p-stable LSH 的碰撞概率与距离无关 C LSH 只能用于汉明空间 D LSH Forest 用固定桶宽
# 14. t-digest 的 scale function k(i) 与 centroid merging 规则。 A scale function 与误差无关 B t-digest 所有质心权重相等 C t-digest 无法估计 P99 D t-digest 用 scale function 控制质心权重上界，k1(q)=δ/2π·asin(2q-1) 使尾部分位数精度更高 ✓ 正确答案
# 15. HyperLogLog 如何用"最长前导零"估计基数（LogLog 思想） A 最长前导零与基数无关 B HLL 用算术平均 C 单个寄存器即可给出精确估计 D HLL 用最长前导零估计 2^ρ 并分桶，LogLog 用几何平均、HLL 用调和平均把误差降到约 1.04/√m ✓ 正确答案
# 16. 多个 HLL 草图如何合并以估计并集的基数 A 同参数 HLL 合并为逐寄存器取 max，等于直接对并集建草图，支持分布式基数统计 ✓ 正确答案 B HLL 合并需要全量数据 C 合并后误差翻倍 D HLL 寄存器应逐桶求和
# 17. 数据流中"独立元素计数"为何不能用精确集合（内存爆炸） A 精确计数需 O(n) 内存记住每个元素，HLL 用 O(log log n) 位的寄存器估计基数，靠哈希均匀性换取精度 ✓ 正确答案 B 精确计数可以用压缩节省到 O(log n) C HLL 需要记住所有元素 D 基数估计误差与 n 线性相关
# 18. 一致性哈希的虚拟节点（virtual node）数量与负载均衡方差关系。 A 负载方差与 v 无关 B 虚拟点不改变负载分布 C 虚拟点数 v 越多负载方差越小（约按 1/√v 衰减），但内存 O(Nv) 上升，通常取 100-200 ✓ 正确答案 D 虚拟点越多内存越小
# 19. HLL 的 stochastic averaging 与 bias correction 在小基数下的修正公式。 A 小基数时调和平均估计偏高 B HLL 分 m 桶做随机平均把方差降 O(1/m)，α_m 与空桶线性计数 m·ln(m/V) 分别修正大/小基数偏差 ✓ 正确答案 C α_m 是任意常数 D stochastic averaging 增加方差
# 20. HLL++ 的 sparse vs dense representation 切换阈值。 A 切换阈值与基数无关 B HLL++ 始终用 6 位数组 C sparse 表示比 dense 快 D HLL++ 小基数用稀疏列表存非零寄存器，超过约 m/2 个非零寄存器时切换定长 dense 数组 ✓ 正确答案
# 21. HyperMinHash 的 full-rank MinHash 在大数据集下的 3-5x 空间优势。 A HyperMinHash 用 rank 截断 + 前导零编码压缩 MinHash 指纹，full-rank 下比普通 MinHash 省 3-5 倍空间 ✓ 正确答案 B HyperMinHash 比 MinHash 更耗空间 C HyperMinHash 不能估计 Jaccard D HyperMinHash 需要存完整哈希值
# 22. KLL（Karnin-Lang-Liberty）quantile sketch 的空间证明中为什么最优空间是 O((1/ε)·log log(1/δ)) 而非 O((1/ε)·log(1/δ))，与 GK sketch 的对比？ A KLL 空间与 GK 相同 B KLL 分层全压缩使层数只需 O(log log(1/δ))、每层 O(1/ε) 空间，总量 O((1/ε)·log log(1/δ))，优于 GK 的 O((1/ε)·log(1/δ)) ✓ 正确答案 C KLL 每层空间随层数指数增长 D KLL 不需要随机化
# 23. LogLog vs SuperLogLog vs HLL 在不同基数范围的相对误差演变。 A HLL 用算术平均误差更小 B 三者误差相同 C SuperLogLog 用全部桶取平均 D LogLog 几何平均误差 1.30/√m，SuperLogLog 截尾 70% 降到 1.05/√m，HLL 调和平均到 1.04/√m ✓ 正确答案
# 24. 布隆过滤器在缓存穿透防护中的工程部署位置 A BF 正判定可直接返回数据 B BF 防穿透部署在存储层之前，负判定直接短路返回；正判定回源，假阳只多一次查询 ✓ 正确答案 C BF 防穿透需要精确集合 D BF 的负判定可能误杀合法 key
# 25. Count-Min Sketch 如何在单射错误下估计频率上界 A Count-Min 用求和估计频率 B Count-Min 可能低估频率 C Count-Min 点查询是精确的 D Count-Min 点查询取 min_j C[j][h_j(x)]，恒为 f(x) 上界，且以 1-δ 概率误差 ≤ε||f||₁ ✓ 正确答案
# 26. Cuckoo Filter 相比布隆在删除与查询效率上的改进 A Bloom Filter 支持删除 B Cuckoo Filter 空间比 Bloom 大 C Cuckoo Filter 查询需 k 次哈希 D Cuckoo Filter 支持删除、查询确定 ≤2 次桶访问、空间约 1.05× 下界，Bloom 约 1.44× 且不可删除 ✓ 正确答案
# 27. HLL 在 Redis 中 PFADD/PFCOUNT/PFMERGE 的合并语义 A Redis 中 PFMERGE 逐寄存器取 max，PFCOUNT 得到并集基数近似；PFADD 幂等，稀疏表示下小基数可精确 ✓ 正确答案 B PFMERGE 把寄存器求和 C PFADD 每次增加计数 D Redis HLL 每 key 固定 64KB
# 28. HLL 的分桶（register）与调和平均如何降低方差 A 分桶随机平均把方差降到 O(1/m)，调和平均对个别异常大 ρ 不敏感，使误差达约 1.04/√m ✓ 正确答案 B 调和平均对离群值更敏感 C 分桶增加误差 D HLL 用几何平均最优
# 29. MinHash 估计集合相似度（Jaccard）与 HLL 估计基数的区别 A MinHash 直接给出基数 B MinHash 估计 Jaccard 相似度、HLL 估计基数，二者可由"并集基数 + 单集基数"间接互转但误差放大 ✓ 正确答案 C HLL 直接给出相似度 D 两者信息内容相同
# 30. 为什么说 HLL 的估计是有偏/无偏及其偏差校正 A 偏差与桶数无关 B HLL 在任何基数下都精确无偏 C HLL 原始调和平均有小样本偏差，α_m 常数 + 小基数线性计数 + 大基数扩展修正后渐近无偏 ✓ 正确答案 D 修正只影响小基数
# 31. 为何 HLL 用常数内存（~1.5KB）即可估上亿基数误差<2% A 需要 64 位/寄存器 B HLL 内存随基数线性增长 C 误差随 n 增长 D HLL 每寄存器仅需 6 位（64 位哈希的前导零范围），m=2048 时 1.5KB 即可保持约 2.3% 恒定相对误差到上亿基数 ✓ 正确答案
# 32. 为何布隆过滤器不能删除（会误清他人位）引出计数变种 A 删除只影响该元素自身 B BF 可以安全删除 C BF 的位被多元素共享，直接清位会误清他人造成假阴，计数布隆用计数器 +1/-1 支持删除 ✓ 正确答案 D 计数布隆计数器可无限计数
# 33. 布隆过滤器的假阳性率公式与 k、m、n 的优化关系 A 最优 k 是 (m/n)·e B k 越大假阳率越低无下界 C 假阳率与 m 无关 D 最优 k=(m/n)ln2 使置位概率 1/2、假阳率 (1/2)^k，m≈1.44n·log2(1/p) ✓ 正确答案
# 34. 计数布隆（Counting Bloom）如何支持删除与计数 A CBF 与 BF 空间相同 B CBF 删除不需要查询确认 C 计数器不会溢出 D CBF 用计数器支持删除，4 位计数器在负载高时溢出概率增大，需 8 位或周期重建 ✓ 正确答案
