Go 里的概率数据结构：用一点错换大量内存
来源：antonz.org — 2026-11-12
📋 概述
概率数据结构对「集合里有没有这一项」「有多少个不同项」「哪些项出现最多」给出近似答案，代价是精度，收益是内存。作者讲了布隆过滤器、Count-min sketch、HyperLogLog、T-digest 与 Top-k 五类，并发布 Go 包 unsure：每个结构核心一百到三百行，通常比同类实现快几倍，除标准库外零依赖。
🔑 核心要点
- 一百万个八字节字符串：普通集合约 64MB，1% 误判率的布隆过滤器只要 1.24MB
- 布隆过滤器不能删除、不能计数、不能遍历；容量按给定误判率预先定好，多塞了误判率就上升
- 典型用法是放在内存里挡掉昂贵查询：答「没有」就跳过，答「有」仍要回源核实
- 五个结构覆盖存在性、频次估计、基数估计、分位数与 Top-k 五类问题
- unsure 的取向是简单、快、无依赖，核心逻辑都控制在三百行以内
- 尺寸与项的大小无关，字符串越长，省下的内存差距越大
💡 金句
与集合、频次表这类确定结构不同，答案可能不精确，但作为回报，内存用量可以大幅下降。
← 返回 Lobsters 首页
👍 0
👎 0