HyperLogLog、t-digest 与 KLL

• 质心（centroid）结构与插入规则
• 按中心排序后两两配对的合并流程
• 合并保持 ε-近似分位数界的理由

Merging Digest 是确定性的分位数草图（quantile sketch）：维护若干质心（centroid，含均值 sum/w 与权重 weight），插入时把新点合并到最近的质心，受质心权重上限约束。合并（merge）两个 sketch 采用 two-by-two merging 策略：把两个 sketch 的质心按中心（mean）排序后两两配对，合并每一对质心——权重相加、中心加权平均；若合并后的质心超过权重上限则分裂成两个。该策略保证合并后仍满足 ε-approximate quantile 界，且可反复合并（分布式聚合场景）不累积破坏误差。

正确性来源：分位数草图把"压缩"定义为保留的质心能还原 (εn)-近似分位数；two-by-two 配对使任意分位数在合并后都能在原 sketch 的质心链上找到包围，质心权重上限约束合并过程中的信息损失，误差维持在 O(ε) 级别，空间 O((1/ε)·log(εn))。

合并策略的要点是"按中心排序后配对合并"保证单调性与界保持；与 GK 的"不可简单合并"形成对比，Merging Digest 的设计目标就是可合并（mergeable），面试时强调"两两配对 + 权重上限"两点。

• 随机游走式的跳桶算法
• 调和级数给出 O(log n) 期望步数
• 单调性与迁移量的推导

Jump Consistent Hash 解决"把 key 分配到 n 个桶、桶数变化时迁移最少"的一致哈希：f(key,n) 的定义是递推式的——从 n=1 开始，以概率 1/(n+1) 决定是否跳到更大的桶号，实现上维护当前桶 j 与随机数 r，用 while 循环按"j=⌊(n+1)/r⌋"的跳步前进直到失败，最终桶号即停止时的 j。期望步数 O(log n)，因为跳跃距离按调和级数增长。

单调性推导：固定 key，其映射桶号随 n 单调不减（每次跳桶只向更大号移动），因此桶数从 N 增到 N+1 时，只有落在"新桶接管区间"的 key 迁移，迁移概率 1/(N+1)；删除桶同理只影响相邻区间。每个 key 至多迁移一次，总迁移量 O(1/N)，这就是"跳跃一致哈希"相对环形哈希零内存、迁移最优的原因。

Jump 的优势是"零内存 + 完美单调性"，代价是每 key 映射 O(log n) 与无分片局部性；回答强调"单调不减 → 迁移 O(1/N)"的推导链即可，无需背诵实现细节。

• 假阳率公式 p≈(1-e^{-kn/m})^k
• 对 k 求导得最优 k=(m/n)·ln2
• 反解 m=-n·lnp/(ln2)²

给定元素数 n 与可接受假阳率 p，最优位数组大小 m=-n·ln p/(ln 2)²≈-1.44·n·ln p，最优哈希数 k=(m/n)·ln 2≈0.69·(m/n)。推导：假阳率公式 p≈(1-e^{-kn/m})^k，固定每元素位数 m/n 时对 k 求导，得最优 k=(m/n)·ln 2；回代得 p=(1/2)^k，反解出 m。例如 n=10^6、p=1% 时 k≈7、m≈9.6×10^6 位≈1.15MB。

工程含义：k 取整数并按公式向上取整，m 对齐字节；p 每降一个数量级，m 增加约 1.44n 位。这是布隆过滤器参数化的标准流程——先定 n、p，再算 m、k，最后用公式验算实际假阳率是否达标。

公式的两个锚点是"最优哈希数使每位被置位概率 1/2"与"此时假阳率 = (1/2)^k"；面试写出 m=-n·lnp/(ln2)² 与 k=(m/n)·ln2 即完整，推导过程能口述更好。

• 插入置位与查询判位的流程
• 位全 1 是"可能"、有 0 位是"一定不在"
• 假阴率为 0 与假阳率的来源

布隆过滤器用 m 位数组 + k 个独立哈希：插入时把 h1(x)..hk(x) 对应的位全部置 1；查询时检查这 k 位——若任一位为 0，则 x 一定不在集合中（假阴率为 0）；若全为 1，则 x 可能在（存在假阳率 p，因为不同元素的哈希位可能重叠）。"可能在/一定不在"的不对称性是布隆过滤器的核心性质，也是所有工程应用（缓存穿透防护、拼写预判等）的基础。

工程含义：缓存穿透防护正是利用"一定不在"的确定性——BF 判定不存在就直接短路，无需访问后端；误判只会造成一次多余的后端查询，不影响正确性。哈希独立性与均匀性是假阳率公式成立的前提。

把"位全 1"读作"可能"，把"有 0 位"读作"一定不在"，这一不对称来源于插入只置位、永不复位；面试时先讲流程、再点出不对称性，逻辑最清晰。

• 多代 HLL 分片与逐寄存器取 max 合并
• 过期片丢弃与窗口滑动的工程实现
• 合并后误差保持约 1.04/√m

