
1. 先把选型这把尺子立起来刚接手一个日活百万级的业务时我遇到过一个典型场景运营要在千万级用户里算“昨天有多少人下单”还要查“这个手机号是不是已经在活动名单里”。第一版代码我用了常规的哈希表和数据库去重跑了一晚上内存直接冲到了机器上限进程被系统杀掉。后来把 BloomFilter 和 HyperLogLog 换上去同样的活儿内存占用从几十 G 掉到了百来兆。这件事让我彻底改变了一个习惯在做数据量大的功能之前先想清楚我需要的是“精确答案”还是“足够好的答案”这个判断直接决定了该用哪个数据结构。这篇文章要聊的五个结构——BloomFilter、HyperLogLog、跳表SkipList、Bitmap含 Roaring Bitmap、并查集Union-Find——都属于那种“平时想不起来一旦用上就再也不想换回去”的东西。它们解决的共同痛点是数据规模一旦越过单机内存的舒适区常规的HashMap、Set、排序数组就开始不听话了要么内存扛不住要么延迟抖得厉害。而这五个结构靠的是概率、位运算和巧妙的索引设计把空间和时间的账重新算了一遍。如果你写过一两年业务代码被内存、去重、排行、连通性这类问题烦过那这篇内容基本都能直接用。如果你刚入行我会尽量把推导过程写出来不让你只抄结论。下面每一个结构我都会按照“它解决什么问题—原理怎么推—参数怎么算—落地怎么踩坑”的顺序讲中间穿插我自己或者同事踩过的真实坑当然细节都做了脱敏处理。1.1 为什么“内存”是这五个结构的共同答案先想一个问题为什么精确结构会这么吃内存因为精确结构把“值”本身存下来了。你要判断一个 URL 在不在集合里最直观的做法是存字符串假设平均 60 字节一亿条就是 6GB还要加上哈希表的桶指针、负载因子留白实际占用往往翻倍到 12GB 以上。而 BloomFilter 判断“在不在”压根不存原值只存一串比特位一亿条、1% 误判率大概 120MB 就够了差了整整一百倍。跳表和并查集属于另一类它们不是省空间而是把“操作复杂度”压下来。跳表让有序集合的插入、删除、范围查询都落在对数级别而且实现里没有旋转这种容易写错的逻辑并查集则把“动态连通性”这种听起来很玄的问题压缩成了几行近乎常数时间的代码。Bitmap 是纯粹的空间魔法一个用户一年的签到记录只占 46 字节还能直接拿位运算算连续天数。所以这五个结构其实是三条路BloomFilter 和 HyperLogLog 走的是“放弃绝对精确换空间和海量吞吐”的路子跳表和 Bitmap 走的是“换一种数据组织方式把常数压到极致”的路子并查集走的是“用增量信息代替重复计算”的路子。把这三条路分清后面的选型就有了基本坐标。1.2 三条判断线空间、精度、可删除性我在做技术评审的时候习惯用三个问题去卡一个结构是否合适这三条线基本能筛掉 90% 的错误选型。第一条是空间预算。你要先算清楚数据量级和单条成本。比如一亿条数据如果每条能压到 1 bit那就是 12.5MB任何机器都能扛如果每条要 64 bit那就是 800MB单机还行但多副本就贵了如果每条要 512 bit那就是 6.4GB这时候就得考虑分片或者换结构了。我在表格里会给出几个常见规模的推荐组合方便你直接对号入座。第二条是精度要求。这决定你能不能接受概率结构。判断“用户是否已签到”就不能有误判签到失败用户会投诉但判断“这个 URL 是否已经抓过”稍微多抓一次重复内容几乎没影响误判完全可以接受。HyperLogLog 估出来的 UV 和真实值差 0.8%业务方如果只是看趋势、做大盘监控这个误差远远够用但如果用来算分成、发奖金那必须走精确统计或者做定期对账校正。第三条是可删除性。这一条最容易被忽略也是踩坑最多的地方。标准 BloomFilter 不支持删除因为一个位可能被多个元素共享你把它清掉别的元素就“被消失”了。HyperLogLog 更彻底单个元素的删除在结构里根本无法表达只能整段重建。如果业务里有“取消关注”“删除商品”“撤销操作”这样的需求用之前必须想好替代方案。2. BloomFilter拿 1% 的误判换 99% 的内存BloomFilter 是这五个结构里知名度最高的一个也最容易被滥用。它的核心承诺只有一句话能百分百确定“某样东西一定不在集合里”但只能说“某样东西可能在集合里”。注意这不是缺陷而是它省内存的全部原因——它用一串哈希映射后的比特位代替了原始数据。2.1 它要解决的问题比它本身更重要我见过很多团队引入布隆过滤器是为了“技术上有亮点”结果用错地方。它真正发光发热的场景是那些**“绝大多数查询的结果都是不存在”**的场合。最经典的就是缓存穿透恶意请求或者程序 bug 导致大量不存在的 key 打到缓存和数据库缓存层每次都没命中压力全部落到后端存储上。加一层布隆过滤器不存在的 key 直接被挡在门口成本只有一次位运算。第二个高频场景是去重。爬虫抓取时判断 URL 是否抓过、推荐系统判断内容是否已经推给某个用户、消息队列消费端做幂等判断这些场景的特点都是“写入量巨大、判断只需要一个是/否、偶尔误判可以接受”。第三个场景是名单过滤比如把一批有风险的 IP 或者账号提前灌进过滤器请求进来先过一遍能挡掉大部分剩下的再走精确校验。注意布隆过滤器的误判方向是单向的。它说“不在”那一定不在它说“在”有概率是假的。所以它适合做“前置拦截”不适合做“最终裁决”。任何拿它当唯一判据的设计早晚会出事。反过来有些场景千万别用它。比如“用户是否已经被封禁”误判会导致正常用户被封这是事故“这个订单号是否已经支付过”误判会导致重复发货或者拒绝正常支付。这类必须精确的场景老老实实走数据库唯一索引或者精确集合。2.2 位数组长度和哈希个数的计算过程很多人用布隆过滤器是随手new BloomFilter(1000000, 0.01)参数从哪来的不知道。我把公式推一遍以后你就能自己算了。设位数组长度为m单位 bit插入元素个数为n哈希函数个数为k目标误判率为p。一个元素插入后某个特定位仍为 0 的概率是(1 - 1/m)^(kn)近似等于e^(-kn/m)。那么误判率就是“k 个位全部被置 1”的概率p ≈ (1 - e^(-kn/m))^k对这个式子求极值可以得到两个最优解最优哈希个数: k (m/n) * ln2 ≈ 0.693 * (m/n) 最优位数组: m -n * ln(p) / (ln2)^2 ≈ 1.44 * n * log2(1/p)也就是说每元素需要的比特数只和误判率有关和数据量本身无关。这是个非常漂亮的性质。我算了几组常用值直接查表就行目标误判率 p每元素比特数 m/n推荐哈希个数 k1 亿元素的位数组大小10%4.793约 60 MB1%9.587约 120 MB0.1%14.3810约 180 MB0.01%19.1713约 240 MB0.001%23.9617约 300 MB拿 1% 那一行验算一下m 1e8 × 9.58 9.58e8 bit换算成字节是9.58e8 / 8 ≈ 1.2e8 B也就是约 114MBk 9.58 × 0.693 ≈ 6.64向上取整到 7。如果同样的 1 亿条 URL 用字符串存按平均 60 字节算光数据就是 6GB还不算哈希表开销。一百倍的差距这就是它存在的理由。这里有个反直觉的点k不是越大越好。位数组大小固定时哈希函数多了每次插入会置更多位位数组更快被填满误判率反而上升。上面那个k值是理论最优实际工程里向下取整、四舍五入都可以影响很小。2.3 落地时必须处理的四个细节第一哈希函数怎么选。不要真的去写 k 个独立的哈希算法。标准做法是用两个独立的哈希值h1、h2然后通过g_i h1 i * h2生成第 i 个位置这叫双重哈希实测误判率和理论值几乎一致。哈希函数本身用 MurmurHash 或者 xxHash 这类速度快的非加密哈希别用 MD5、SHA1一条数据算一次 SHA1 的时间够你算几十次 MurmurHash 了。第二容量必须预估不能动态扩。这是最坑的一点。布隆过滤器的误判率是建立在“元素数不超过设计容量”的前提下的一旦实际插入量超过预估位数组被填满误判率会急剧飙升。我见过一个案例设计容量 500 万实际写进去 3000 万误判率从 1% 涨到了接近 40%下游数据库直接被放大的流量打崩。所以设计容量一定要按峰值的 1.5 到 2 倍来估。第三删除需求要提前识别。标准布隆过滤器不支持删除。真需要删除有两个方案一是用计数布隆过滤器Counting Bloom Filter每个位换成一个小的计数器通常 4 bit删除时减一代价是内存涨 4 倍二是用 Cuckoo Filter布谷鸟过滤器它存的是元素指纹支持删除空间效率还比计数布隆高在误判率 1% 时每元素大概只要 12 bit 左右。如果你的场景既要查又要删我建议一开始就上 Cuckoo Filter别等改造。第四重建和持久化的成本。布隆过滤器在内存里是易失的重启就没了。常规做法是把位数组定期快照到磁盘启动时加载。但要注意重建 1 亿条数据往往要跑几分钟到几十分钟这段时间要么降级直接放行所有请求要么用双缓冲切换。我的经验是准备两套位数组一套服务中、一套后台预热预热完成再原子切换指针切换过程业务无感。3. HyperLogLog12KB 撑起亿级去重计数如果说布隆过滤器解决的是“在不在”那 HyperLogLog 解决的是“有多少个不同的”。这个需求听起来简单实际做起来非常费劲精确去重你必须把每个元素都存下来一亿个不重复的用户 ID 就是几百 MB 到 GB 级别而且每次查询都要遍历集合。HyperLogLog 把这件事压到了固定 12KB无论你统计一千万还是一百亿个不同元素内存都不变。3.1 从抛硬币说起为什么看“最长连续零”这个算法的直觉其实来自一个生活场景。假设你不停地抛硬币记录“第一次出现正面之前连续出现反面的最大次数”。如果你抛了很多轮观察到的最大连续反面次数是r那你会怎么猜总共抛了多少轮合理的猜测是2^r轮左右——因为连续 r 次反面的概率是2^-r要出现这么长的连串你至少得抛2^r次。HyperLogLog 就是这么干的只不过它抛的是“哈希值”。对每个元素算一个 64 位哈希在二进制里从低位或高位往另一端数看第一个 1 出现在第几位记为ρ。如果集合里所有元素的ρ最大值是r那基数大概就是2^r。问题是这样估计的方差太大单次实验根本不能信所以算法把哈希值的前若干位当作“桶编号”把元素分散到m个桶里每个桶各自维护自己的最大ρ最后对所有桶的值做调和平均。用调和平均而不是算术平均是因为算术平均会被个别极端大的值带偏而调和平均对异常值不敏感这是这个算法能保持稳定误差的关键。小基数的时候还要做线性计数修正Linear Counting否则桶还有很多空着的时候估计值会有明显偏差。3.2 桶数、误差与内存的三角关系误差公式很简单标准误差 ≈ 1.04 / √mm是桶的数量必须是 2 的幂。反推一下就能知道要多少桶目标误差桶数 mp桶编号位数内存每桶 6 bit1.63%4096123 KB0.81%163841412 KB0.41%655361648 KB0.20%26214418192 KB主流实现默认取m 16384也就是 12KB 内存、0.81% 误差这个点性价比最高。我算过一笔账一个亿级 UV 的统计任务精确去重需要几百 MB 内存加几秒的合并时间HyperLogLog 只要 12KB 加毫秒级误差 0.81% 相当于“100 万和 100.8 万”的差别对看盘监控完全无感。6 bit 每桶是有讲究的。桶里存的是ρ值理论上最大值取决于哈希位数64 位哈希最多到 50 左右6 bit 能表示 0 到 63正好够用而且刚好能对齐字节边界方便批量处理。如果哈希只有 32 位那 5 bit 就够了但现在没人省这一个 bit。3.3 实操批量写入、合并与序列化用一个常见的内存缓存服务举个例子。它的 HyperLogLog 命令很直白# 单个写入返回 1 表示基数发生了变化 PFADD uv:20240601 user_1001 # 批量写入一次传多个元素比循环单次调用快一个数量级 PFADD uv:20240601 user_1001 user_1002 user_1003 # 读取估算值 PFCOUNT uv:20240601 # 合并多天的数据结果写进一个新的 key PFMERGE uv:week user_20240601 user_20240602 user_20240603 # 注意 key 命名 PFCOUNT uv:week合并是它的隐藏杀器。假设你要算最近 30 天的 UV不需要把所有元素重新灌一遍只要把 30 个 12KB 的结构合并起来就行合并后误差不会显著放大因为合并本质上是对每个桶取最大值误差还是原来那个量级。这个特性让它在做多维度、多时间粒度的统计时极其方便属于“离线预聚合 在线合并”的标准套路。如果要自己实现或者在不支持该结构的环境里落地核心代码大概长这样import hashlib P 14 # 桶编号位数 M 1 P # 16384 ALPHA 0.7213 / (1 1.079 / M) def _hash64(data: bytes) - int: # 用 md5 示意实际生产建议换成 xxhash/murmurhash3 的 64 位输出 return int.from_bytes(hashlib.md5(data).digest()[:8], big) def _rho(w: int, bits: int 64) - int: 从低位往高位找第一个 1 出现的位置全 0 返回 bits1 if w 0: return bits 1 pos 0 while (w 1) 0: w 1 pos 1 return pos 1 class HLL: def __init__(self): self.registers bytearray(M) def add(self, item: str): h _hash64(item.encode()) idx h (64 - P) # 高 P 位做桶编号 w h ((1 (64 - P)) - 1) # 剩余位算 rho r _rho(w, 64 - P) if r self.registers[idx]: self.registers[idx] r def count(self): import math inv sum(2.0 ** (-r) for r in self.registers) raw ALPHA * M * M / inv # 小基数修正 zeros self.registers.count(0) if raw 2.5 * M and zeros 0: return M * math.log(M / zeros) return raw这段代码里有两个细节值得说。一是桶编号取高位、ρ算低位顺序不能反否则桶之间会有相关性误差会变大。二是小基数修正必须做当元素数量在几百到几千这个量级时原始估算会明显偏高线性计数修正能把它拉回来。注意HyperLogLog 不支持删除单个元素也不支持“查询某个元素是否在里面”。它只是一个计数器别指望拿它当集合用。如果业务有“取消关注后 UV 要减一”的需求只能整段重建或者改用 Bitmap 精确存储代价是内存大得多。4. SkipList有序集合为什么偏偏选了它跳表这个结构我第一次看的时候觉得有点“土”——不就是给链表加了几层索引吗怎么就能和红黑树平起平坐后来自己写了一遍又对比了几种有序结构的实际表现才明白它赢在哪同样的对数复杂度实现难度低了一个数量级而且范围查询特别顺手。4.1 用概率换掉旋转操作普通链表查一个元素要 O(n)因为只能一个一个往下走。跳表的思路很朴素既然走楼梯慢那就修几部电梯。最底层是完整的链表上面每隔几个节点抽一个出来做成索引层再往上继续抽形成多层结构。查找时从最高层开始能往右就往右右边太大就往下掉一层这样每一层基本只走常数步总复杂度是 O(log n)。关键在于“抽多少个出来”。如果是严格每隔 2 个抽 1 个那插入删除之后就要维护这个比例代价和平衡树的旋转差不多白忙一场。跳表的做法是让每个节点自己掷骰子决定层数每次插入时先按概率p决定要不要升到上面一层升上去之后再掷一次直到失败或者到达最大层数。这个随机化听起来很不靠谱但数学上可以证明只要p选得合适整体高度依然是对数级别且期望性能稳定。这个设计带来的最大好处是并发友好。红黑树插入时要做旋转一旋转就要锁住一大片节点跳表插入只需要修改局部几个指针而且如果只在最底层做链表操作上层索引甚至可以异步构建。很多高性能内存数据库的有序集合选跳表而不是平衡树核心原因就在这里。4.2 层数与查询代价的估算p一般取 0.25 或 0.5。取 0.25 时一个节点升一层的概率是 1/4升两层的概率是 1/16。元素个数为n时期望层高是L ≈ log_(1/p) n一亿个元素、p 0.25log_4(1e8) ln(1e8) / ln4 18.42 / 1.386 ≈ 13.3也就是平均 13 到 14 层。所以设一个 32 层的上限绰绰有余实际实现里通常会硬编一个MAX_LEVEL 32用位运算配合随机数生成层数比循环掷骰子快。查找的时候每层的期望步数是1/p。p 0.25时每层平均走 4 步13 层加起来大概 52 次指针跳转对比红黑树的 2 倍 log2(n) ≈ 54 次比较基本在同一个量级。但跳表的每一步就是一次内存访问加一次比较分支预测友好实测在内存里经常比红黑树快 20% 到 30%。// 层数生成用位运算代替循环实测比 while(random) 快 2~3 倍 private int randomLevel() { int level 1; // ThreadLocalRandom 返回的随机位低两位都为 0 的概率是 1/4 while ((ThreadLocalRandom.current().nextInt() 0x3) 0 level MAX_LEVEL) { level; } return level; }范围查询是跳表的另一个甜点。找到起点之后直接在最底层沿着链表往后走就行完全不需要像树那样做中序回溯。做“取分数排名前 100 的用户”“取时间区间内的日志”这类操作代码写出来短得离谱。4.3 红黑树、跳表、B树怎么选这三个经常被拿来对比但它们的战场其实不一样。我整理了一张表基本覆盖了日常遇到的情况维度跳表红黑树B 树实现难度低核心 100 行左右高删除和旋转容易写错中高涉及页分裂合并点查询O(log n)O(log n)O(log_B n)磁盘场景优势大范围查询极优底层链表直接扫一般需中序回溯优叶子节点链表相连并发修改优局部指针修改差旋转影响面大中需要页锁或 latch内存开销每节点平均 1/(1-p) 个指针每节点 3 指针 颜色位按页分配有空间浪费典型用途内存有序集合、排行榜通用有序映射磁盘索引、数据库存储引擎结论很清楚纯内存、要范围查询、有并发写入选跳表数据要落盘、要按页读写选 B 树只是要一个有序字典元素不多红黑树或者直接在语言标准库里挑就行。别为了炫技在业务代码里手写平衡树标准库的实现比你写的稳。5. Bitmap 与 Roaring Bitmap把集合压进比特位位图是所有压缩结构里最“暴力”的一种既然你要表示一个整数在不在集合里那我就用第 n 位表示整数 n。一亿个用户 ID 对应一亿个比特12.5MB查询就是一次位运算快得没有道理。但它有个致命弱点如果 ID 是稀疏的比如只有 1000 万个活跃用户散布在 10 亿的 ID 空间里位图就要占 125MB而且绝大部分位是 0。Roaring Bitmap 就是为了解决这个问题出现的。5.1 位图的基本盘与它的死穴先说位图本身它在几个场景里几乎是不可替代的。签到日历是典型例子一个用户一年的签到状态只要 365 bit46 字节存进一个字段里毫无压力。要算“连续签到天数”不用循环把位图按位与上自己右移一位反复几次就能定位断点要算“本月签到次数”一次 popcount 就出来了。这类计算在数据库里做要写一堆 SQL用位运算在应用层做就是几行代码。活跃用户交集也是位图的强项。判断“昨天登录过且本周下过单”的用户两个位图按位与一下再数一下 1 的个数毫秒级出结果。如果用户 ID 范围可控比如自增 ID位图方案几乎是最优解。死穴也很明确ID 空间必须相对稠密且上界不能太大。如果 ID 是 UUID 或者雪花算法生成的长整型直接做位图会撑爆内存。这时候要么先做 ID 映射维护一个自增到 UUID 的对照表要么直接上 Roaring Bitmap。5.2 Roaring 的三类容器与切换阈值Roaring Bitmap 的核心思路是分段 自适应容器。它把 32 位整数的高 16 位当作块编号低 16 位落在对应的块里。每个块最多容纳 65536 个值然后根据这个块里的元素密度自动选择三种容器之一容器类型适用情况单个元素成本切换阈值数组容器Array元素稀疏2 字节存 16 位值元素数 ≤ 4096位图容器Bitmap元素稠密每块固定 8 KB元素数 4096运行容器Run连续区间多每段 4 字节连续段占比高时启用那个 4096 的阈值不是随便定的。数组容器存 4096 个 16 位整数正好是 8192 字节和位图容器占的 8KB 完全相等超过这个点位图就比数组更省。这个临界点的设计非常优雅是 Roaring 论文里明确推导过的结论。运行容器是后来的优化专门针对“大量连续整数”的场景。比如一批自增 ID 从 100000 到 120000用位图要 8KB用运行容器只要 2 个 4 字节记录起点和长度8 个字节差了一千倍。判断是否切换到运行容器一般看连续段的平均长度超过阈值常见是 32 左右就值得切换。实际用的时候还有个坑频繁的随机插入删除会导致容器反复切换每次切换都要重建整个容器性能抖得厉害。解决办法是加一点滞后区间比如超过 4096 之后到 4800 才切到位图跌回 3400 才切回数组避免在临界点附近来回横跳。5.3 签到与活跃统计的落地写法签到场景我推荐直接用long数组做位图一年 365 天最多 6 个long代码简单可控public class SignBitmap { private final long[] bits new long[6]; // 6 * 64 384 位够一年 public void sign(int dayOfYear) { int idx dayOfYear 6; // 除以 64 int off dayOfYear 63; // 模 64 bits[idx] | (1L off); } public boolean isSigned(int dayOfYear) { return (bits[dayOfYear 6] (1L (dayOfYear 63))) ! 0; } /** 计算最长连续签到把位图和自己右移一位做与直到结果全 0 */ public int maxConsecutive() { int best 0; long[] cur bits.clone(); int rounds 0; while (!allZero(cur)) { rounds; long carry 0; for (int i cur.length - 1; i 0; i--) { long nextCarry cur[i] 1L; // 记录最低位供下一轮错位用 cur[i] (cur[i] 1) | (carry 63); if ((cur[i] bits[i]) ! 0) best Math.max(best, rounds); carry nextCarry; } } return best; } private boolean allZero(long[] arr) { for (long v : arr) if (v ! 0) return false; return true; } }提示上面这段连续签到的写法是为了演示思路实际生产里用循环位移会更稳妥。如果你追求简洁也可以直接循环遍历每一位365 次判断对现代 CPU 来说微不足道别为了省那点时间引入 bug。活跃统计则更适合 Roaring Bitmap。假设你要算“最近 7 天都活跃的用户”把 7 天的位图做交集就行。Roaring 的库基本都提供了原生的and、or、andNot操作而且会智能选择容器级别的算法两个都是位图容器就直接 64 位字做与一个数组一个位图就遍历数组去查位图。这层优化不需要你操心。6. 并查集连通性问题的一把快刀前面四个结构都在处理“集合”或者“计数”并查集处理的是另一类问题动态连通性。给定一堆两两连接的关系快速判断“这两个东西是不是连在一起的”。听起来像图论算法但它的实现短到令人发指二十行代码就能解决很多需要反复 DFS 才能搞定的问题。6.1 两个优化缺一不可并查集的基础版本很简单用一个数组parent[i]记录 i 的父节点查根就一直往上找合并就把一个根挂到另一个根下面。但只用这个版本如果合并顺序是恶意的树会退化成一条链查找变成 O(n)。第一个优化是路径压缩查找的时候把沿途所有节点直接挂到根上。这样第二次查同一个节点就是 O(1)。第二个优化是按秩合并或者叫按大小合并合并的时候把浅的树挂到深的树下面避免树高增加。用秩rank记录树高上界或者用 size 记录节点数都可以。这两个优化必须一起用才能保证均摊 O(α(n))α是反阿克曼函数在 64 位整数范围内不超过 5实际等于常数。只做路径压缩不做按秩合并理论最坏还是 O(log n)只做按秩合并不做路径压缩也是 O(log n)。很多教程写了路径压缩就收工在小数据量下看不出问题量大起来就慢了。6.2 完整实现与一次真实的反例先看标准写法public class UnionFind { private final int[] parent; private final int[] rank; private int count; // 连通分量个数 public UnionFind(int n) { parent new int[n]; rank new int[n]; count n; for (int i 0; i n; i) parent[i] i; } public int find(int x) { // 路径压缩迭代写法避免深递归爆栈 int root x; while (parent[root] ! root) root parent[root]; while (parent[x] ! root) { int next parent[x]; parent[x] root; x next; } return root; } public boolean union(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; // 本来就连通可能成环 if (rank[ra] rank[rb]) { int t ra; ra rb; rb t; } parent[rb] ra; // 矮树挂到高树下 if (rank[ra] rank[rb]) rank[ra]; count--; return true; } public boolean connected(int a, int b) { return find(a) find(b); } }我在一个社交关系合并的需求里见过反例。当时为了“代码简洁”只写了路径压缩没写按秩合并合并逻辑是固定的parent[rb] ra。数据量小时一切正常上线三个月后用户关系变复杂出现了几次很深的树一次“判断两个账号是否属于同一个人”的查询扫了几十万个节点接口 P99 从 8ms 涨到 400ms。补上按秩合并之后P99 立刻回到 9ms 以内。这个优化不是锦上添花是必需项。6.3 它能用在哪、不能用在哪并查集最典型的应用是账号合并同一个人的多个账号因为手机号、设备号、身份证等维度被识别为同一个人需要把它们归到一组。每来一条“账号 A 和账号 B 是同一个人”的信号就union(A, B)最后count就是去重后的人数find就能拿到每个账号的归属组。第二个场景是网络和集群的连通性判断一批机器两两之间有心跳判断整个集群是否还连通、分成了几个孤岛。第三个场景是图片处理里的连通区域标记把相邻的相似像素合并成一个色块。还有最小生成树的 Kruskal 算法判断加入一条边会不会成环就是用并查集做的。它不能做的事也很明确。第一不支持删除不能把两个已经合并的组再拆开需要拆分就得重建或者用更复杂的可撤销并查集。第二不记录路径它只告诉你“连不连通”不告诉你“怎么连的”想要最短路径还得用 BFS。第三只处理无向关系有向图的强连通分量是另一套算法。7. 五个结构横向对比与选型速查聊完五个结构我把它们放在一张表里对比一下这个表我在评审会上用过很多次基本能帮人快速锁定方向。7.1 一张表看完结构解决什么问题空间成本精度支持删除典型场景BloomFilter判断元素是否可能存在约 10 bit/元素p1%有假阳性无假阴性否缓存穿透拦截、URL 去重、名单过滤HyperLogLog估算去重后的基数固定 12 KB相对误差约 0.81%否只能重建UV 统计、独立访客估算、多日合并SkipList有序集合的增删改查与范围查询每元素约 1.33 个指针p0.25精确是排行榜、延时队列、有序索引Bitmap / Roaring稠密整数集合的存储与位运算稠密 1 bit/元素稀疏自适应精确是签到、活跃交集、标签位图并查集动态连通性判断与分组2 个 int 数组精确否账号合并、集群连通、连通域标记选型的时候我一般按这个顺序问自己数据要不要精确要精确就排除前两个。需不需要删除需要删除就排除布隆和 HLL、并查集。ID 是不是稠密整数是就优先位图。要范围查询上跳表。只问连不连通上并查集。四五个问题问下来答案通常就唯一了。7.2 常见异常与排查速查表这几个结构出问题的方式都挺有特点我把遇到过的整理成表现象大概率原因排查动作处理方式布隆过滤器误判率突然飙升实际插入量超过设计容量统计写入条数 vs 设计容量扩容重建容量按峰值 2 倍设计布隆过滤器把确定存在的元素判为不存在哈希实现不一致或位数组未持久化检查哈希种子、重启后是否重新加载统一哈希实现位数组落盘 校验HLL 小基数时数值明显偏大未做线性计数修正对比小样本真实值补上m * ln(m/zeros)修正HLL 合并后误差放大多个 HLL 桶数不一致检查各实例的 precision 参数全局统一p14不允许混用跳表查询退化成线性层数生成概率写错或随机数种子固定打印节点层数分布修正p换用高质量随机源Roaring 内存占用远超预期数据稀疏但落到同一个高位块统计每个块的元素数分布检查 ID 是否高位集中考虑加盐打散并查集查询越来越慢缺按秩合并或路径压缩写成递归爆栈打印最大树深补齐两个优化find改迭代并查集合并结果和预期不符索引从 0/1 起始不一致打印parent数组统一索引基准初始化时校验提示这几个结构都有个共同特点——在小数据量下几乎不会暴露问题。所以我的习惯是在压测环境里故意灌入 10 倍设计容量的数据专门看它们的退化曲线。布隆过滤器灌超容量、HLL 灌小基数、并查集用递增顺序合并这三个测试能提前发现 80% 的隐患。我个人在实际操作中的体会是这五个结构真正的价值不在于“炫技”而在于把一个问题从“做不了”变成“做得起”。很多需求不是技术上无解而是用精确方案成本太高、延迟太大被迫砍掉。换成概率结构或者位运算结构之后成本降了两个数量级原本要排期的功能当天就能上线。但代价也很实在你必须比用普通集合更清楚数据的分布、增长速度和业务对误差的容忍度否则省下来的内存迟早会以线上事故的形式还回去。最后分享一个我常用的判断方法拿到一个新需求先问“这个结果的误差会影响钱吗”。影响钱、影响用户权益的老老实实用精确结构哪怕多花十倍的资源只是影响看板、影响排序、影响体验细节的大胆上概率结构省下的资源去做更有价值的事。这条线划清楚之后选型就不再纠结了。