工程实用结构（LRU / 跳表 / 布隆过滤器）
工程实用结构是把「理论数据结构」按真实系统的延迟、内存、并发要求打磨后落地的一组高频组合：LRU 缓存用哈希表 + 双向链表在 O(1) 内做「最近最少使用」淘汰；**跳表（Skip List）**用多层概率索引链表给有序集合提供 O(log n) 的查找/插入/删除，是平衡树的概率替代；**布隆过滤器（Bloom Filter）**用位数组 + 多哈希做空间极省的概率去重，允许误判但绝不漏判。三者都不追求理论最优，而是追求「工程上够用、常数小、实现可控」——LRU 背后是 Redis/操作系统页置换的真实淘汰策略，跳表是 Redis ZSET 的底座，布隆过滤器是缓存穿透、爬虫 URL 去重、垃圾邮件黑名单的守门人。
这三类结构合述的原因是：它们共同展示了**「用一个数据结构补另一个的短板」**的工程思想。哈希表 O(1) 查找但无序、链表 O(1) 增删但查找慢——LRU 把两者拼起来各取所长；单层有序链表查找 O(n)——跳表用「概率多级索引」把这条路压到 O(log n)；海量数据精确判重空间扛不住——布隆过滤器用「多哈希 + 位数组 + 接受误判」换空间。理解了它们，就理解了「为什么 Redis 选跳表而不是红黑树」「为什么布隆过滤器能省 100 倍内存」这类工程选型问题。
评价
优点
- LRU 缓存：
get/put均 O(1)（哈希表定位 + 双向链表 O(1) 移动到头/删尾）；命中率高（淘汰最久未访问的，贴近「局部性原理」）；虚拟头尾节点让边界处理极简——是 Redis、MySQL Buffer Pool、操作系统页置换的事实标准淘汰策略 - 跳表：查找/插入/删除全 O(log n)，且实现远比红黑树简单（无旋转、无颜色翻转）；天然支持范围查询（沿底层链表顺序扫）；并发友好（链表局部加锁即可，不像树要旋转锁大块）；Redis
ZSET、LevelDB MemTable 的核心结构 - 布隆过滤器：空间极省（每个元素约 10 bit 即可，比哈希表省 1~2 个数量级）；插入/查询 O(k)（k 个哈希，常数小）；绝不会漏判（在集合里的元素一定判定为「在」）——是缓存穿透、URL 去重、垃圾过滤的「第一道防线」
缺点
- LRU 缓存：需要额外存双向链表节点（每元素多 2 个指针 + 哈希表项，空间开销约为数据的 2~3 倍）；全容量淘汰时退化（如顺序扫描整个数据集会逐个淘汰热数据，工程上常用 LRU-K 或 LFU 改良）；纯 LRU 在高并发下链表操作需加锁
- 跳表：基于概率，最坏 O(n)（虽然期望 O(log n)，但极低概率层级退化）；空间换时间（多层索引，额外约 1.33 倍指针开销）；查找常数比数组二分略大（要跨层下探）
- 布隆过滤器：存在误判（false positive，不在集合里可能误判为「在」，误判率随填充率上升而升高）；不支持删除（标准版多元素共享 bit 位，删一个会误删别的，需用 Counting Bloom Filter）；不能枚举元素（只能判存在性，无法遍历还原集合）
本叶地图
- 入门 —— 三种结构的定位与适用场景速览、各自的核心数据结构与复杂度、何时选 LRU/跳表/布隆过滤器
- LRU 缓存：哈希表 + 双向链表 —— LRU 淘汰策略、为何哈希 + 双向链表能 O(1)、虚拟头尾节点、Redis/页置换应用
- 跳表与布隆过滤器：概率数据结构 —— 跳表多层索引概率层级 O(log n)、Redis zset；布隆过滤器位数组 + 多哈希、误判不漏判、Counting BF、缓存穿透/URL 去重
- 参考 —— 三种结构复杂度表、LRU 代码模板、跳表骨架、布隆参数选择、易错点
交互演示
- LRU 缓存可视化演示 —— 哈希表 + 双向链表的 O(1) 访问与淘汰
- 跳表可视化演示 —— 多层概率索引链表的查找与插入
- 布隆过滤器可视化演示 —— 位数组 + 多哈希的概率判重