Sliding HyperLogLog 在时间窗口（如最近 1 小时）上估计基数：简单方案是维护"多代 HLL"——把窗口切成若干时间片，每片一个 HLL，查询时合并窗口内所有片的草图（HLL 合并是逐寄存器取 max，可交换可结合），过期片直接丢弃；代价是内存与片数成正比。更精细的滑动（如"最近 N 条记录"）可按记录计数分代，精确滑动则用带时间戳的寄存器或衰减窗口，但会引入偏差。

工程取舍：多代 HLL 实现简单、误差可控（合并后误差仍约 1.04/√m，与单图同阶），是主流；每代再叠加稀疏表示与小基数修正可进一步省内存。窗口粒度的选择是"内存 vs 时间精度"的权衡：片越细滑动越平滑、内存越大。

滑动窗口的本质是"可丢弃旧数据"，HLL 的可合并性让"合并窗口内片"成为自然答案；回答落点在分代 + 过期淘汰 + 合并正确性三点，即算完整。

• 环结构下增删节点只影响相邻弧段
• 迁移量 O(1/N) 与单调性
• 虚拟节点 v 的负载方差 O(1/v) 与内存 O(Nv)

一致性哈希把哈希环分成 N 个弧段，每个节点负责其顺时针邻段；增加/删除一个节点只影响该节点的相邻节点——数据迁移量 O(1/N)（总数据被 N 段平分，迁移只涉及相邻段的数据）。相比取模哈希的"全部迁移"，这是单调性（映射稳定性）的直接收益。

虚拟节点：每个物理节点在环上放 v 个虚拟点，key 落到哪段由虚拟点决定；v 越大，各节点负责的弧段长度方差越小（负载方差按 O(1/v) 衰减，标准差与均值之比约 1/√v），但内存与查找成本 O(Nv) 上升。工程上 v 通常取 100-200，可把负载不均衡压到 10% 以内。

迁移量 O(1/N) 来自"环上邻域"几何，方差 O(1/v) 来自"更多抽样点平滑弧长"；两个结论一起构成一致性哈希的完整画像，面试时把"迁移"与"均衡"分开讲。

• (v, g, Δ) 元组链的结构
• 空间 O((1/ε)·log(εn)) 与 n 弱相关
• 确定性保证与不可合并的特性

Greenwald-Khanna（GK）是确定性的 ε-approximate 分位数草图：维护按值排序的元组 (v, g, Δ)（v 为值，g 为该元组代表的最小计数，Δ 为允许的计数误差上界），插入新值时合并满足 g+Δ 约束的相邻元组以压缩；任意时刻可用元组链回答任意分位数，误差 ≤εn，空间 O((1/ε)·log(εn))。在小数据集上，GK 的存储主要由误差要求 ε 决定而非 n——即使 n=10^6，1% 误差也只要几千个元组，远小于原始数据。

内存优势的量化：空间中的 log(εn) 因子随 n 增长极慢，主项是 1/ε；小数据上 GK 与"存全量排序"的差距变小但仍保持确定性的 ε 保证。相比 KLL（O((1/ε)·log log(1/δ))），GK 是确定性的、无需随机化即可达到 1% 界，但不可合并（合并会破坏 g、Δ 结构），这是其局限。

GK 的价值是"空间与 n 弱相关、与 ε 强相关"；回答强调"确定性、O((1/ε)log(εn))、不可合并"三特征即完整，与 KLL 的对比能体现深度。

• 排位表（permutation）与查表构建
• m 取素数、大小与冲突率的关系
• 查询 O(1) 与重建成本的权衡

Maglev Hash（Google 的负载均衡一致哈希）为每个后端维护一个"排位表"（permutation），构建大小为 m 的 lookup table：按后端顺序，每个后端从排位表起点尝试放入表，遇到占用就顺延到下一空位（next-slot 扫描）；构建后查询 O(1)——table[h(key)%m] 直接给出后端。lookup table 大小 m 须为素数（推荐 >100×后端数）：m 越大冲突概率越低、构建越平滑、平衡性越好，但构建时间 O(m×后端数) 与内存上升。

平衡性取舍：Maglev 的确定性构建保证构建后负载近似均匀；但后端增删时需重建表，受影响后端可能较多（迁移量比环形哈希大），不过重建开销 O(m) 可控。相比 Jump（零内存、O(log n) 映射）与环形哈希（虚拟节点），Maglev 用 O(m) 内存换 O(1) 查询与更均匀分布。

Maglev 的核心是"离线确定性构建 + 在线 O(1) 查表"；取舍词是 m（内存/构建）vs 平衡性与冲突，面试答出"m 为素数、next-slot 冲突处理"两点即到位。

• 最小哈希相等的概率恒等式
• k 次独立试验的频率估计
• 伯努利估计的方差下界

MinHash 估计集合相似度 Jaccard(A,B)=|A∩B|/|A∪B|：对每个元素计算哈希 h(x)，取集合的最小哈希值；关键恒等式：随机哈希下 P[min h(A)=min h(B)] = J(A,B)——并集里最小哈希元素落在交集的概率恰为 |A∩B|/|A∪B|。用 k 个独立哈希（或"单哈希取 k 个最小值"变体）得到 k 次独立试验，用频率估计 J，误差 O(1/√k)。

