3.1 Symbol Tables：关联数组、顺序查找与有序数组二分

3.1 · Symbol Tables覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“3.1 · Symbol Tables”如何用键值 API、顺序查找和有序数组二分建立符号表的语义与成本基线
  • 能逐项核对 符号表、符号表API、有序符号表、顺序查找、有序数组二分查找，并区分作者站内容与本页独立补充
  • 能按“有序数组查询 O(log N)，插入最坏 O(N)；无序链表查询和插入最坏 O(N)”手算一个最小输入，逐步检查“每个键至多关联一个当前值，put 已有键只更新值而不增加 size”
  • 能注入“用 null 同时表示缺失和值，或二分 rank 的返回语义与插入位置语义混淆”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“3·1 · Symbol Tables”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“3·1 · Symbol Tables”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“3·1 · Symbol Tables”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：3.1 · Symbol Tables

  • 1. 符号表：在本页通过“解析键值操作”连接解释、交互状态和练习验收。
  • 2. 符号表API：在本页通过“查找已有键”连接解释、交互状态和练习验收。
  • 3. 有序符号表：在本页通过“决定更新或插入”连接解释、交互状态和练习验收。
  • 4. 顺序查找：在本页通过“维护有序表示”连接解释、交互状态和练习验收。
  • 5. 有序数组二分查找：在本页通过“核对 size 与返回值”连接解释、交互状态和练习验收。

从“同一个单词第二次出现”开始

符号表（symbol tables）回答“这个key当前关联什么value”。Frequency counter读到单词 the 时，不是新增第二个 the node，而是取得旧count并写回加1；同一key始终只对应一个current value。

先预测 put("S", 0) 后再 put("S", 3)，size会不会从1变2。不会，第二次put覆盖旧association，size保持1。若实现每次都插新node，get会依赖遍历顺序，keys会重复，已不满足associative-array contract。

官方3.1按 Symbol table、API、Ordered symbol tables、Sample clients、Sequential search in an unordered linked list、Binary search in an ordered array 展开。它用两个最简单representation揭示核心权衡：无序链表更新结构便宜但search线性；有序数组search logarithmic却为新key搬移linear items。

3.1.1 Symbol table API：association的精确定义

符号表API（symbol table API）把key type与value type参数化：

void put(Key key, Value val)
Value get(Key key)
void delete(Key key)
boolean contains(Key key)
boolean isEmpty()
int size()
Iterable<Key> keys()

官方约定禁止null key；null value也不能成为合法association，因为 get(key)==null 表示absent，put(key,null) 等价于delete。这样contains可由get实现，但也意味着不能区分“key不存在”和“key存在且value为null”。不同Map API可能允许null，client不能跨contract想当然。

删除可lazy或eager。Lazy deletion保留key并标null，之后再清理；eager deletion立即移除pair。由于本API把null定义为absence，任何keys/size都必须排除deleted keys。重复delete不存在key应保持idempotent，不改变size。

Key equality必须是equivalence relation：reflexive、symmetric、transitive、consistent，且 x.equals(null) 为false。Key最好immutable；若插入后影响equals的fields改变，已有node可能再也无法由逻辑相同query找到。

3.1.2 Ordered symbol tables：order扩展了问题空间

有序符号表（ordered symbol tables）在basic API上增加：

  • min / max：最小与最大key；
  • floor(k)：不大于k的最大key，ceiling(k)：不小于k的最小key；
  • rank(k)：严格小于k的keys数量，select(r)：rank r的key；
  • keys(lo,hi) 与 size(lo,hi)：inclusive range；
  • deleteMin / deleteMax。

Rank（rank）连接几乎所有operations。若query在table中，select(rank(query)) 返回同key；若不在，rank是插入点，ceiling在该index，floor在前一index。Boundary不存在时，官方key-returning methods抛exception，而不是返回一个伪key。

Range size可由rank组成。对inclusive [lo,hi]：

size(lo,hi)=rank(hi)−rank(lo)+{1,hi present0,hi absentsize(lo,hi)=rank(hi)-rank(lo)+ \begin{cases} 1,& hi\text{ present}\\ 0,& hi\text{ absent} \end{cases}

Comparable key type最好让 compareTo()==0 与 equals() 一致。Sequential linked list按equals识别duplicate，ordered implementations按compareTo为0识别duplicate；若两者不一致，换representation会改变table semantics。

3.1.3 Sample client：FrequencyCounter只依赖API

FrequencyCounter过滤短于minimum length的words，用symbol table累计count，再遍历keys找最大frequency。Client不应依赖linked-list order或sorted-array order：

while (!StdIn.isEmpty()) {
    String word = StdIn.readString();
    if (word.length() < minlen) continue;
 
    if (st.contains(word)) st.put(word, st.get(word) + 1);
    else                   st.put(word, 1);
}
 
String max = "";
st.put(max, 0);
for (String word : st.keys())
    if (st.get(word) > st.get(max)) max = word;

这段client把filter、count与argmax职责分开。Performance取决于get/put sequence，而不只N words：contains 后再 get 可能做两次search；提供getOrDefault或一次get缓存可减少lookup，但必须保留null convention。Tie时返回哪个max取决于iteration order，若需要deterministic lexicographic tie-break应明确编码。

3.1.4 Sequential search：无序链表逐项比较

顺序查找（sequential search）在每个Node存key、value、next。Get linear scan；put先scan，命中就update value，miss才在head插新node。

public Value get(Key key) {
    if (key == null) throw new IllegalArgumentException();
    for (Node x = first; x != null; x = x.next)
        if (key.equals(x.key)) return x.val;
    return null;
}
 
public void put(Key key, Value val) {
    if (key == null) throw new IllegalArgumentException();
    if (val == null) { delete(key); return; }
    for (Node x = first; x != null; x = x.next)
        if (key.equals(x.key)) { x.val = val; return; }
    first = new Node(key, val, first);
    n++;
}

Miss、新key insert与tail hit都需要N compares；successful search worst case也是N。向empty table依次插入N个distinct keys时，第k次先扫描k个old nodes：

0+1+⋯+(N−1)=N(N−1)2∼N220+1+\cdots+(N-1)=\frac{N(N-1)}{2}\sim\frac{N^2}{2}

Head insertion本身constant，但“确认key不存在”不是。Current official recursive delete代码简洁，却明确警告large table可能call stack过深；iterative predecessor deletion更稳健。删除head、middle、tail、missing与single node都应独立测试并核对n。

3.1.5 Binary search in an ordered array：rank是核心

有序数组二分查找（binary search in an ordered array）维护两条parallel arrays：keys[0..n) strictly ordered，vals[i] 与 keys[i] 的association必须同index。

public int rank(Key key) {
    int lo = 0;
    int hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(keys[mid]);
        if      (cmp < 0) hi = mid - 1;
        else if (cmp > 0) lo = mid + 1;
        else              return mid;
    }
    return lo;
}

