问什么决定选什么结构 — 用探测次数与高度预先计数
一句话总结
同样是“查找”，问的是什么——恰好一条、一个区间，还是前几名——不同，合适的结构也不同。而且这种结构要付出的代价，在测量时间之前，就可以先用探测次数、树的高度、替换次数这类确定性的数字算出来。
为什么需要它
在 Python 中，“想要快速查找”的第一个答案几乎总是 dict。但对于“过去 10 分钟有多少条？”“分数前 20 名”“订单 ID 从 1000 号到 2000 号”这样的问题，dict 回答不了。因为哈希是放弃顺序、换取便宜的单条查找的结构。bisect 文档也说了同样的话——二分查找适合用来查找值的区间，而要查找某个特定的值，字典更好。
反过来，如果因为需要顺序而选了树，但输入是已经排好序送进来的，不做平衡的树就只会向一侧生长，实际上变成链表。自增 ID、按时间顺序的事件等等，服务的输入比想象中更常是有序的。选择结构时，除了“问的是什么”，还要看“输入以什么顺序到来”。
工作原理
哈希表与装载因子。 线性探测从键的首选槽位 h(key) 开始，一个槽位一个槽位地查看 h+1、h+2……直到遇到空槽位或该键。已占用的比例 α（装载因子）上升后，连续被占用的槽位组成的“簇”就会变长，落进簇里的键必须一路走到簇的末尾。Linear probing 词条把这种现象称为一次聚集（primary clustering），并指出首个假设哈希函数随机的理论分析出自 Knuth（1963）。Sedgewick 与 Wayne 所著《Algorithms》第 3.4 节的 Proposition M，在均匀哈希假设下给出的平均探测数是：查找成功约 ½(1 + 1/(1−α))，查找失败和插入约 ½(1 + 1/(1−α)²)。
| α | 查找成功（理论） | 查找失败（理论） |
|---|---|---|
| 0.5 | 1.5 | 2.5 |
| 0.75 | 2.5 | 8.5 |
| 0.9 | 5.5 | 50.5 |
成功一侧增长平缓，而失败一侧按平方飙升。因为不存在的键必须穿过整个簇，直到遇到空槽位。决定何时扩大表（resize）的装载因子，依据就是这张表。实验中，首个槽位、找到的槽位、最后一个空槽位都各计 1 次，按与这个公式相同的定义来测量。
二叉搜索树的高度。 查找开销与高度成正比。本实验把高度按从根到叶子最长路径上的节点数来计（只有一个节点时为 1）。用 n 个键能构造出的最低高度是 ceil(log2(n+1))，按排好的顺序插入时则是 n。如果用递归深入这么深，就会撞上 sys.setrecursionlimit 文档所说的解释器栈限制。与其提高限制，不如写成循环更安全。
堆与 top-k。 heapq 用一个数组构造最小堆。不变式是 heap[k] <= heap[2k+1]、heap[k] <= heap[2k+2]，最小的值始终是 heap[0]。选取前 k 名时，用的不是最大堆，而是大小为 k 的最小堆，原因就在这里。根是目前为止前 k 名中最弱的项，也就是门槛，所以新项只需与根比较一次，大多数都会被丢弃。只有超过门槛时，才用 heapreplace 替换根。文档补充说，nlargest 和 nsmallest 在 n 较小时最好，n 较大时 sorted() 更高效。另外，堆不会保证优先级相同的项的顺序。文档中的优先队列示例把到达的序号作为第二个键，来区分并列项。本实验用 (分数, −id) 作为键，并列时留下 id 较小的一方。
有序数组与 bisect。 bisect_left 返回的位置 ip，把数组切成左侧全部小于 x、右侧全部大于等于 x。所以 [lo, hi) 的个数是 bisect_left(a, hi) − bisect_left(a, lo)。当边界上堆着相同的值时，如果混用 bisect_right，就会把 hi 包含进来，或者漏掉 lo。查找是 O(log n)，但按文档所说，insort 因为有插入这一步，是 O(n)。如果新值总是追加到末尾（时间戳、自增 ID），只靠 append 就能保持有序，这个弱点就消失了。
在现场相遇的样子
把排行榜做成 Redis 的 Sorted Set 的方法与过期策略，由“Redis 与缓存”课程讲；数据库用平衡树（B+ 树）索引同时解决单条查找与区间查询的内容，由“数据库概念”课程讲；优化器是否真的使用了这个索引，要用执行计划来确认，这件事由“SQL 实战”课程讲。本模块是要亲手做出垫在这些之下的结构，用数字确认：在装载因子 0.9 时，查找一个不存在的键要走多少个槽位；有序输入会把树变成几层。
下一项实验要做什么
用规定好的哈希规则求出首选槽位，构建线性探测表，把装载因子 0.5、0.75、0.9 下的平均探测数与理论值并排写出。把同样的键按打乱的顺序和有序的顺序分别插入树中，比较高度；亲手做出最小堆，使 pop 顺序与 heapq 一致；再用大小为 k 的堆求出流中的前 k 名，用 bisect 统计区间个数。最后针对四种工作负载选出结构，并附上你测得的数字作为依据。