下界：Jaccard 估计等价于估计伯努利概率，方差反比于试验次数 k，要达到相对误差 ε（Chernoff/Chebyshev 界）需 k=O(1/ε²) 次独立试验，这是"哈希函数数"的信息论成本——与排序下界类似，无法用更少独立样本达到相同精度。

MinHash 把集合相似度化为"最小值相等的概率"，用 k 次试验平均逼近；下界回答紧扣"方差 ~1/k"，面试时先讲恒等式、再讲下界，逻辑完整。

• 随机超平面投影与符号位
• P[符号不同]=θ/π 的几何概率
• 汉明距离经 arccos 反推夹角

SimHash 把文档哈希成 64/128 位指纹：每个特征（词）用随机 ±1 向量加权累加，按累加和符号取位，得到高维向量到超立方体的映射。对偶关系：两个向量的指纹汉明距离的期望与两向量夹角成正比——对随机超平面 h，P[符号不同] = θ/π（θ 为两向量夹角，因为夹角为 θ 的两个向量被随机超平面分隔的概率是 θ/π），故 Hamming(A,B)/指纹长 ≈ θ/π；而余弦相似度 = cos θ，所以"余弦相似度 ↔ 汉明距离"经 θ=arccos(cos 相似度) 互转。

工程用途：把高维向量压成指纹后，海量文档去重/相似检索用汉明距离（异或 + popcnt，配合分块索引与抽屉原理）在常数时间内近似完成。注意这是期望意义上的近似：指纹位数越多、独立投影越多，汉明距离越接近 θ/π。

对偶关系来自"随机超平面划分"的几何概率；面试写出 P[h(A)≠h(B)]=θ/π 即抓住本质，再讲 arccos 互转与位运算加速。

• 最高随机权重选择机制
• 零内存、支持权重、查询 O(n)
• 与 Jump/Maglev 的对比

HRW（Highest Random Weight / Rendezvous hashing）：对 key 与每个节点计算权重 w(key,node)=hash(key,node)（可乘以节点权重因子），选权重最大的节点作为归属。性质：无需环或查表，单调性天然成立（节点集合变化只影响新节点接管/让出的 key，迁移比例 = 变化节点权重占比），查询 O(n)（n 为节点数），权重支持直接通过权重因子实现，每个 key 独立决策，避免热点级联。

工程案例：元数据分片、缓存路由、DNS 选服——变更节点时受影响 key 比例理想为 1/N；对比 Jump（O(log n) 映射、不可加权、零内存）与 Maglev（O(m) 内存、确定性均匀），HRW 胜在"零内存 + 加权 + 实现简单"，代价是每 key O(n) 计算（可缓存结果或并行计算）。

HRW 的卖点是"不需要全局状态的一致性哈希"；面试对比三种一致哈希（Jump/Maglev/HRW）更能体现体系化理解，答出"权重因子乘入随机权重"即算掌握加权机制。

• 只保留最小哈希的低 b 位
• 偏差修正公式 J≈(F-2^-b)/(1-2^-b)
• 位打包与字节对齐优化

b-bit MinHash 只保留每个最小哈希值的最低 b 位（其余位丢弃），把每哈希存储从 64 位降到 b 位。由于截断引入信息损失，直接取"低 b 位相等的频率"F 估计 Jaccard 会有偏差（系统性低估），需偏差修正：J ≈ (F - 1/2^b) / (1 - 1/2^b)——推导自贝叶斯式分解：低 b 位相等 = 元素真的相同（概率 J）或不同元素碰巧低 b 位相同（概率 (1-J)/2^b），故 F = J + (1-J)/2^b，反解即得。

字节级优化：b=8 时每个哈希恰好 1 字节，可用 char 数组与 SIMD 比较；b=1 时把 8 个哈希打包进一个字节按位存储；典型配置 b∈[1,8]，存储 = k·b 位，精度随 b 增大收敛到全量 MinHash。

偏差修正公式的本质是"观测频率 = 真 J + 随机碰撞 (1-J)/2^b"的反解；面试给出公式即到位，能解释"为什么 b 越大越接近无偏"更好。

• p-stable 分布随机投影与量化
• 碰撞概率是距离的单调递减函数
• LSH Forest 的多棵前缀树层级索引

Euclidean LSH 用 p-stable 分布构造：取随机向量 a（分量独立同分布 p-stable，p=2 即高斯分布），把点 x 投影到 a·x，再量化成桶号 ⌊(a·x+b)/w⌋（b∈[0,w) 均匀随机）。两个点落在同桶的概率是距离 d 的单调递减函数 c(d)，从而构成 (R,cR,p1,p2) 的 LSH 族，可级联（多表 + 多投影）用于近似最近邻（ANN）检索。

LSH Forest：不用固定桶宽，改用"每层随机投影 + 前缀树"：把投影值 a·x 的二进制表示插入字典树，查询时沿共享前缀找邻居，多棵树（森林）提高召回率，避免桶宽 w 的调参难题。参数：投影维数、树数、每树深度需按数据分布调优，且 p-stable 族对高维数据有维度灾难衰减。