Loop invariant是：所有index小于lo的keys严格小于query，所有index大于hi的keys严格大于query；若exact key存在，它在candidate interval。Miss时interval empty，lo恰是lower bound。Worst-case comparisons：

Crank(N)≤⌊lg⁡N⌋+1C_{\mathrm{rank}}(N)\le\lfloor\lg N\rfloor+1

Get先rank，再检查 i<n && keys[i].compareTo(key)==0。漏掉 i<n 会在query大于max时越界；只读 keys[i] 不验证equality，会把ceiling value误当exact hit。

3.1.6 Ordered put/delete：search快，搬移仍线性

Put先rank。Exact hit只update vals[i]；new key需要capacity，随后从back向front同步右移keys与vals，最后写入pair：

int i = rank(key);
if (i < n && keys[i].compareTo(key) == 0) {
    vals[i] = val;
    return;
}
if (n == keys.length) resize(2 * keys.length);
for (int j = n; j > i; j--) {
    keys[j] = keys[j - 1];
    vals[j] = vals[j - 1];
}
keys[i] = key;
vals[i] = val;
n++;

正向右移会用 keys[i] 覆盖 keys[i+1]，随后复制的已是重复值；必须back-to-front。Delete反向左移、n减1、把old tail的key/value设null避免loitering，并在quarter-full时halve。

New key插入worst case约移动N pairs，每pair读写key/value，官方给出约2N array accesses的数量级：

Anew put(N)∼2N,Abuild(N)=Θ(N2)A_{\mathrm{new\ put}}(N)\sim 2N, \qquad A_{\mathrm{build}}(N)=\Theta(N^2)

因此BinarySearchST适合read-heavy、update-light ordered data。它让get、contains、rank、floor、ceiling logarithmic，min/max/select constant；new put/delete仍linear。下一节BST尝试让ordered search与update都由tree path承担。

统一验收：从association到rank/select逆关系

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“3.1 · Symbol Tables”的两个最小情境间切换，再逐项选择正式概念。预测“有序数组查询 O(log N)，插入最坏 O(N)；无序链表查询和插入最坏 O(N)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

3.1 · Symbol Tables：对象、操作与不变量

用键值 API、顺序查找和有序数组二分建立符号表的语义与成本基线

选择最小情境

切换正式概念

输入合同操作证书algs4-3.1 · 先给前提，再执行，再验收当前概念：1/6
更新已有键
put(A,1) 后再 put(A,2)
当前观察
symbol tables：size 保持 1，get(A) 返回 2
有序数组查询 O(log N)，插入最坏 O(N)；无序链表查询和插入最坏 O(N)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 符号表：在实验 1 中指出对应状态，并写出一个通过条件。
  • 符号表API：在实验 2 中指出对应状态，并写出一个通过条件。
  • 有序符号表：在实验 3 中指出对应状态，并写出一个通过条件。
  • 顺序查找：在实验 1 中指出对应状态，并写出一个通过条件。
  • 有序数组二分查找：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“有序数组查询 O(log N)，插入最坏 O(N)；无序链表查询和插入最坏 O(N)”不是孤立结论？

问题 3：故障恢复。 怎样证明“用 null 同时表示缺失和值，或二分 rank 的返回语义与插入位置语义混淆”已经修复？

本章回顾

  1. Symbol table把unique key关联到一个current value，duplicate put覆盖而不增加size。
  2. 官方API禁止null values，用get-null表示absent，并让put-null等价delete。
  3. Ordered ST以Comparable扩展min/max、floor/ceiling、rank/select和range operations。
  4. SequentialSearchST用unordered linked list，search与new-key confirmation worst-case linear。
  5. BinarySearchST用sorted parallel arrays，rank在log N内给出exact位置或插入点。
  6. Ordered array get快，但new put/delete要同步移动pairs，worst-case linear。
  7. Representation验收既要检查structure invariant，也要与association-level reference oracle比较。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…