入门：LRU / 跳表 / 布隆过滤器的定位与适用场景
基于通用数据结构概念 · 核于 2026-07
速查
- 本叶讲三件事：LRU 缓存（淘汰策略）、跳表（有序集合的概率结构）、布隆过滤器（概率型去重）——它们都不追求理论最优，而是追求「工程上够用、常数小、实现可控」。
- LRU 缓存：淘汰「最久没被访问」的元素——命中
get/写入put时把元素提到队头，容量满时淘汰队尾。用哈希表 + 双向链表实现，get/put全 O(1)。 - LRU 为何 O(1)：哈希表负责 O(1) 定位节点；双向链表负责 O(1) 移动到头/删尾（单链表做不到 O(1) 删已知节点的前驱）；两者各补对方的短板。
- 虚拟头尾节点（dummy head/tail）：链表首尾各加一个哨兵节点，任何真实节点都夹在中间，边界处理（空表、单节点、头尾操作）统一为「中间操作」——这是 LRU 实现最易错也最关键的技巧。
- 跳表（Skip List）：在有序链表之上叠加多层概率索引，查找时从最高层起逐层下探，把单层链表的 O(n) 查找压到期望 O(log n)——是红黑树的概率替代。
- 跳表为什么用概率层级：每个节点以概率 p（通常 1/2）「晋升」到上一层，期望一半节点上一层、四分之一上两层……高度期望 O(log n)；这避免了平衡树的旋转，实现远比红黑树简单。
- 跳表的工程地位：Redis
ZSET（有序集合）、LevelDB/RocksDB 的 MemTable、Redisson 的分布式锁都用跳表——选它而非红黑树，主要因为实现简单、并发友好、支持范围查询。 - 布隆过滤器（Bloom Filter）：一个 m 位的位数组 + k 个哈希函数；插入时把 k 个哈希位置都置 1，查询时检查这 k 位是否全为 1——全 1「可能在」，有 0「一定不在」。
- 布隆过滤器的核心性质：可能误判（false positive），但绝不漏判（no false negative）——「判不在」一定准，「判在」可能错；误判率随填充率上升而升高。
- 布隆不支持删除：标准版多位共享 bit，删一个会误删别的；要支持删除用 Counting Bloom Filter（每位改成计数器，删除时减 1）。
- 布隆的典型应用：缓存穿透防护（先过滤不存在的 key）、爬虫 URL 去重、垃圾邮件/恶意 URL 黑名单、HBase/LevelDB 读放大优化——都是「海量数据 + 容忍误判 + 要省空间」的场景。
- 布隆参数选择：给定元素数 n 和目标误判率 p，最优位数组大小
m ≈ -n·ln p / (ln2)²，最优哈希函数个数k = (m/n)·ln2；典型「每元素约 9.6 bit + 7 个哈希」可达 1% 误判率。 - 三者共同思想：用一个数据结构补另一个的短板——LRU 拼 哈希+链表；跳表拼 多层索引+概率；布隆拼 多哈希+位数组+接受误判。工程选型看的不是理论最优，而是「延迟、内存、实现复杂度、并发」的综合权衡。
- 进阶顺序：LRU 缓存 → 跳表与布隆过滤器 → 参考。
一、LRU 缓存：淘汰「最久没被访问」的
LRU（Least Recently Used）是缓存淘汰策略中最经典的一种：当缓存满了需要腾位置时，淘汰「最长时间没被访问过」的元素。它的依据是程序的局部性原理——最近被访问过的数据，近期再次被访问的概率也高；反之，很久没碰的数据，短期内大概率也不会被碰。
LRU 的关键操作有两条：
- 访问（
get）/写入（put）时把该元素移到「最近」端——表示它刚被用过。 - 容量满时淘汰「最久」端的元素。
如果用普通数组实现，每访问一次就要把元素搬到头部，O(n)；如果只用链表，搬移 O(1) 但查找 O(n)。LRU 的标准做法是哈希表 + 双向链表——哈希表存「key → 链表节点」的映射，O(1) 找到节点；双向链表让「把节点移到头/删尾」O(1)（因为双向链表已知节点就能拿到前驱，单链表不行）。两者一拼，get/put 全 O(1)。
LRU 是工程世界的事实标准：Redis 的 maxmemory-policy allkeys-lru、MySQL Buffer Pool 的改良版 LRU、操作系统页面置换算法（Unix 早期用 LRU 的近似 CLOCK）都基于这个思想。
二、跳表：有序集合的概率结构
有序集合（Sorted Set）要支持「插入、删除、按 score 查找、范围查询」。理论上的最优解是平衡二叉搜索树（AVL、红黑树），全部 O(log n)。但红黑树实现复杂（旋转、颜色翻转、边界情况多），并发也不友好（旋转要锁大块结构）。
跳表给出了一种概率替代：在一个有序链表之上叠加多层「快车道」索引。最底层（Level 0）是完整的有序链表；每个节点以概率 p（通常 1/2）「晋升」到上一层，形成稀疏的索引层。查找时从最高层起，一路向右走、走不动就下一层，像走楼梯一样快速定位，期望 O(log n)。
跳表相对红黑树的优势：
- 实现简单：无旋转、无颜色翻转，插入/删除就是链表节点操作 + 随机层级。
- 并发友好：链表是局部结构，加锁粒度小（只锁相邻节点），不像树旋转要锁大块。
- 天然支持范围查询：底层是有序链表，定位起点后沿链表顺序扫即可。
代价是空间换时间（多层索引约 1.33 倍指针开销）和概率保证而非确定保证（期望 O(log n)，极低概率退化）。Redis ZSET 同时存哈希表（按 member 查 score，O(1)）+ 跳表（按 score 范围查，O(log n)），正是这种工程取舍的典范。
三、布隆过滤器：概率型去重的「第一道防线」
海量数据下精确判重（如「这个 URL 爬过吗」「这个邮箱是黑名单吗」「这个 key 在缓存里吗」）用哈希表太费空间——1 亿个 URL 每个平均 50 字节就是 5GB。布隆过滤器用一个 m 位的位数组 + k 个哈希函数，把每个元素压到约 10 bit（比哈希表省 1~2 个数量级）。
工作机制：
- 插入：对元素算 k 个哈希，对应位数组的 k 个位置全置 1。
- 查询：算 k 个哈希，检查这 k 位——全是 1「可能在集合里」，有任何一位是 0「一定不在」。
关键性质：可能误判（false positive），但绝不漏判（no false negative）。因为不同元素的哈希位可能重叠（都置成 1），导致「不在集合里的元素」恰好 k 位全 1 被误判为「在」；但「真在集合里的元素」插入时 k 位必全置 1，查询绝不会判错。这让布隆过滤器特别适合做**「第一道防线」**：先用它快速过滤掉绝大多数不存在的查询，没过滤掉的再用慢但精确的方式（查数据库/缓存）二次确认。
典型应用：缓存穿透防护（数据库前挡一层布隆，不存在的 key 直接挡掉）、爬虫 URL 去重、垃圾邮件/恶意 URL 黑名单、HBase/LevelDB 读放大优化（读之前先布隆过滤避免无谓磁盘 IO）。
下一步
理解了三者的定位后，下一步拆开看 LRU 的 O(1) 实现——哈希表 + 双向链表 + 虚拟头尾节点如何把 get/put 都做到 O(1)，见LRU 缓存：哈希表 + 双向链表。