p-stable 的要点是"投影值距离分布已知 → 碰撞概率是距离的单调函数"；LSH Forest 是"免桶宽调参"的工程化，面试把这两层讲清即可。

• scale function 定义质心数量上界
• k1(q)=δ/2π·asin(2q-1) 与 k2(q)=4δq(1-q)
• 合并超限则分裂、尾部分位数精度更高

t-digest 维护一组 (mean, weight) 质心并保持有序；插入时二分找到最近质心尝试合并，若合并后的质心权重超过 scale function k(q) 允许的界则拒绝合并（新点自成新质心）。scale function 刻画"分位数 q 处允许的质心最大数量"：k1(q)=δ/(2π)·asin(2q-1)（对称 asin 分布）与 k2(q)=4δq(1-q)（简单多项式）是两种常用选择；δ 控制精度（误差约 O(1/δ)）。由于 k1 在 q→0、1 处斜率发散，尾部质心更细密，极值分位数（如 P99.9）精度远高于中部，正契合监控场景对尾部分位数的重视。

合并规则：合并后质心权重不得超过其所在刻度 k(q) 的局部界（等价于每质心权重 ≤ N·Δk），超限则保持独立质心；查询分位数时线性扫描质心累积权重并插值。内存 O(δ)，尾部精度优于 GK/KLL，且支持合并。

t-digest 的识别特征是"scale function 控制质心粒度随分位数变化"；回答抓住"尾部更细 + 权重上界 + 插值查询"三要素即可，能写出 k1 表达式更显专业。

• ρ(x) 前导零与 2^ρ 的指数估计
• LogLog 的分桶几何平均
• HLL 调和平均与常数修正

HyperLogLog 的根源是 LogLog 思想：对每个元素哈希到均匀随机位串，记 ρ(x)=最长前导零个数+1；若集合含 n 个不同元素，期望最大 ρ ≈ log2 n，故用 2^(max ρ) 估计 n。单个寄存器方差太大，LogLog 用 m=2^p 个桶（按哈希前 p 位分桶）取每桶最大 ρ，再用几何平均 2^((1/m)Σρ_j) 压低方差，误差约 1.30/√m。

HLL 的改进：把几何平均换成调和平均——估计 E = α_m·m²/Σ 2^{-ρ_j}，调和平均对"个别特别大的 ρ 离群值"不敏感（max 型噪声被均摊），把误差降到约 1.04/√m；配合无偏常数 α_m 与偏差修正（小基数线性计数、大基数扩展）后，全量程相对误差约 1.04/√m。

回答链条"前导零→指数估计→分桶平均→调和平均"是 HLL 的全部演进史；面试按此递进即可覆盖 LogLog 与 HLL 的关系。

• 寄存器取 max 的合并操作
• 并集 = 两边最大值的可交换结合性
• 参数一致性与稀疏表示的处理

HLL 的可合并性来自"寄存器取最大值"：两个 HLL（同参数 p、同哈希）合并 = 逐寄存器 max(M1[j], M2[j])，结果等价于"对并集重新插入一遍"——因为每个寄存器记录的是"该桶中出现过的最大前导零"，并集在该桶的最大前导零 = 两边取 max。因此 PFMERGE / 分布式计数（多节点各自建草图后合并）正确、相对草图无信息丢失，误差保持约 1.04/√m。

工程要点：合并要求哈希函数与桶数一致（不同参数需先转换或重新编码）；稀疏表示合并时需先"解压"或直接对稀疏表做逐对合并；合并操作可交换可结合，适合 MapReduce 与流式聚合框架。

HLL 是"幂等可合并草图"的典型——寄存器 max 是并集的充分统计量；与 Count-Min 的逐桶求和、MinHash 的逐哈希取小形成三种合并模式，面试对比三者更显体系。

• 精确集合 O(n) 内存随基数线性增长
• 哈希均匀性代替精确成员关系
• 信息论上"近似计数"只需分布信息

精确统计流中不同元素个数必须记住每个已见元素（集合/哈希表），内存 O(n)（n 为不同元素数）：10^9 基数 × 8 字节哈希 ≈ 8GB，数据流场景内存与基数线性增长、不可接受。而基数估计不需要精确集合：HLL 只用 m 个 6 位寄存器（如 16384×6bit≈12KB）即可达 0.8% 误差——信息论上"近似计数"把空间从 O(n) 压到 O(log log n)（每寄存器 6 位足以表达前导零的 log log 范围）。

关键洞察：估计基数只需知道"哈希值的稀疏性"（前导零长度分布），无需存储元素本身；用哈希的均匀性代替集合的精确成员关系，误差与 n 无关、只与寄存器数相关。这解释了"为什么必须放弃精确性才能流式计数"。

回答的核心是"成员信息 vs 分布信息"的信息论区分——统计"有几个"不必知道"是哪些"；面试从内存爆炸讲起、引出哈希均匀性，逻辑最顺。

