概率型数据结构与 Scala 读码手册

问题	优先看的结构	一句话说明
判断某元素是否存在	Bloom Filter / Cuckoo Filter / Quotient Filter	典型的 membership 问题，适合缓存穿透防护、黑名单、预过滤。
估计有多少个不同元素	HyperLogLog / KMV / Theta / CPC	典型的 distinct count 问题，适合 UV、独立访客、去重用户数。
估计某元素出现了多少次	Count-Min Sketch / Count Sketch	典型的频率估计问题，适合热点 key、热门 query、流量计数。
找最热的那些元素	Misra-Gries / Space-Saving / Top-K	你关心的不是所有元素，而是 heavy hitters 和榜单头部。
判断两个集合或对象像不像	MinHash / SimHash / LSH	适合查重、近重复检测、相似内容聚类和大规模候选检索。
从无限数据流抽样	Reservoir Sampling	不知道流会有多长，但想始终保留一个公平样本。
估计 p50 / p95 / p99	t-digest / KLL / GK	典型的 quantile 问题，适合请求时延、响应时间和尾延迟分析。
极小内存计数	Morris Counter	如果你只愿意付出很少的比特去换一个数量级估计。

Filter 家族最典型的代表是 Bloom Filter、Counting Bloom、Stable Bloom、Cuckoo Filter 和 Quotient Filter。它们共同关心的不是“完整保存集合”，而是“用更少空间快速判断某个元素是否值得继续查”。

共同目标

尽快回答 membership，减少后续昂贵查询。

共同代价

通常接受 false positive，但标准 Bloom 不接受 false negative。

共同做法

把元素压成 bit / fingerprint / local layout，再做局部检查。

可以把它们理解成“先挡掉明显不在集合里的东西”。这就是为什么 filter 类常被放在缓存穿透防护、黑名单、索引预过滤和流式去重的前面。

展开看：这一类为什么能省空间？

因为它们不保存原始元素，只保存被 hash 后的很少状态。Bloom 保存的是被点亮的 bit，Cuckoo/Quotient 保存的是 fingerprint 或局部布局信息，所以空间从“存对象”降成了“存指纹/状态”。

Sketch 不是单个算法，而是一类“把流压缩成统计摘要”的方法。HyperLogLog、Count-Min Sketch、Count Sketch、KLL、GK、t-digest、Theta、KMV 都属于这个大类，只是分别服务不同统计量。

子类	代表结构	回答的问题	摘要长什么样
Log / Cardinality	FM、LogLog、HLL	不同元素有多少	bucket + 前导零 / register
Frequency	CMS、Count Sketch、Misra-Gries	某个 key 多热	多行计数器 / 候选表
Quantile	GK、KLL、t-digest	p50 / p95 / p99	压缩后的排序摘要
Set / Similarity	KMV、Theta、MinHash	集合像不像	最小哈希值 / 采样签名

这一类的共同点很朴素：不存全量数据，只存足够恢复统计量的摘要。因为题目允许近似，所以这条路走得通，而且误差通常还能写清楚。

先找四件事，再看语法

拿到一段 sketch 实现，先不要从第一行逐字翻译。先扫字段和方法名，把它放进下面四个格子里。

状态

保存的是位数组、寄存器数组、二维计数矩阵、最小哈希样本，还是压缩摘要点？

更新

新元素进来后，是点亮 bit、计数加一、寄存器取 max，还是插入后再压缩？

查询

最后是检查若干槽位、取多行的 min、代入估计器，还是按 rank 找 quantile？

合并

两份局部状态之间，是按位 OR、逐项相加、逐寄存器取 max，还是合并后重压缩？

这四个问题都能回答时，算法已经读懂了大半。Scala 只是把同一套状态转移写成代码。

第 1 步：拆掉最常见的 Scala 外壳

课堂实现常用的语法很集中：class、val、var、def、Array、for、if，再加少量 map、foreach 和 sum。

class HyperLogLog(val p: Int) {
  val m: Int = 1 << p
  val registers: Array[Int] = Array.fill(m)(0)

  def add(x: String): Unit = {
    // 更新状态，不返回结果
  }

  def estimate(): Double = {
    // 读取状态，返回估计值
    0.0
  }
}

class

定义一种数据结构。构造参数 p 通常决定精度或空间。

val

名字不再绑定到别的对象，但数组里的内容仍然可以更新。

var

变量本身会变，常见于循环下标和中间计算。

def ...: Unit

没有返回值的更新函数，通常负责改变 sketch 状态。

看到 add、insert、update，先标成“更新”；看到 estimate、query、contains，先标成“回答问题”。

第 2 步：从容器认出状态

val bits = Array.fill(16)(false)
val registers = Array.fill(8)(0)
val table = Array.ofDim[Int](3, 10)

case class Entry(value: Double, g: Int, delta: Int)

Scala 写法	按算法语言翻译	常见结构
`Array.fill(n)(false)`	长度为 `n` 的位状态	Bloom Filter
`Array.fill(n)(0)`	一排寄存器或计数器	HLL、Counting Bloom
`Array.ofDim[Int](d, w)`	`d × w` 的计数矩阵	CMS、Count Sketch
`case class Entry(...)`	一条带多个字段的摘要记录	GK、t-digest
`Seq` / `Vector` / `Set`	少量样本、摘要点或签名	KLL、MinHash、Theta

例如 table(r)(c) 不需要理解成特殊语法，它就是二维数组第 r 行、第 c 列的计数器。

第 3 步：把位运算看成算法信号

HLL、LogLog、Bloom、CMS 的代码里经常出现位运算。它们通常不是为了炫技，而是在拆 hash、选桶或数前导零。

1 << p

计算 2^p，HLL 里常用来得到桶数 m。

x >>> k

