数据结构

Jon Bentley 在他的经典著作《Programming Pearls》中记录了一个令人震惊的实验结果：在贝尔实验室和 IBM 的课程中，他给专业程序员几个小时的时间实现二分查找，结果超过 90% 的人写出了有 bug 的代码。更令人惊讶的是，二分查找算法首次发表于 1946 年，但第一个正确的实现直到 1962 年才出现——整整 16 年间，这个看似简单的算法一直以"错误"的形式流传。 ...

假设你面前有一组从小到大排好序的数字，需要找出其中任意两个数之和等于目标值的组合。最直观的想法是嵌套两层循环，逐一尝试所有配对——时间复杂度 $O(n^2)$，当数据量达到十万级别时，程序开始变得迟缓。 ...

当你第一次尝试实现斐波那契数列时,可能会写出这样的递归代码: public int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } 这段代码看起来简洁优雅,但当 n 达到 50 时,程序会运行很长时间才能返回结果。问题出在哪里?重复计算。计算 fib(5) 时会调用 fib(3),计算 fib(4) 时又会再次调用 fib(3)。随着 n 增大,重复计算的次数呈指数级增长——时间复杂度高达 $O(2^n)$。 ...

1953年1月，IBM研究员Hans Peter Luhn在一篇内部备忘录中提出了一个看似简单的想法：把数据放进"桶"里以加速查找。他当时的目的是解决一个日益紧迫的问题——科学文献的数量正以指数级增长，人工索引已经跟不上节奏。Luhn可能没想到，这个为了信息检索而设计的"桶"方案，会在七十年后成为计算机科学中最核心的数据结构之一。 ...

一个电商平台在双十一期间需要处理数百万个订单超时取消任务。每个订单创建后30分钟未支付就需要自动取消，释放库存。最直观的实现方式是在数据库中存储订单的创建时间，然后启动一个定时任务每隔几秒扫描一次，找出所有超时的订单。 ...

2018年之前，Visual Studio Code用户经常报告一个奇怪的问题：打开某些文件会导致内存溢出崩溃。罪魁祸首是一个35 MB的文件——听起来不大，但它有1370万行。VSCode为每一行创建一个对象，每个对象占用40-60字节，结果光是行数组就消耗了约600 MB内存，是原文件大小的近20倍。 ...

title: “跳表：概率如何击败确定性复杂度” date: “2026-03-07T04:35:05+08:00” description: “从William Pugh 1990年的原始论文出发，深入解析跳表的概率平衡原理、Redis与LevelDB的技术选型逻辑、与红黑树的权衡分析，以及为什么这种"用随机换简单"的设计哲学在高性能系统中持续发光。” draft: false categories: [“数据结构”, “算法”, “系统设计”] tags: [“跳表”, “Skip List”, “Redis”, “红黑树”, “概率数据结构”, “并发编程”, “LevelDB”] 1989年，马里兰大学的William Pugh向 Communications of the ACM 投递了一篇仅四页的论文。这篇论文提出了一个看似荒谬的问题：能不能用掷硬币的方式，替代红黑树中那些令人头疼的旋转操作？ ...