• 虚拟点均匀撒布与弧长方差
• 负载方差按 O(1/v) 衰减
• 内存 O(Nv) 与收敛收益递减

一致性哈希中物理节点 P 在环上放 v 个虚拟点后，key 被映射到 P 的概率 = P 的虚拟点在环上覆盖的弧长占比。若 v 个虚拟点独立均匀随机，P 负责的弧段是 v 段弧长之和，其方差按 O(1/v) 衰减：负载（弧长占比）标准差与均值之比约 1/√v——v=100 时约 10% 波动，v=1000 时约 3%，这是"独立同分布求和"的中心极限效应。

代价：内存 O(Nv)（每虚拟点一个哈希值与有序结构），查找需二分 O(log Nv)；v 继续增大收益递减（方差按 1/√v 收敛缓慢），工程上 v 取 100-200 是常见折中，配合 key 数量级选择。

方差按 1/√v 收敛是"均值平滑"的中心极限现象；回答给出"方差 O(1/(vN²))、内存 O(Nv)"的权衡即完整，能画出收敛曲线更佳。

• 分 m 桶的随机平均与方差 O(1/m)
• α_m 无偏常数的渐近修正
• 空桶线性计数 E=m·ln(m/V)

stochastic averaging：把流分成 m=2^p 个桶（按哈希前 p 位分桶），每个桶独立估计并平均，方差从单桶的 O(1) 降到 O(1/m)——桶间独立的"子估计平均"即随机平均；代价是每桶样本数变少，引入小样本偏差。估计式 E = α_m·m²/Σ_j 2^{-ρ_j}（调和平均），α_m 是 m 相关的无偏化常数（m 大时 α_m≈0.7213/(1+1.079/m)）。

小基数偏差修正：基数小时（n ≤ 2.5m 且空桶多），调和平均估计严重偏低，改用线性计数：用 V=空桶数，E = m·ln(m/V)（基于"空桶比例 ≈ e^{-n/m}"反解，无偏性好）；中等基数用原始估计加查表修正；大基数（接近 2^32）用 64 位哈希扩展。这些修正使 HLL 在全量程误差 ≈1.04/√m。

两类修正——"α_m 修正调和平均的系统偏差"与"空桶线性计数修正小基数"——回答时点出触发条件（n 与 m 的相对大小）即到位。

• sparse 列表存 (桶号, ρ) 对
• 非零寄存器超过约 m/2 时切换 dense
• 稀疏省内存、稠密省时间的权衡

HLL++ 对寄存器存储做两段式：sparse 表示用稀疏列表记录 (桶号, ρ) 对（仅存非零寄存器），适合小基数——插入时检查桶号是否存在，维护成本 O(sparse 长度)；dense 表示用 m×6 位数组直接存储，插入 O(1) 随机访问。切换阈值：当非零寄存器数超过约 m/2（或列表大小超过 dense 内存预算）时切换，工程实现（如 Redis）是"稀疏占用超过阈值字节（如 3000 字节）转 dense"。

切换的工程收益：小基数（如 <50k）时 sparse 只占几十到几百字节，dense 固定 12KB+；大基数后 dense 的定长存储与随机访问更高效。切换是"按数据规模选择存储形态"的典型自适应结构，也影响小基数下 PFCOUNT 的精确性（sparse 可退化线性计数）。

sparse/dense 是时间-空间的双曲线：稀疏省内存、稠密省时间；回答阈值（≈m/2 非零寄存器）即抓住 HLL++ 的核心设计，Redis 的字节阈值可作为工程佐证。

• rank 截断与前导零编码
• 与 HLL 编码的杂交
• full-rank 变体的空间-精度曲线

HyperMinHash 把 MinHash 与 HLL 的压缩编码结合：MinHash 需要记录每个最小哈希的"秩"（rank，即最小哈希的数值，约 log2(1/J) 位），HyperMinHash 只存每个最小哈希的前 r 位（rank 截断），并配合"桶 + 前导零"的 HLL 式编码，把每哈希降至 r 位 + O(1) 前导零信息；full-rank 变体（r 取全部位）相比普通 MinHash（64 位/哈希）可实现 3-5 倍空间压缩，同时保持 Jaccard 估计精度（截断偏差可分析并修正）。

原理：最小哈希值的分布是均匀的，其二进制"秩"可用前导零编码压缩（类似 HLL 的 ρ）；存 rank 的前 r 位、低位用概率计数近似，估计 Jaccard 时结合 rank 分布反推。空间-精度曲线比 MinHash 平缓，适合大规模集合相似度（基因序列、图节点邻域、去重检索）场景。

HyperMinHash 是"MinHash 的秩信息用 HLL 式前导零压缩"的杂交；回答抓住"rank 截断 + 前导零编码"两个机制，再给出 3-5 倍数字即完整。

• 分层存储与均匀压缩（compaction）
• 层容量几何增长消去 log n 因子
• 与 GK 元组链的对比