无符号右移，常用来取 hash 高位作为 bucket id。

x & mask

只保留 mask 指定的位，常用来取槽位或 fingerprint。

numberOfLeadingZeros

计算前导零长度，是 LogLog/HLL 家族的核心统计信号。

val h = hash64(x)
val bucket = (h >>> (64 - p)).toInt
val w = (h << p) | (1L << (p - 1))
val rho = java.lang.Long.numberOfLeadingZeros(w) + 1

元素先被哈希成 64 位整数 h。
高 p 位被取出，变成桶号 bucket。
剩余位移到前面，交给 numberOfLeadingZeros。
rho 是这次更新观察到的前导零长度，接下来通常会和寄存器做 max。

第 4 步：完整读一遍 HyperLogLog

这段代码把前面 HLL 章节的四个环节全部写出来了。不要只看懂某一行，要能从输入 x 一直跟到最后的 distinct-count 估计。

class HyperLogLog(val p: Int) {
  val m: Int = 1 << p
  val registers: Array[Int] = Array.fill(m)(0)

  def add(x: String): Unit = {
    val h = hash64(x)
    val j = (h >>> (64 - p)).toInt
    val w = h << p
    val r = java.lang.Long.numberOfLeadingZeros(w) + 1
    registers(j) = math.max(registers(j), r)
  }

  def merge(other: HyperLogLog): Unit = {
    for (i <- registers.indices) {
      registers(i) = math.max(registers(i), other.registers(i))
    }
  }

  def estimate(): Double = {
    val z = registers.map(r => math.pow(2.0, -r)).sum
    0.7213 / (1 + 1.079 / m) * m * m / z
  }
}

状态：registers 保存了什么？

数组长度是 m = 2^p。每个位置对应一个桶，只保存这个桶见过的最大前导零长度。它不保存原始元素，也不保存全部 hash。

更新：一个新元素改了哪里？

h 被拆成桶号 j 和剩余位。剩余位产生 r，最后只有 registers(j) 可能变化，而且更新规则是 max(old, r)，不是加一。

合并：为什么逐寄存器取 max？

机器 A 和机器 B 在同一个桶里分别见过最大值 4 和 7，全局数据里该桶的最大值自然就是 7。所以 mapper 本地建 HLL，reducer 逐位置取 max，就能得到全局状态。

查询：估计器最终算了什么？

map(r => 2^{-r}).sum 先计算 z = Σ2^{-M[j]}，下一行再计算 α_m · m² / z。因此这不是简单平均寄存器，而是把所有桶的证据放进 HLL 的调和平均形式估计器，输出 distinct count。

第 5 步：用动词认出其他结构

结构	状态	更新时找什么	查询时找什么	merge 时找什么
Bloom Filter	位数组	`bits(pos) = true`	对应位是否全为 1	按位 OR
Count-Min Sketch	二维计数矩阵	`table(r)(c) += 1`	多行计数取 `min`	矩阵逐项相加
MinHash	签名数组	每个位置取 `min`	相同位置所占比例	逐位置取更小值
KLL / GK	摘要点或分层缓冲	`insert` + `compress`	按累计权重找 rank	合并后继续压缩

// 逐位置合并 HLL
for (i <- registers.indices) {
  registers(i) = math.max(registers(i), other.registers(i))
}

// 对每个哈希函数更新 Bloom
hashes.foreach { h =>
  val pos = (h(x) % m).toInt
  bits(pos) = true
}

// CMS 查询与 MinHash 比较
val frequency = counters.min
val similarity = signature.zip(otherSig)
  .count { case (a, b) => a == b }.toDouble / signature.length

这里的 foreach 就是循环，zip 是把两个数组按位置配对，count 是统计满足条件的位置数。把高阶函数翻译回朴素循环，不会影响你理解算法。

Bloom

预过滤：先排除一定不存在的 key，少做后面的昂贵查询。

HLL

去重计数：各节点维护小寄存器数组，最后低成本 merge。

CMS

流式频率：用固定大小矩阵估计热门 key，接受保守高估。

KLL / t-digest

延迟分位数：节点先做摘要，汇总后查询 p95、p99。

考试时按这六步读

圈字段：找出数组、矩阵、样本或摘要点，这些就是持久状态。
圈更新函数：看 add / update / insert 收到一个元素后改了哪些状态。
圈查询函数：看 query / estimate / contains 怎样把状态翻译成答案。
检查 merge：判断它是 OR、加法、max、min，还是合并后重建。
解释位运算：优先往桶号、mask、前导零、fingerprint 上翻译，不要停在语法名称。
收尾一句：说明它维护什么摘要、允许什么误差、为什么适合流式或分布式场景。

目标不是从零默写 Scala，而是看到实现后能沿着“状态 → 更新 → 查询 → 输出”把算法完整复原。

用很小的状态，看懂很大的数据

先看核心思想，再看算法名字

我想解决什么问题？

边界条件先说清楚

Filter 类：压缩存在性证据

Sketch 类：用有限摘要恢复统计量

Log 类：用稀有哈希模式反推规模

Similarity 类：让相似对象在短表示里靠近

Sampling 类：固定空间保留代表性

Redis / PostgreSQL / Apache DataSketches 里有什么？

Redis

PostgreSQL / Postgres

Apache DataSketches

大对比表

学习路线

建议顺序

面试速记版

共同思想与家族分类

第一层：先分问题

第二层：再看共同骨架

第四章：把算法翻译成 Scala

先找四件事，再看语法

状态

更新

查询

合并

第 1 步：拆掉最常见的 Scala 外壳

第 2 步：从容器认出状态

第 3 步：把位运算看成算法信号

第 4 步：完整读一遍 HyperLogLog

第 5 步：用动词认出其他结构

考试时按这六步读