KLL（Karnin-Lang-Liberty）把数据分层次（level）存储：插入的元素进入 level 0，满时做"全压缩"（uniform compaction）——把本层元素均匀减半并升入下一层，同时部分层做"部分压缩"保持精度。空间分析的关键：各层容量按几何级数增长，绝大部分元素驻留在低层且每层容量 O(1/ε)，层数只需 O(log log(1/δ)) 即可把失败率压到 δ——因为全压缩是确定性的均匀降采样，错误贡献随层数指数衰减，需要的层数是对数对数级别，故总空间 O((1/ε)·log log(1/δ))。

与 GK 对比：GK 用 (v,g,Δ) 元组链，空间 O((1/ε)·log(εn))，含对 n 的 log 依赖；KLL 用分层全压缩把"数据规模 n"的 log 因子换成"失败率 δ"的 log log 因子，且 log log(1/δ) 几乎可视为常数。GK 是确定性结构，KLL 引入随机性（失败率 δ），但空间更紧。

回答的关键是"层容量几何增长 + 全压缩的指数级错误衰减"；对比 GK 的 log(1/δ) 依赖，讲清 log log 的来源（层数而非每层容量）即算掌握。

• 三种平均方式的误差常数 1.30/1.05/1.04
• 截尾平均与调和平均的改进机理
• 小基数修正的成熟度差异

三者的演进是"压低误差常数"的历史：LogLog 用 m 桶的几何平均，误差 ≈1.30/√m，但几何平均对离群的大 ρ 敏感（系统性高估）；SuperLogLog 引入截尾平均——排序后只取最小的约 70% 桶的均值，去掉尾部 max 型噪声，误差降到 ≈1.05/√m；HLL 用调和平均 E=α_m·m²/Σ2^{-ρ} 替代几何平均，配合 α_m 常数与偏差修正，误差压到 ≈1.04/√m。

基数范围适用性：小基数（n≲2.5m）三者的绝对误差都受小样本偏差困扰，HLL 的线性计数修正最成熟（可直接用空桶比例）；大基数下调和平均的方差优势稳定保持。实际工程（Redis、DataSketches）几乎只用 HLL，LogLog/SuperLogLog 作为历史对比出现。

误差常数 1.30→1.05→1.04 的每一步都对应"更稳健的平均方式"（截尾、调和）；回答按此脉络展开即展示理解而非背诵，末尾点出小基数修正差异更完整。

• 存储层之前短路负判定
• 正判定回源与假阳无害
• 合法 key 集合的维护与重建

布隆过滤器防缓存穿透的部署位置：位于缓存与数据库之间（或缓存之前）——请求到达时先查 BF：若 BF 判定"一定不存在"，直接短路返回（不查缓存、不查 DB），因为假阴率为 0；若"可能存在"才继续查缓存/DB。这样把"大量查询不存在 key"的流量挡在存储层之外。BF 的误判（假阳）只会带来一次多余的下层查询，不影响正确性。

工程细节：BF 维护"合法 key 集合"——数据写入/预热时同步插入已知合法 key；BF 中"存在"的 key 查 DB 仍可能不存在（假阳），处理方式与普通未命中一致（如回源后写短期空值缓存）；还需处理 BF 的过期重建窗口（数据淘汰导致 BF 失真）与内存预算（m≈1.44n·log2(1/p)）。另一种部署是仅 DB 前（旁路），取决于"不存在 key 是否也打缓存"的流量结构。

部署要点的本质是"BF 的负判定绝对可靠、正判定需回源"；回答落点在短路路径与假阳不伤正确性，再补充合法 key 集合的同步维护。

• min 估计器与碰撞计数
• 单射错误（只上偏）的论证
• ε||f||₁ 概率界

Count-Min 用 d×w 计数矩阵：插入 x 时对每行 C[j][h_j(x)]++（j=1..d）；点查询估计 f̂(x)=min_j C[j][h_j(x)]（取 d 个桶的最小值）。每个桶的计数 = x 的真实频率 + 与 x 碰撞的其他元素频率之和，即 C[j][h_j(x)] ≥ f(x)，所以 min 也是 f(x) 的上界——单射错误：只高估、永不低估。期望过估计 = 每行碰撞元素频率和 ≤ n/w（w 为行宽），取 w=e/ε、d=ln(1/δ) 时，以概率 ≥1-δ 有 f̂(x) ≤ f(x)+ε||f||₁。

因此 CM 的回答模式是"上界 + 概率保证"：f̂(x) ≥ f(x) 恒成立，f̂(x) ≤ f(x)+ε||f||₁ 大概率成立；用 min 而非 sum 是"只保留碰撞最少的桶"，这是 CM 精度的关键设计。

CM 的"单射错误"即"只上偏不偏下"；回答给出 min 估计器与 ε||f||₁ 界即完整，能解释"为什么取 min"更显深度。

• 指纹存储与候选桶定位
• 删除支持与查询 ≤2 次桶访问
• 空间 1.05× vs 1.44× 与实现复杂度

Cuckoo Filter 用"指纹 + partial-key cuckoo hashing"：每个元素存 f 位指纹，两个候选桶 i1=h(x)、i2=i1⊕h(指纹)；插入冲突时逐出旧指纹换桶（布谷鸟式），支持删除——删除 = 在候选桶中清除匹配指纹。相比 Bloom：删除支持（BF 不可删除）、查询延迟确定（最多 2 次桶访问 + 桶内小扫描，BF 需 k 次哈希与位访问）、空间效率（CF 约 1.05× 信息论下界 vs BF 约 1.44×，同 n、p 下 CF 更省）、负载上限高（95%+ 仍可用，BF 需预知 n 否则假阳率恶化）。

代价：CF 的删除对"同指纹不同元素"存在假删除风险（可用计数或更长指纹缓解）、插入最坏需要循环驱逐（需扩容或随机重哈希）、实现复杂度高。选型：需要删除/遍历/高负载选 CF，简单稳定与固定容量选 BF。

对比维度锁定"删除、空间倍数、查询延迟、负载因子"四个指标即可覆盖；高频考点数字是 1.05× vs 1.44× 与 2 次 vs k 次，回答时点出。

• PFADD 的幂等更新与 PFCOUNT 估计
• PFMERGE 逐寄存器取 max 的并集语义
• p=14、6 位寄存器与稀疏切换阈值

Redis 的 PFADD key element 更新 HLL（对 element 哈希分桶并更新寄存器），PFCOUNT 返回基数估计（小基数走线性计数/稀疏精确路径），PFMERGE dest src... 把多个 key 的 HLL 逐寄存器取 max 合并到 dest——语义与并集基数一致：PFMERGE 后 PFCOUNT(dest) ≈ |∪ 集合|。实现细节：Redis HLL 默认 p=14（16384 桶 × 6 位 ≈12KB），稀疏表示超过约 3000 字节转稠密；PFCOUNT 对单 key 直接估计，对多 key 先临时合并再估计（避免污染源）。

工程语义：PFADD 相同元素幂等（同一哈希分桶）；多源基数去重用 PFMERGE；稀疏表示下小基数可精确返回（线性计数）。复杂度：PFADD 稠密 O(1)、稀疏 O(非零寄存器数)；PFCOUNT 稠密 O(1)。

Redis HLL 是"参数固定（p=14、6 位）的工程实现"；回答围绕 PFADD/PFCOUNT/PFMERGE 的语义与稀疏/稠密切换，再补充 12KB 与 3000 字节两个数字即完整。

• 分桶随机平均的 √m 方差缩减
• 调和平均对 max 型噪声不敏感
• α_m 无偏化的配合

HLL 分 m 桶（stochastic averaging）把方差降 √m 倍：每个桶的估计 ~2^ρ，桶间独立，平均后相对误差约 1.04/√m。调和平均 E=α_m·m²/Σ2^{-ρ_j} 是关键：桶内 ρ 是"max"型统计量（对分布右尾敏感），几何/算术平均会被个别异常大的 ρ 拉高；调和平均对小值敏感、对大值不敏感，正好压制"某桶恰好出现超长前导零"的尖峰噪声，配合 α_m 常数修正后误差更紧。

直觉：所有桶共享同一哈希分布，某桶 ρ 偏大是随机事件；调和平均的倒数均值对这类右尾事件稳健，等价于"用中心趋势而非极值"估计。这也是 HLL 比 LogLog 常数好的根本原因。

答题链"分桶降方差（√m）+ 调和平均抗离群（α_m 无偏化）"是 HLL 设计的两大支柱；面试先讲分桶、再讲平均方式的选择理由，逻辑最清晰。

• 两种草图回答的问题类型
• 指纹信息（rank）与寄存器信息（前导零）
• 经并集基数间接互转与误差放大

两者都是基于哈希的随机化摘要，但回答不同问题：MinHash 估计"集合相似度 Jaccard"（交集与并集之比），HLL 估计"集合基数"（不同元素个数）。MinHash 的指纹（k 个最小哈希的秩）支持两两相似度、聚类、近重复检测；HLL 的寄存器（前导零分布）只支持基数（含并集基数），无法给出相似度。反过来 MinHash 也能粗估基数，但精度不如 HLL。

数学关系：J(A,B)=|A∩B|/|A∪B| 是基数比；同时估计并集基数（HLL 合并）与单集基数可得 |A∩B|=|A|+|B|-|A∪B|，从而算 Jaccard，但减法放大误差；直接相似度场景用 MinHash 更合适。存储：MinHash k=200 个 64 位 ≈1.6KB 换相似度精度，HLL 12KB 换基数精度，成本结构不同。

选型一句话"相似度用 MinHash、基数用 HLL"；回答对比信息类型（秩值 vs 前导零分布）即显深度，能说出互转的误差放大更好。

• 小样本偏差与均值算子偏差
• α_m 渐近无偏修正
• 三区间分段修正策略

HLL 的原始估计（无 α_m 的调和平均）是有偏的：分桶后每桶样本少，2^{-ρ} 的期望与真实概率不相等（小样本偏差），同时桶数为 m 而非无穷，均值算子与期望交换引入系统性偏差。修正：乘无偏常数 α_m（随 m 渐近使偏差趋于 0，m 越大越准）；小基数用线性计数 E=m·ln(m/V)（基于空桶占比）或论文的 bias correction 查表；基数极大时用 64 位哈希扩展。修正后 HLL 渐近无偏、相对误差约 1.04/√m。

实践语义：Redis 等实现对小基数（≤阈值）直接用精确缓存或线性计数，对中等基数用修正表，大基数用 α_m 估计——三区间分段保证全量程低偏差。

"有偏/无偏"的讨论必须分区间：小基数（空桶多）偏差最大，α_m 修正大基数渐近偏差；回答给出触发条件与三区间策略即完整。

• 寄存器位数只取决于哈希位长（6 位）
• m=2048 时 1.5KB 与约 2.3% 误差
• 相对误差恒定与 n 无关

HLL 的寄存器数是 m=2^p 个，每个寄存器只需 log2(log2 n) 位（记录最大前导零，64 位哈希下前导零最多 64，即 6 位）：p=11（m=2048）时内存 2048×6 位 = 1.5KB，误差 1.04/√2048≈2.3%；p=14（16384 桶）12KB 时误差约 0.81%。寄存器位数只取决于哈希值位长（64 位哈希 → 前导零范围 0..63 → 6 位），与基数 n 无关，这是 O(log log n) 位的来源。

为什么能覆盖上亿基数：哈希均匀性保证"前导零 ≥ k"的概率 2^{-k}，n 个元素中最大前导零约 log2 n；只要 n<2^64，寄存器值域不溢出，估计式 α_m·m²/Σ2^{-ρ} 自动缩放到任何基数。误差只由 m 决定、与 n 无关（相对误差恒定），所以"常数内存、恒定相对误差"同时成立。

回答锚点"寄存器 6 位够用因为哈希 64 位 + 误差只依赖 m"；1.5KB 的代价是约 2.3% 误差，换取 O(log log n) 空间的本质，面试把这两点讲清即可。

• 位共享与置位不可逆
• 删除误清他人位的假阴后果
• 计数布隆的 +1/-1 修复

布隆过滤器的位被多个元素共享：k 个哈希位中任一位都可能由多个元素置 1。删除元素若把其 k 位清 0，会误清其他元素的置位（假阴），使后续查询错误地"一定不存在"。这是"置位不可逆、位共享"的必然结果——除非记录每个位被置过几次。

计数变种：Counting Bloom Filter 把位换成计数器（典型 4 位），插入时 k 个计数器 +1、删除时 -1（计数器归零才算清空该位），支持删除且不误伤；代价是空间 ×4。工程上还需周期性重建（计数器饱和）或"删除前先查询确认"防止下溢，这些细节构成 CBF 的完整实践。

不可删除的根源是"多位共享 + 无引用计数"；计数变种是直接修复，回答讲清"误清他人位 → 计数"因果链，再补下溢与重建细节即完整。

• 位清空概率与泊松近似
• p=(1-e^{-kn/m})^k 的推导
• 最优 k=(m/n)·ln2 与 m≈1.44n·log2(1/p)

假阳率推导：插入 n 个元素后某位仍为 0 的概率 (1-1/m)^{kn} ≈ e^{-kn/m}；查询不在集合的元素 x，其 k 个哈希位全被置 1 的概率 p=(1-e^{-kn/m})^k。固定 m/n（每元素位数），对 k 求导取最优 k=(m/n)·ln 2，此时每位被置位概率 1/2，p_min=(1/2)^k=(0.6185)^{m/n}；即假阳率随 m/n 指数下降，m≈1.44n·log2(1/p)。k 太小则冲突分散不足、太大则位提前置满，均衡点恰在置位概率 1/2。

工程建议：先按业务定 n 与 p，用公式算 m、k（取整），再按公式验算实际假阳率；m 取字节对齐并预留 10% 余量（n 预估误差）。这就是标准 BF 参数化的完整闭环。

优化关系一句话"k 最优使每位 1/2 概率置位，p=(1/2)^k"；推导从位清空概率出发，面试能口述推导链即可。

• 计数器 +1/-1 与归零语义
• 4 位计数器在负载高时的溢出概率
• 位宽选择与周期性重建

Counting Bloom Filter（CBF）把每位换成计数器（C[i]∈[0,2^b-1]）：插入时 k 个计数器 +1、删除时 -1（计数器归 0 才算该位清空），查询逻辑不变（k 位计数全 >0 → 可能）。删除的正确性：计数器记录多位共享的"重叠次数"，-1 只在该元素插入过时安全；需要查询确认或约定不删不存在的元素，否则计数器下溢。

位宽选取：典型 b=4（16 级）。溢出分析：某计数器被命中的次数近似二项/泊松分布，期望 λ=nk/m；负载高（λ 大）时 4 位溢出概率显著——例如 λ=8 时 P[Poisson(8)>15] 已达约 1% 量级，故工程上把 λ 控制在 ≤4 或用 8 位计数器、或周期性重建（扫描重置高位）。空间代价 = b×m，即普通 BF 的 4-8 倍。

CBF 的工程要点是"计数器位宽与负载的溢出权衡"；回答给出"期望 λ=nk/m 与 4/8 位选择"即完整，泊松近似给出量化直觉更好。