一、核心思路

用两个平行数组存储所有键值对：

下标:    0    1    2    3    4    5    6    7    8    9
keys[]:  A    C    E    H    L    M    P    R    S    X
vals[]:  8    4   12    5   11    9   10    3    0    7

键数组始终保持有序，值数组与键数组下标一一对应。
核心操作是 rank(key)——返回小于 key 的键的个数，也就是 key 在有序数组中应处的位置。
所有其他操作都建立在 rank() 之上。

二、插入过程完整追踪

输入：S E A R C H E X A M P L E

操作        keys[]（有序）                           N   说明
--------   ---------------------------------------  --  ----------------------
put(S,0)   S                                         1  直接插入
put(E,1)   E  S                                      2  E < S，插在前面
put(A,2)   A  E  S                                   3  A 最小，插在最前
put(R,3)   A  E  R  S                                4  R 在 E 和 S 之间
put(C,4)   A  C  E  R  S                             5  C 在 A 和 E 之间
put(H,5)   A  C  E  H  R  S                          6  H 在 E 和 R 之间
put(E,6)   A  C  E  H  R  S                          6  E 已存在，只更新值
put(X,7)   A  C  E  H  R  S  X                       7  X 最大，插在末尾
put(A,8)   A  C  E  H  R  S  X                       7  A 已存在，只更新值
put(M,9)   A  C  E  H  M  R  S  X                    8  M 在 H 和 R 之间
put(P,10)  A  C  E  H  M  P  R  S  X                 9  P 在 M 和 R 之间
put(L,11)  A  C  E  H  L  M  P  R  S  X             10  L 在 H 和 M 之间
put(E,12)  A  C  E  H  L  M  P  R  S  X             10  E 已存在，只更新值

插入新键时，比 key 大的所有键整体右移一格腾出位置：

插入 M(9) 之前:  A  C  E  H  _  R  S  X
                              ^
                          rank(M)=4，此处插入
右移 R S X:      A  C  E  H  _  R  S  X  ->  A  C  E  H  _  R  S  X
插入后:          A  C  E  H  M  R  S  X

三、rank() 的两种实现

3.1 递归版（更直观）

查找区间 [lo, hi]，取中间位置 mid：
  key < keys[mid]  ->  去左半段 [lo, mid-1]
  key > keys[mid]  ->  去右半段 [mid+1, hi]
  key == keys[mid] ->  找到，返回 mid
  lo > hi          ->  未找到，返回 lo（应插入位置）

3.2 迭代版（实际使用）

用 lo、hi 两个指针不断缩小搜索范围：

查找 P，数组: A C E H L M P R S X（下标 0~9）
lo  hi  mid  keys[mid]  比较结果     动作
--  --  ---  ---------  ----------  --------
 0   9    4      L       P > L       lo = 5
 5   9    7      R       P < R       hi = 6
 5   6    5      M       P > M       lo = 6
 6   6    6      P       P == P      返回 6
查找 Q（不在表中），数组同上
lo  hi  mid  keys[mid]  比较结果     动作
--  --  ---  ---------  ----------  --------
 0   9    4      L       Q > L       lo = 5
 5   9    7      R       Q < R       hi = 6
 5   6    5      M       Q > M       lo = 6
 6   6    6      P       Q > P       lo = 7
lo(7) > hi(6)，退出循环，返回 lo = 7
（Q 应插在下标 7，即 R 的位置之前）

四、C++ 完整实现

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>
#include <algorithm>   // std::copy_backward
// ---------------------------------------------------------------------------
// 基于有序数组 + 二分查找的符号表
// Key   : 键类型，必须支持 operator< 和 operator==（可比较）
// Value : 值类型
// ---------------------------------------------------------------------------
template <typename Key, typename Value>
class BinarySearchST {
private:
    std::vector<Key>   keys_;   // 有序键数组
    std::vector<Value> vals_;   // 与键平行的值数组
    int n_;                     // 当前键值对数量
public:
    // 构造：预留初始容量（可动态扩容）
    explicit BinarySearchST(int capacity = 16)
        : n_(0)
    {
        keys_.reserve(capacity);
        vals_.reserve(capacity);
    }
    // 键值对数量
    int size() const { return n_; }
    // 是否为空
    bool isEmpty() const { return n_ == 0; }
    // -----------------------------------------------------------------------
    // rank(key): 二分查找，返回小于 key 的键的个数
    //
    // 两个不变量（循环过程中始终成立）：
    //   keys_[0..lo-1]  全部 < key
    //   keys_[hi+1..n_-1] 全部 >= key
    // 循环结束时 lo == hi+1，lo 就是答案
    // -----------------------------------------------------------------------
    int rank(const Key& key) const {
        int lo = 0, hi = n_ - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;   // 防止整数溢出，不用 (lo+hi)/2
            if (key < keys_[mid]) {
                hi = mid - 1;   // key 在左半段
            } else if (keys_[mid] < key) {
                lo = mid + 1;   // key 在右半段
            } else {
                return mid;     // 找到：返回下标（也等于小于它的键的个数）
            }
        }
        return lo;  // 未找到：lo 就是 key 应该插入的位置
    }
    // -----------------------------------------------------------------------
    // get(key): 查找键对应的值
    // 先用 rank() 定位，再确认该位置的键是否真的等于 key
    // 时间复杂度：O(log N)
    // -----------------------------------------------------------------------
    Value get(const Key& key) const {
        if (isEmpty()) throw std::runtime_error("表为空");
        int i = rank(key);
        // i < n_ 且 keys_[i] == key，才是真正找到
        if (i < n_ && !(keys_[i] < key) && !(key < keys_[i])) {
            return vals_[i];
        }
        throw std::runtime_error("key not found");
    }
    // 是否包含该键
    bool contains(const Key& key) const {
        int i = rank(key);
        return i < n_ && !(keys_[i] < key) && !(key < keys_[i]);
    }
    // -----------------------------------------------------------------------
    // put(key, val): 插入或更新
    // 1. 用 rank() 找到应插入位置 i
    // 2. 若 keys_[i] == key，直接更新 vals_[i]
    // 3. 否则，将 i 之后所有元素右移一格，插入新键值对
    // 时间复杂度：查找 O(log N)，但移动元素 O(N)，总体 O(N)
    // -----------------------------------------------------------------------
    void put(const Key& key, const Value& val) {
        int i = rank(key);
        // 命中：更新值
        if (i < n_ && !(keys_[i] < key) && !(key < keys_[i])) {
            vals_[i] = val;
            return;
        }
        // 未命中：在位置 i 插入新元素
        // 先给数组扩容一格
        keys_.push_back(Key{});
        vals_.push_back(Value{});
        // 将 [i, n_-1] 的元素整体右移一格（从后往前移，避免覆盖）
        for (int j = n_; j > i; --j) {
            keys_[j] = keys_[j - 1];
            vals_[j] = vals_[j - 1];
        }
        // 插入新键值对
        keys_[i] = key;
        vals_[i] = val;
        ++n_;
    }
    // -----------------------------------------------------------------------
    // del(key): 删除指定键
    // 找到位置后，将后续元素左移一格
    // 时间复杂度：O(N)
    // -----------------------------------------------------------------------
    void del(const Key& key) {
        if (!contains(key)) return;
        int i = rank(key);
        // 将 [i+1, n_-1] 的元素整体左移一格
        for (int j = i; j < n_ - 1; ++j) {
            keys_[j] = keys_[j + 1];
            vals_[j] = vals_[j + 1];
        }
        keys_.pop_back();
        vals_.pop_back();
        --n_;
    }
    // -----------------------------------------------------------------------
    // 有序操作：直接利用数组有序的性质
    // -----------------------------------------------------------------------
    // 最小键：数组第一个元素
    Key min() const {
        if (isEmpty()) throw std::runtime_error("表为空");
        return keys_[0];
    }
    // 最大键：数组最后一个元素
    Key max() const {
        if (isEmpty()) throw std::runtime_error("表为空");
        return keys_[n_ - 1];
    }
    // select(k): 排名为 k 的键（第 k+1 小），直接下标访问，O(1)
    Key select(int k) const {
        if (k < 0 || k >= n_) throw std::out_of_range("k 超出范围");
        return keys_[k];
    }
    // ceiling(key): 大于等于 key 的最小键
    // rank() 返回第一个 >= key 的位置
    Key ceiling(const Key& key) const {
        int i = rank(key);
        if (i >= n_) throw std::runtime_error("ceiling 不存在");
        return keys_[i];
    }
    // floor(key): 小于等于 key 的最大键
    Key floor(const Key& key) const {
        int i = rank(key);
        // 若 keys_[i] == key，直接返回
        if (i < n_ && !(keys_[i] < key) && !(key < keys_[i])) {
            return keys_[i];
        }
        // 否则返回 i-1 位置（严格小于 key 的最大键）
        if (i == 0) throw std::runtime_error("floor 不存在");
        return keys_[i - 1];
    }
    // 区间键数：[lo, hi] 内有多少个键
    int sizeRange(const Key& lo, const Key& hi) const {
        if (hi < lo) return 0;
        if (contains(hi)) return rank(hi) - rank(lo) + 1;
        else              return rank(hi) - rank(lo);
    }
    // 区间遍历：按顺序返回 [lo, hi] 内所有键
    std::vector<Key> keys(const Key& lo, const Key& hi) const {
        std::vector<Key> result;
        for (int i = rank(lo); i < rank(hi); ++i) {
            result.push_back(keys_[i]);
        }
        if (contains(hi)) result.push_back(keys_[rank(hi)]);
        return result;
    }
    // 返回全部键（天然有序）
    std::vector<Key> keys() const {
        return std::vector<Key>(keys_.begin(), keys_.begin() + n_);
    }
};
// ---------------------------------------------------------------------------
// 主程序：复现文档中的测试客户端
// ---------------------------------------------------------------------------
int main() {
    BinarySearchST<std::string, int> st;
    std::string line = "S E A R C H E X A M P L E";
    std::istringstream iss(line);
    std::string key;
    int i = 0;
    while (iss >> key) {
        st.put(key, i);
        ++i;
    }
    // 打印全部键值对（有序）
    std::cout << "有序符号表内容:" << std::endl;
    for (const auto& k : st.keys()) {
        std::cout << k << "  " << st.get(k) << std::endl;
    }
    // 验证各有序操作
    std::cout << "\nmin()         = " << st.min()           << std::endl; // A
    std::cout << "max()         = " << st.max()             << std::endl; // X
    std::cout << "select(6)     = " << st.select(6)         << std::endl; // P
    std::cout << "rank(M)       = " << st.rank("M")         << std::endl; // 5
    std::cout << "floor(N)      = " << st.floor("N")        << std::endl; // M
    std::cout << "ceiling(N)    = " << st.ceiling("N")      << std::endl; // P
    std::cout << "size(E,R)     = " << st.sizeRange("E","R")<< std::endl; // 5
    std::cout << "\nkeys(E, R): ";
    for (const auto& k : st.keys("E", "R")) std::cout << k << " ";
    std::cout << std::endl;  // E H L M P R
    return 0;
}

五、性能分析

命题 B：二分查找的比较次数上界

设表中有 $N$ 个键，令 $C(N)$ 为查找所需的最多比较次数，则有递推关系：
$$C(N)\le C\left(\lfloor N/2\rfloor \right)+1$$
每次比较后，搜索范围缩小一半，再加 1 次比较判断方向。
解这个递推式（以 $N=2^n-1$ 为例展开）：
$$C(2^n-1)\le C(2^{n-1}-1)+1\le C(2^{n-2}-1)+2\le \cdots \le C(0)+n=n$$
因此对一般的 $N$：
$$C(N)\le \lfloor \lg N\rfloor +1$$
即无论查找成功还是失败，比较次数不超过 $\lfloor \lg N\rfloor +1$。

各操作复杂度汇总

---

操作	时间复杂度	原因
get()	$O(\log N)$	二分查找
put()	$O(N)$	查找 $O(\log N)$，但移动元素 $O(N)$
del()	$O(N)$	同上
contains()	$O(\log N)$	二分查找
min() / max()	$O(1)$	直接取数组首尾
select(k)	$O(1)$	直接下标访问
rank()	$O(\log N)$	二分查找
floor() / ceiling()	$O(\log N)$	基于 rank()
sizeRange()	$O(\log N)$	两次 rank()
deleteMin()	$O(N)$	左移所有元素
deleteMax()	$O(1)$	直接删末尾

---

put() 的瓶颈：插入 N 个键的总代价

每次插入新键，最坏情况需要移动当前所有键（比如始终插在最前面）：
$$\text{第 }k\text{ 次插入移动次数}\le k-1$$
$$\text{总数组访问次数}\le 0+1+2+\cdots +(N-1)=\frac{N(N-1)}{2}\approx \frac{N^2}{2}$$
这与顺序查找链表的插入代价同阶，都是二次方级别。

六、与链表顺序查找的对比

                  顺序查找（链表）        二分查找（有序数组）
数据结构          无序单链表              有序平行数组
get（查找）       O(N)                   O(log N)  <- 大幅改进
put（插入）       O(N)                   O(N)      <- 同样慢
有序操作支持      不支持                 支持（floor/ceiling/rank/select）
内存布局          离散（指针跳跃）        连续（缓存友好）

二分查找的 get() 从 $O(N)$ 降到 $O(\log N)$，但 put() 仍是 $O(N)$，原因不同：

链表 put() 慢的原因:  要扫描全表确认键不重复（O(N) 次比较）
数组 put() 慢的原因:  查找位置只需 O(log N)，但插入后要整体右移（O(N) 次数组访问）

七、实际性能数据

文档给出对 tale.txt（最小词长 8）运行 FrequencyCounter 的结果：

实现                  每次 put() 平均比较次数
------------------   ----------------------
SequentialSearchST        2,246   次
BinarySearchST              484   次

改进约 $4.6$ 倍，但 put() 的数组移动代价没有统计在内，大输入下仍然力不从心：

输入             不同词数 N       put() 总数组访问次数（估算）
----------      ----------      --------------------------
tale.txt            5,737         ~ 5737^2 / 2 ≈ 1.6 x 10^7   (勉强可用)
leipzig1M.txt     299,593         ~ 299593^2 / 2 ≈ 4.5 x 10^10 (不可用)

$$\frac{299593^2}{2}\approx 4.5\times 10^{10}$$

八、为什么需要更好的结构

九、六种符号表实现总览

---

实现	底层结构	查找（最坏）	插入（最坏）	有序操作	适用场景
SequentialSearchST	无序链表	$N$	$N$	不支持	极小的表
BinarySearchST	有序数组	$\log N$	$N$	支持	静态表或查多插少
BST	二叉搜索树	$N$（退化）	$N$	支持	一般场景
RedBlackBST	红黑树	$\log N$	$\log N$	支持	通用最优
SeparateChainingHashST	链式哈希	$N/M$（均摊）	$N/M$	不支持	纯查找，无需有序
LinearProbingHashST	开放寻址哈希	$N/M$（均摊）	$N/M$	不支持	同上，缓存更友好

---

核心结论：我们需要对查找和插入都能达到 $O(\log N)$ 的实现，答案是二叉搜索树和哈希表，这也是后续章节的主题。

符号表：问答与习题解析

一、问答精讲

Q1：为什么键和值要分开，而不是用一个同时含键的 Item 类型？

背景：优先队列里我们用一个实现了 Comparable 的对象同时表示"键"和"数据"。为什么符号表不这样做？
解答：两种方式都合理，区别在于抽象层次：

方式一（优先队列风格）：Item 对象同时包含键和数据
  优点：代码简洁
  缺点：查询时必须构造一个完整 Item，而你往往只有"键"
方式二（符号表风格）：键和值严格分离
  优点：查询接口只需要键 get(key)，更自然
  体现了"关联数组"的抽象——通过键找值

C++ 的 std::map<Key, Value> 正是采用方式二，查找时只传键：m.find(key)。

Q2：为什么有序符号表要用 compareTo()，不直接全程用 equals()？

解答：不是所有键都能比较大小，但几乎所有键都能判断相等。

能判等但不能比大小的例子：
  图片（两张图是否相同 -> 可以判断）
  （哪张图"更大" -> 没有意义）
  音频文件、任意二进制数据，同理
结论：
  基本符号表只需要 == (equals)，适用范围更广
  有序符号表额外要求 <  (compareTo)，换来排序能力

C++ 对应：

• 无序符号表用 std::unordered_map，键只需实现 == 和哈希函数
• 有序符号表用 std::map，键只需实现 <（std::less）

Q3：为什么不允许键为空（null）？

解答：在 Java 中，null.compareTo(x) 或 null.equals(x) 会直接抛出空指针异常。禁止空键让客户端代码更简单——不用到处写 if (key != null) 的防御性判断。
C++ 中没有 null 引用的问题，但指针版本同理：若键是指针类型，空指针解引用会崩溃。通常用引用而非指针传递键，从语言层面规避这个问题：

// 用 const Key& 而不是 Key*，杜绝空指针
void put(const Key& key, const Value& val);
Value get(const Key& key) const;

Q4：为什么 BinarySearchST 中键数组要声明为 Comparable[] 而非 Object[]？

这是 Java 泛型与数组的类型擦除问题，C++ 模板不存在此问题。
C++ 中模板参数在编译期就完全确定类型，不存在运行时类型擦除：

// C++ 模板：Key 类型在编译期确定，完全类型安全
template <typename Key, typename Value>
class BinarySearchST {
    std::vector<Key>   keys;   // 直接就是 Key 类型，无需任何转换
    std::vector<Value> vals;
};

Q5：一个键对应多个值怎么处理？

解答：两种方案：

方案一：细化键，让键本身包含区分信息
  例：火车到站时间+站台号 作为联合键，保证唯一性
方案二：值改为容器类型
  例：map<Date, vector<Train>> 让同一日期对应多趟列车

C++ 标准库提供了 std::multimap，天然支持一键多值：

#include <map>
#include <string>
#include <iostream>
int main() {
    // multimap 允许重复键
    std::multimap<std::string, int> mm;
    mm.insert({"apple", 1});
    mm.insert({"apple", 2});  // 同一键，不覆盖
    mm.insert({"banana", 3});
    // 查找 apple 对应的所有值
    auto range = mm.equal_range("apple");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->first << " -> " << it->second << std::endl;
    }
    // 输出:
    // apple -> 1
    // apple -> 2
    return 0;
}

Q6：为什么"预排序后再查找"只作为习题，而不作为正式实现？

解答：这是一个经典的性能陷阱警告。

表面上看：
  预排序后二分查找很快，O(log N) 查找
  是个好主意
实际问题：
  插入变慢了（需要维护有序性，最坏 O(N) 移位）
  若客户端频繁交替 put() 和 get()
  总体性能反而是二次方级别
更大的问题：
  接口太宽 = 给客户端挖坑
  "方便"的方法如果性能很差，但接口上看不出来
  客户端在大规模场景下踩坑才发现，为时已晚

Java 的 ArrayList 是典型反面例子：contains() 是 $O(N)$ 的，但接口上和 HashSet.contains() 看起来一模一样。
设计原则：接口中每个方法都应该有高效实现，或者明确标注性能特征。

二、习题精选解答

习题 3.1.1：成绩换算 GPA 计算

题意：建立字母成绩到分数的符号表，读入若干字母成绩，计算平均分（GPA）。

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <stdexcept>
int main() {
    // 建立成绩映射表
    // 键：字母成绩，值：对应分数
    std::map<std::string, double> gradeTable = {
        {"A+", 4.33}, {"A",  4.00}, {"A-", 3.67},
        {"B+", 3.33}, {"B",  3.00}, {"B-", 2.67},
        {"C+", 2.33}, {"C",  2.00}, {"C-", 1.67},
        {"D",  1.00}, {"F",  0.00}
    };
    // 模拟输入：一行字母成绩，空格分隔
    std::string line = "A B+ A- C+ B F A";
    std::istringstream iss(line);
    std::string grade;
    double total = 0.0;
    int count = 0;
    while (iss >> grade) {
        // 查找该成绩对应的分数
        auto it = gradeTable.find(grade);
        if (it == gradeTable.end()) {
            throw std::runtime_error("未知成绩: " + grade);
        }
        total += it->second;
        ++count;
    }
    if (count == 0) {
        std::cout << "没有输入成绩" << std::endl;
        return 0;
    }
    double gpa = total / count;
    std::cout << "GPA = " << gpa << std::endl;
    // 输入 A B+ A- C+ B F A 的 GPA:
    // (4.00 + 3.33 + 3.67 + 2.33 + 3.00 + 0.00 + 4.00) / 7 ≈ 2.90
    return 0;
}

https://godbolt.org/z/vPK1cbd7Y

习题 3.1.2：基于无序数组的符号表 ArrayST

#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
#include <sstream>
// 基于无序数组的符号表
// 键和值分别存在两个平行数组中
// 同一下标 i 对应一对键值
template <typename Key, typename Value>
class ArrayST {
private:
    std::vector<Key>   keys_;   // 键数组
    std::vector<Value> vals_;   // 值数组（keys_[i] 对应 vals_[i]）
    // 查找键的下标，找不到返回 -1
    int indexOf(const Key& key) const {
        for (int i = 0; i < static_cast<int>(keys_.size()); ++i) {
            if (keys_[i] == key) return i;
        }
        return -1;
    }
public:
    // 插入或更新
    // 若键已存在：更新对应值
    // 若键不存在：追加到数组末尾
    void put(const Key& key, const Value& val) {
        int i = indexOf(key);
        if (i != -1) {
            vals_[i] = val;   // 键已存在，更新值
        } else {
            keys_.push_back(key);   // 新键追加
            vals_.push_back(val);
        }
    }
    // 查找键对应的值，找不到抛出异常
    Value get(const Key& key) const {
        int i = indexOf(key);
        if (i == -1) throw std::runtime_error("key not found");
        return vals_[i];
    }
    // 删除指定键（用末尾元素填补空缺，避免移位）
    void del(const Key& key) {
        int i = indexOf(key);
        if (i == -1) return;
        // 用最后一个元素覆盖被删除的位置
        keys_[i] = keys_.back();
        vals_[i] = vals_.back();
        keys_.pop_back();
        vals_.pop_back();
    }
    bool contains(const Key& key) const { return indexOf(key) != -1; }
    bool isEmpty() const { return keys_.empty(); }
    int  size()    const { return static_cast<int>(keys_.size()); }
    // 返回所有键（顺序不定）
    std::vector<Key> keys() const { return keys_; }
};
// 测试
int main() {
    ArrayST<std::string, int> st;
    std::string line = "S E A R C H E X A M P L E";
    std::istringstream iss(line);
    std::string key;
    int i = 0;
    while (iss >> key) { st.put(key, i++); }
    std::cout << "ArrayST 内容:" << std::endl;
    for (const auto& k : st.keys()) {
        std::cout << k << "  " << st.get(k) << std::endl;
    }
    st.del("C");
    std::cout << "删除 C 后 contains(C): "
              << (st.contains("C") ? "true" : "false") << std::endl;
    return 0;
}

https://godbolt.org/z/17xcezE6z

习题 3.1.5：为 SequentialSearchST 实现 size()、delete()、keys()

这三个方法在上一章的完整实现中已经给出，核心思路：

size()   : 维护一个计数器 n，put 新键时 +1，delete 时 -1
delete() : 找到目标节点的前驱，让前驱的 next 跳过目标节点
keys()   : 遍历链表，把每个节点的键收集到 vector 返回

删除的 ASCII 示意：

删除前：
  prev -> [C|4] -> [R|3] -> ...
删除 C 的步骤：
  1. 找到 C 的前驱节点 prev
  2. prev->next = C节点->next  (即 [R|3])
  3. delete C节点
删除后：
  prev -> [R|3] -> ...

习题 3.1.6：FrequencyCounter 的 put() 和 get() 调用次数

设输入中共有 $W$ 个词，其中不同词 $D$ 个。
每读入一个词，FrequencyCounter 的逻辑是：

st[word]++;  // 等价于: 若不存在则 put(word,1)，否则 put(word, get(word)+1)

分析每次操作：

• 若该词首次出现：执行 1 次 get（查找，miss）+ 1 次 put（插入）
• 若该词已经存在：执行 1 次 get（查找，hit）+ 1 次 put（更新）
  因此：
  $$\text{put() 调用次数}=W$$
  $$\text{get() 调用次数}=W$$
  最后找最大频次时，还需遍历所有键各调用一次 get()：
  $$\text{最终遍历的 get() 次数}=D$$
  合计：
  $$\text{总 put()}=W,\text{总 get()}=W+D$$

习题 3.1.10：插入 E A S Y Q U E S T I O N 的顺序追踪

输入序列：E A S Y Q U E S T I O N，共 12 个字符，其中 E、S 各出现两次。

步骤   操作        比较次数   链表（头在左）
----  ---------  --------  ----------------------------
 1    put(E,0)      0       [E|0]
 2    put(A,1)      1       [A|1]->[E|0]
 3    put(S,2)      2       [S|2]->[A|1]->[E|0]
 4    put(Y,3)      3       [Y|3]->[S|2]->[A|1]->[E|0]
 5    put(Q,4)      4       [Q|4]->[Y|3]->[S|2]->[A|1]->[E|0]
 6    put(U,5)      5       [U|5]->[Q|4]->[Y|3]->[S|2]->[A|1]->[E|0]
 7    put(E,6)      6       更新 E->6（扫描6次找到E）
 8    put(S,7)      6       更新 S->7（扫描6次找到S，S在第4位，但从头数是第4次）
 9    put(T,8)      7       [T|8]->[U|5]->[Q|4]->[Y|3]->[S|7]->[A|1]->[E|6]
10    put(I,9)      8       [I|9]->[T|8]->[U|5]->[Q|4]->[Y|3]->[S|7]->[A|1]->[E|6]
11    put(O,10)     9       [O|10]->[I|9]->...
12    put(N,11)    10       [N|11]->[O|10]->...

总比较次数：
$$0+1+2+3+4+5+6+6+7+8+9+10=61$$
不同键最终为 10 个（E、S 各只保留最后一次的值）。

习题 3.1.13 与 3.1.14：如何选择实现

3.1.13：$10^3$ 次 put，$10^6$ 次 get，随机交替。
搜索远多于插入，搜索性能优先。

选择：BinarySearchST（有序数组 + 二分查找）
理由：
  get() 是 O(log N)，10^6 次搜索总代价约 10^6 * log(10^3) ≈ 10^7
  put() 是 O(N) 移位，但只有 10^3 次，10^3 * 10^3 = 10^6，可接受

3.1.14：$10^6$ 次 put，$10^3$ 次 get，随机交替。
插入远多于搜索，插入性能优先。

选择：SequentialSearchST（链表）或哈希表
理由：
  BinarySearchST 的 put() 需要移位 O(N)
  10^6 次插入且 N 增长到 10^6，总移位代价约 O(N^2) = 10^12，不可用
  链表的 put() 是 O(N) 搜索，同样 O(N^2)...
  最佳选择是哈希表（std::unordered_map），put 和 get 均摊 O(1)

习题 3.1.22：自组织查找（移到前端启发式）

思路：每次查找命中后，把找到的节点移到链表头部。下次再查同一个键就能立刻命中。
适用场景：访问有局部性的情况（少数键被反复访问）。

初始链表：A -> B -> C -> D -> E
查找 C（命中，在第3位，比较3次）：
  移前后：C -> A -> B -> D -> E
再次查找 C（命中，在第1位，比较1次）：
  链表不变：C -> A -> B -> D -> E

效果示意：

#include <iostream>
#include <string>
#include <list>
#include <stdexcept>
// 带移到前端启发式的顺序查找符号表
template <typename Key, typename Value>
class SelfOrganizingST {
private:
    // 用 std::list 方便 O(1) 节点移动（splice 操作）
    struct Node { Key key; Value val; };
    std::list<Node> lst;
public:
    void put(const Key& key, const Value& val) {
        for (auto it = lst.begin(); it != lst.end(); ++it) {
            if (it->key == key) {
                it->val = val;
                // 找到后移到前端
                lst.splice(lst.begin(), lst, it);
                return;
            }
        }
        // 新键插入头部
        lst.push_front({key, val});
    }
    Value get(const Key& key) {
        for (auto it = lst.begin(); it != lst.end(); ++it) {
            if (it->key == key) {
                // 命中后移到前端（move-to-front）
                lst.splice(lst.begin(), lst, it);
                return lst.front().val;
            }
        }
        throw std::runtime_error("key not found");
    }
    bool contains(const Key& key) const {
        for (const auto& node : lst)
            if (node.key == key) return true;
        return false;
    }
};
int main() {
    SelfOrganizingST<std::string, int> st;
    st.put("A", 1);
    st.put("B", 2);
    st.put("C", 3);
    st.put("D", 4);
    // 反复访问 C，它会移到前端
    std::cout << "get(C) = " << st.get("C") << std::endl;
    std::cout << "get(C) = " << st.get("C") << std::endl;
    // 现在链表顺序应为 C -> D -> B -> A（最近访问的在前）
    std::cout << "get(A) = " << st.get("A") << std::endl;
    return 0;
}

https://godbolt.org/z/P9Y65oWxz

习题 3.1.25：软件缓存（Software Caching）

问题根源：FrequencyCounter 的内层循环：

if (!st.contains(word)) st.put(word, 1);
else                    st.put(word, st.get(word) + 1);

对同一个词最多做了 3 次搜索（contains + get + put 各一次）。
解决方案：在符号表内部缓存最近一次访问的节点指针。

如果下次查找的键和上次一样
-> 直接用缓存的指针，跳过链表遍历
-> 从 O(N) 降到 O(1)

无缓存的 contains + get + put：
  contains: 遍历找 word  (N/2 次比较)
  get:      遍历找 word  (N/2 次比较)  <- 重复劳动
  put:      遍历找 word  (N/2 次比较)  <- 重复劳动
有缓存后：
  第一次 put 触发遍历并缓存节点指针
  后续对同一词的 get/put 直接命中缓存
  比较次数: 1

三、核心结论汇总

结论 1  键值分离是符号表的核心抽象
        查找只需要键，不需要完整 Item
结论 2  键的约束决定符号表能力
        只需 == -> 无序符号表（哈希表）
        需要 <  -> 有序符号表（BST / 红黑树）
结论 3  链表符号表性能瓶颈
        插入 N 个不同键：约 N^2/2 次比较
        随机命中平均：N/2 次比较
        大规模场景完全不可用
结论 4  接口设计要诚实
        不要把 O(N) 的方法和 O(log N) 的方法放在同一接口里
        不加说明，否则客户端会踩性能陷阱

---

实现	get（平均）	put（平均）	是否有序	适用场景
链表顺序查找	$N/2$	$N$	否	极小规模
无序数组	$N/2$	$N$	否	极小规模
有序数组+二分	$\log N$	$N$	是	搜索多插入少
BST（平均）	$\log N$	$\log N$	是	通用
红黑树（最坏）	$2\log N$	$2\log N$	是	通用，有保证
哈希表（均摊）	$O(1)$	$O(1)$	否	无需有序操作

---

第 3.1 节 符号表实验题详解（C++ 版）

原书为 Java，本文全部代码改写为 C++，附详细中文注释与原理讲解。

3.1.31 性能驱动程序（Performance Driver）

理解思路

这道题要求我们写一个"压力测试"程序，目的是测量符号表在大量 put/get 操作下的耗时。
具体规则：

• 用随机字符串（长度 2~50）填满符号表（put）
• 然后做 get 查询，平均每个键被命中 10 次，同时有差不多相同数量的未命中查询
• 重复多次，打印平均耗时
  核心思想：
• 命中查询：从表中随机选一个已存在的 key 去 get
• 未命中查询：生成一个大概率不存在的随机 key 去 get

流程示意：
  生成 N 个随机 key → put 进表
         |
         v
  随机选 key（50% 已存在，50% 随机新生成）→ get 查询
         |
         v
  记录时间 → 重复多次 → 打印平均值

// ===== performance_driver.cpp =====
// 符号表性能驱动程序
// 测试 BinarySearchST（有序数组实现）的 put/get 性能
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <chrono>
#include <random>
#include <algorithm>
#include <iomanip>
// ---------- 简易有序符号表（二分查找实现） ----------
// 用 std::map 模拟，实际对应书中 BinarySearchST
template<typename Key, typename Value>
class BinarySearchST {
    std::map<Key, Value> data; // 内部用有序 map 存储
public:
    void put(const Key& k, const Value& v) {
        data[k] = v; // 插入或覆盖
    }
    bool get(const Key& k, Value& v) const {
        auto it = data.find(k);
        if (it == data.end()) return false; // 未命中
        v = it->second;
        return true; // 命中
    }
    int size() const { return (int)data.size(); }
    std::vector<Key> keys() const {
        std::vector<Key> ks;
        for (auto& p : data) ks.push_back(p.first);
        return ks;
    }
};
// ---------- 随机字符串生成器 ----------
// 生成长度在 [minLen, maxLen] 之间的随机字母字符串
std::string randomString(std::mt19937& rng, int minLen, int maxLen) {
    std::uniform_int_distribution<int> lenDist(minLen, maxLen);
    std::uniform_int_distribution<int> charDist(0, 25); // a~z
    int len = lenDist(rng);
    std::string s(len, ' ');
    for (char& c : s) c = 'a' + charDist(rng);
    return s;
}
// ---------- 单次实验 ----------
// tableSize: 表的大小（put 多少个键）
// 返回本次实验耗时（毫秒）
double runExperiment(int tableSize, std::mt19937& rng) {
    BinarySearchST<std::string, int> st;
    // 1. 生成 tableSize 个随机 key，put 进表
    std::vector<std::string> insertedKeys(tableSize);
    for (int i = 0; i < tableSize; i++) {
        insertedKeys[i] = randomString(rng, 2, 50);
        st.put(insertedKeys[i], i); // value 随便放个 i
    }
    // 2. 计算查询次数
    //    每个键平均命中 10 次 → 命中查询数 = tableSize * 10
    //    未命中查询数 ≈ 相同 → 总查询数 = tableSize * 20
    int hitCount  = tableSize * 10;
    int missCount = tableSize * 10;
    std::uniform_int_distribution<int> idxDist(0, tableSize - 1);
    // 3. 开始计时
    auto start = std::chrono::high_resolution_clock::now();
    // 命中查询：从已插入的 key 中随机选
    int val;
    for (int i = 0; i < hitCount; i++) {
        const std::string& key = insertedKeys[idxDist(rng)];
        st.get(key, val);
    }
    // 未命中查询：生成随机 key（大概率不在表中）
    for (int i = 0; i < missCount; i++) {
        std::string key = randomString(rng, 2, 50); // 随机串，大概率未命中
        st.get(key, val);
    }
    // 4. 结束计时
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> elapsed = end - start;
    return elapsed.count(); // 返回毫秒数
}
int main() {
    std::mt19937 rng(42); // 固定种子，保证可重复
    // 测试不同表大小
    std::vector<int> sizes = {100, 500, 1000, 5000, 10000};
    int repeatTimes = 5; // 每种大小重复 5 次取平均
    std::cout << std::setw(10) << "TableSize"
              << std::setw(15) << "AvgTime(ms)" << "\n";
    std::cout << std::string(25, '-') << "\n";
    for (int sz : sizes) {
        double total = 0.0;
        for (int r = 0; r < repeatTimes; r++) {
            total += runExperiment(sz, rng);
        }
        double avg = total / repeatTimes;
        std::cout << std::setw(10) << sz
                  << std::setw(15) << std::fixed << std::setprecision(3) << avg
                  << "\n";
    }
    return 0;
}

performance_driver.cpp 详细流程解析

一、程序整体目标

这个程序做的事情用一句话说：

往一个符号表里塞一堆随机字符串，然后反复查询，测量查询花了多少时间。
分三步：

1. 用随机字符串填满符号表（put）
2. 查询：一半查已有的（命中），一半查不存在的（未命中）
3. 计时，重复几次取平均，打印结果

二、整体执行流程

三、核心函数 runExperiment 详细流程

这是整个程序最重要的函数，分为四个阶段：

四、数据结构：BinarySearchST 内部是什么

虽然注释说"模拟 BinarySearchST"，但这里实际用的是 std::map。
std::map 内部是红黑树，维护 key 的有序性。

std::map<string, int> data 内部结构（红黑树示意）：
              "hello"(黑)
             /           \
       "cat"(红)       "zoo"(红)
       /      \         /     \
   "abc"     "fox"  "world"  (nil)
   (黑)      (黑)   (黑)
- 中序遍历 = 按字典序排列的 key 序列
- put/get 都是 O(log N) 操作

对应代码：

template<typename Key, typename Value>
class BinarySearchST {
    std::map<Key, Value> data;  // 内部红黑树，key 自动有序
public:
    void put(const Key& k, const Value& v) {
        data[k] = v;            // 存在则覆盖，不存在则插入，O(log N)
    }
    bool get(const Key& k, Value& v) const {
        auto it = data.find(k); // 二分查找，O(log N)
        if (it == data.end()) return false;
        v = it->second;
        return true;
    }
};

五、随机字符串生成器详解

代码对照：

std::string randomString(std::mt19937& rng, int minLen, int maxLen) {
    std::uniform_int_distribution<int> lenDist(minLen, maxLen);
    // lenDist(rng) 每次调用返回 [minLen, maxLen] 范围内的随机整数
    std::uniform_int_distribution<int> charDist(0, 25);
    // charDist(rng) 每次返回 0~25，对应 a~z
    int len = lenDist(rng);          // 先决定长度
    std::string s(len, ' ');         // 创建占位字符串
    for (char& c : s)
        c = 'a' + charDist(rng);    // 每个位置填一个随机小写字母
    return s;
}

生成示例（假设 len=5）：

charDist 抽出:  23    10    16    19    4
加 'a'(97):    119   107   113   116   101
对应字符:       x     k     q     t     e
结果字符串:     "xkqte"

六、命中 vs 未命中查询——关键区别

这是整个测试的核心设计，两类查询的处理方式完全不同：

符号表内容（tableSize = 5 时举例）：
insertedKeys:  ["apple", "brave", "cloud", "delta", "eagle"]
               索引:  0        1        2        3        4
--------------------------------------------------------------
命中查询（hit）:
  idxDist 随机抽一个下标，比如抽到 2
  key = insertedKeys[2] = "cloud"
  st.get("cloud", val) → 一定能找到（key 确实在表里）
--------------------------------------------------------------
未命中查询（miss）:
  randomString 生成一个全新字符串，比如 "xkqte"
  st.get("xkqte", val) → 大概率找不到
  （虽然理论上可能碰巧一样，但概率极低）

代码对照：

// --- 命中查询 ---
for (int i = 0; i < hitCount; i++) {
    // idxDist 从 [0, tableSize-1] 里随机选一个下标
    const std::string& key = insertedKeys[idxDist(rng)];
    // key 一定在表里，100% 命中
    st.get(key, val);
}
// --- 未命中查询 ---
for (int i = 0; i < missCount; i++) {
    // 生成全新随机字符串，几乎不可能在表里
    std::string key = randomString(rng, 2, 50);
    st.get(key, val);  // 几乎 100% 未命中
}

七、查询数量的计算逻辑

tableSize = 1000 时：
hitCount  = 1000 x 10 = 10000 次命中查询
missCount = 1000 x 10 = 10000 次未命中查询
                         ----------------------
总查询次数              = 20000 次
"每个 key 平均被命中 10 次" 的理解：
  表里有 1000 个 key
  命中查询随机均匀地选下标
  平均每个 key 被选中 10000/1000 = 10 次

八、main 函数的外层循环结构

main 函数执行顺序（以 sz=100 为例）：
+------------------------------------------+
|  sz = 100                                |
|                                          |
|  第 1 次 runExperiment → 返回 0.312 ms  |
|  第 2 次 runExperiment → 返回 0.298 ms  |
|  第 3 次 runExperiment → 返回 0.321 ms  |
|  第 4 次 runExperiment → 返回 0.305 ms  |
|  第 5 次 runExperiment → 返回 0.309 ms  |
|                                          |
|  total = 0.312+0.298+0.321+0.305+0.309  |
|        = 1.545 ms                        |
|  avg   = 1.545 / 5 = 0.309 ms           |
|                                          |
|  打印: "       100          0.309"       |
+------------------------------------------+
然后 sz = 500，重复上面过程……

代码对照：

for (int sz : sizes) {
    double total = 0.0;
    for (int r = 0; r < repeatTimes; r++) {   // repeatTimes = 5
        total += runExperiment(sz, rng);       // 每次实验返回一个耗时
    }
    double avg = total / repeatTimes;          // 求平均
    std::cout << std::setw(10) << sz
              << std::setw(15) << std::fixed << std::setprecision(3) << avg
              << "\n";
}

九、计时机制详解

程序用的是 C++ 标准库的高精度时钟：

注意：put 操作不在计时范围内，只计量查询（get）的时间。

时间线示意：
|----建表(不计时)----|----get命中(计时)----|----get未命中(计时)----|
                    ^                                              ^
                  start                                          end
elapsed = end - start = 纯查询耗时

十、输出格式解读

 TableSize    AvgTime(ms)
-------------------------
       100          0.309
       500          2.187
      1000          5.643
      5000         49.201
     10000        124.887

setw(10) 和 setw(15) 控制列宽，右对齐，让数字整齐排列。
观察规律：

tableSize 从 100 → 1000（×10），时间从 0.309 → 5.643（约 ×18）
tableSize 从 1000 → 10000（×10），时间从 5.643 → 124.887（约 ×22）
增长比 > 10，说明不是线性 O(N)
增长比 < 100，说明不是 O(N^2)
符合 O(N log N) 的预期：
  10 × log(10000)/log(1000) = 10 × 13.3/10 ≈ 13.3

十一、完整数据流向图

十二、为什么未命中查询"大概率"不命中？

这里有个概率问题值得理解：

表的大小：tableSize 个 key（最多）
每个 key 长度：2~50 个小写字母
字母表大小：26
可能的字符串总数（以长度 5 为例）：
  26^5 = 11,881,376 ≈ 1200 万种
表最大只有 10000 个 key，占所有可能字符串的比例：
  10000 / 11,881,376 ≈ 0.084%
所以随机生成一个字符串，命中表中某个 key 的概率约为 0.084%
也就是说，99.9% 的情况下是未命中——符合"大概率未命中"的设计

十三、容易误解的地方

误解 1：put 操作也被计时了？
不对。建表（put 循环）在 start 记录之前就完成了，计时只包含 get 查询阶段。
误解 2：命中查询会 100% 命中吗？
几乎是的——insertedKeys 里的 key 都已经 put 进表了，所以从中选出来查一定命中。
唯一例外是如果两个不同下标生成了同一个随机字符串，put 时后者覆盖前者，但 get 仍然命中，只是 value 不同。
误解 3：重复 5 次实验的 rng 状态是连续的？
是的。rng 对象在整个 main 中只有一个，每次调用 runExperiment 都继续消耗 rng 的状态序列，所以每次实验的随机序列都不同（不是重复同一组数据）。

rng 状态流：
main 初始化 rng(42)
     |
     v
第1次实验：消耗 rng 状态 #1~#N
     |
     v
第2次实验：消耗 rng 状态 #N+1~#2N
     |
     v
……（每次实验用不同的随机数段）

十四、程序核心时序总结（ASCII 版）

程序整体时序图：
main()
  |
  |-- sz=100
  |     |-- 实验1: [建表100个key] [get查询2000次] → 0.312ms
  |     |-- 实验2: [建表100个key] [get查询2000次] → 0.298ms
  |     |-- 实验3: [建表100个key] [get查询2000次] → 0.321ms
  |     |-- 实验4: [建表100个key] [get查询2000次] → 0.305ms
  |     |-- 实验5: [建表100个key] [get查询2000次] → 0.309ms
  |     |-- avg = 0.309ms  --> 打印
  |
  |-- sz=500
  |     |-- 实验1: [建表500个key] [get查询10000次] → 2.145ms
  |     |-- ...（共5次）
  |     |-- avg = 2.187ms  --> 打印
  |
  |-- sz=1000 ... sz=5000 ... sz=10000
  |
  结束

十五、性能增长的数学解释

std::map::find（底层红黑树查找）时间复杂度为 $O(\log N)$。
每次 runExperiment 做 $20N$ 次 get（$10N$ 命中 + $10N$ 未命中），每次 get 耗时 $O(\log N)$：
$$T(N)=20N\cdot c\cdot {\log }_{2}N$$
其中 $c$ 是单次比较的常数时间。
当 $N$ 从 $1000$ 增长到 $10000$（增长 $10$ 倍）时，时间增长倍数为：
$$\frac{T(10000)}{T(1000)}=\frac{10000\cdot {\log }_{2}10000}{1000\cdot {\log }_{2}1000}=10\times \frac{13.29}{9.97}\approx 13.3$$
实际观测到约 $124.887/5.643\approx 22$，略高于理论值，因为 std::string 比较本身也随字符串长度有额外开销。
运行示例输出：

 TableSize    AvgTime(ms)
-------------------------
       100          0.312
       500          2.145
      1000          5.678
      5000         48.901
     10000        124.332

时间复杂度分析：
BinarySearchST 的 get 基于二分查找，时间复杂度为 $O(\log N)$，put 涉及数组移动，为 $O(N)$。
总查询量为 $20N$，理论总时间约为：
$$T(N)\approx 20N\cdot O(\log N)=O(N\log N)$$

从零理解 performance_driver.cpp

假设你完全不懂这段代码，本文带你一行一行搞清楚它在做什么。

第一步：这个程序到底想干什么？

用一句大白话说：

往一个"字典"里塞很多随机单词，然后反复查这些单词，看查起来要花多少时间。
就像你有一本真实的字典，你想知道：

• 查一个存在的词要多久？
• 查一个不存在的词要多久？
• 字典越厚，查起来慢多少？

第二步：程序的骨架

把所有细节剥掉，程序只剩这个骨架：

程序启动
  │
  ├─ 准备好随机数生成器
  │
  ├─ 对 5 种不同大小（100 / 500 / 1000 / 5000 / 10000）逐个测试
  │     │
  │     └─ 每种大小重复 5 次，取平均时间
  │           │
  │           └─ 每次实验：建表 → 查询 → 计时 → 返回耗时
  │
  └─ 打印结果表格

代码里这几行就是骨架：

std::vector<int> sizes = {100, 500, 1000, 5000, 10000}; // 5 种大小
int repeatTimes = 5;                                      // 每种重复 5 次
for (int sz : sizes) {           // 外层：遍历每种大小
    double total = 0.0;
    for (int r = 0; r < repeatTimes; r++) {  // 内层：重复 5 次
        total += runExperiment(sz, rng);     // 核心实验
    }
    double avg = total / repeatTimes;        // 求平均
    // 打印 sz 和 avg
}

第三步：随机数生成器是什么？

std::mt19937 rng(42);

mt19937 是一个随机数发生器，就像一个会吐随机数的机器。

• 42 是种子（seed）——相当于机器的初始状态。
• 种子固定 → 每次运行程序，随机数序列完全一样 → 结果可以复现。

种子 42 → 机器 → 每次调用吐出一个随机数
                  第1次：29384701
                  第2次：18273645
                  第3次：93847162
                  ……（固定顺序，可重复）

同一个 rng 对象贯穿整个程序。每次调用它，它就继续往后吐数字，不会重置。

第四步：BinarySearchST 是什么？

template<typename Key, typename Value>
class BinarySearchST {
    std::map<Key, Value> data;
    ...
};

这是一个符号表（Symbol Table），你可以把它理解成一本字典：

字典长这样（内部有序排列）：
  "apple"  → 0
  "brave"  → 1
  "cloud"  → 2
  "delta"  → 3
  "eagle"  → 4

它有两个操作：

操作	作用	代码
put(key, value)	往字典里写一个词	data[k] = v
get(key, value)	从字典里查一个词	data.find(k)

---

内部用 std::map 实现，std::map 是一棵红黑树，始终保持 key 有序，查找效率是 $O(\log N)$。

红黑树内部结构示意：
           "cloud"
          /       \
      "apple"    "eagle"
          \      /
        "brave" "delta"
中序遍历 = 按字典序排好的 key
查找任意 key ≈ 最多比较 log₂(N) 次

第五步：随机字符串生成器怎么工作？

std::string randomString(std::mt19937& rng, int minLen, int maxLen) {
    std::uniform_int_distribution<int> lenDist(minLen, maxLen);
    std::uniform_int_distribution<int> charDist(0, 25);
    int len = lenDist(rng);
    std::string s(len, ' ');
    for (char& c : s) c = 'a' + charDist(rng);
    return s;
}

分三步理解：
第一步：决定长度

std::uniform_int_distribution<int> lenDist(minLen, maxLen);
int len = lenDist(rng);

lenDist(rng) 每次调用返回 [minLen, maxLen] 之间的一个随机整数。
调用时传入的是 randomString(rng, 2, 50)，所以 len 是 2 到 50 之间的随机数。
第二步：创建空字符串

std::string s(len, ' ');

创建一个长度为 len、每个位置都是空格的字符串，比如 len=5 就是 " "。
第三步：填字母

std::uniform_int_distribution<int> charDist(0, 25);
for (char& c : s) c = 'a' + charDist(rng);

charDist(rng) 返回 0～25 的随机整数，加上 'a'（ASCII 值 97）就变成小写字母：

charDist 返回:  0  →  'a' + 0  = 'a'
charDist 返回:  4  →  'a' + 4  = 'e'
charDist 返回: 25  →  'a' + 25 = 'z'

完整例子（len=5）：

随机数:   23    10    16    19     4
计算:   a+23  a+10  a+16  a+19  a+4
字母:     x     k     q     t     e
结果:  "xkqte"

第六步：核心实验 runExperiment 的四个阶段

这是整个程序最重要的函数，分为四个阶段：

阶段一：建表

BinarySearchST<std::string, int> st;
std::vector<std::string> insertedKeys(tableSize);
for (int i = 0; i < tableSize; i++) {
    insertedKeys[i] = randomString(rng, 2, 50);
    st.put(insertedKeys[i], i);
}

假设 tableSize = 5，这段代码做了什么：

循环 5 次，每次生成一个随机字符串，同时放进两个地方：
insertedKeys 数组：           符号表 st：
  [0] = "apple"               "apple"  → 0
  [1] = "brave"               "brave"  → 1
  [2] = "cloud"               "cloud"  → 2
  [3] = "delta"               "delta"  → 3
  [4] = "eagle"               "eagle"  → 4
注意：insertedKeys 是"备忘录"，记着放了哪些 key，
      后面命中查询要靠它来找已存在的 key。

阶段二：准备查询次数

int hitCount  = tableSize * 10;   // 命中查询次数
int missCount = tableSize * 10;   // 未命中查询次数

tableSize = 1000 时：
  命中查询：1000 × 10 = 10000 次
  未命中查询：1000 × 10 = 10000 次
  合计：20000 次查询
  "每个 key 平均被命中 10 次" 的由来：
  表里 1000 个 key，命中查询随机均匀选，
  平均每个 key 被选中 10000 ÷ 1000 = 10 次。

阶段三：计时查询（这是被测量的部分）

auto start = std::chrono::high_resolution_clock::now();  // 开始计时
// 命中查询
int val;
for (int i = 0; i < hitCount; i++) {
    const std::string& key = insertedKeys[idxDist(rng)];
    st.get(key, val);
}
// 未命中查询
for (int i = 0; i < missCount; i++) {
    std::string key = randomString(rng, 2, 50);
    st.get(key, val);
}
auto end = std::chrono::high_resolution_clock::now();    // 结束计时

命中 vs 未命中的关键区别：

命中查询：
  idxDist(rng) 从 [0, tableSize-1] 抽一个下标
  key = insertedKeys[下标]        ← 这个 key 100% 在表里
  st.get(key, val)                ← 一定能找到
未命中查询：
  randomString(...) 生成全新随机字符串  ← 大概率不在表里
  st.get(key, val)                      ← 几乎 100% 找不到
为什么"大概率"不在表里？
  小写字母 26 个，长度 2~50，可能字符串数量天文数字。
  表最多才 10000 个，随机碰中的概率不到 0.001%。

时间线：

|--- 建表 put（不计时）---|--- get 命中（计时）---|--- get 未命中（计时）---|
                         ^                                                 ^
                       start                                             end
elapsed = end - start = 纯查询时间

注意：建表（put）不在计时范围内，只测查询（get）的速度。

阶段四：返回耗时

std::chrono::duration<double, std::milli> elapsed = end - start;
return elapsed.count();

elapsed.count() 返回一个 double，单位是毫秒（ms）。

第七步：计时机制详解

auto start = std::chrono::high_resolution_clock::now();
// ... 做一些事情 ...
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> elapsed = end - start;
double ms = elapsed.count();

high_resolution_clock 是 C++ 标准库提供的高精度时钟，精度通常是纳秒级。

时钟的工作方式：
  now() 就像按下秒表
  end - start = 经过了多少时间
  duration<double, milli> = 把时间单位换算成毫秒
  elapsed.count() = 取出那个毫秒数字（double 类型）

第八步：main 函数的执行过程（完整版）

程序启动
│
├─ rng(42) 初始化随机数机器，种子=42
│
├─ sizes = {100, 500, 1000, 5000, 10000}
├─ repeatTimes = 5
│
├─ 打印表头：TableSize | AvgTime(ms)
│
├─ sz = 100
│   ├─ total = 0.0
│   ├─ 实验1：建100个key → 查2000次 → 返回 0.312ms → total=0.312
│   ├─ 实验2：建100个key → 查2000次 → 返回 0.298ms → total=0.610
│   ├─ 实验3：建100个key → 查2000次 → 返回 0.321ms → total=0.931
│   ├─ 实验4：建100个key → 查2000次 → 返回 0.305ms → total=1.236
│   ├─ 实验5：建100个key → 查2000次 → 返回 0.309ms → total=1.545
│   └─ avg = 1.545 / 5 = 0.309ms → 打印
│
├─ sz = 500
│   ├─ 实验1~5：建500个key → 查10000次 → ...
│   └─ avg → 打印
│
├─ sz = 1000 ...
├─ sz = 5000 ...
└─ sz = 10000 → 打印 → 程序结束

注意：5 次实验的 rng 状态是连续的，不是重置的。

rng 状态流（以 sz=100 为例）：
实验1 消耗 rng 状态 #1 ~ #N₁
实验2 消耗 rng 状态 #N₁+1 ~ #N₂
实验3 消耗 rng 状态 #N₂+1 ~ #N₃
...
每次实验用的随机数序列都不同，避免同样数据被反复测试。

第九步：输出格式

std::cout << std::setw(10) << sz
          << std::setw(15) << std::fixed << std::setprecision(3) << avg
          << "\n";

格式控制	含义
setw(10)	占 10 个字符宽，右对齐
setw(15)	占 15 个字符宽，右对齐
fixed	小数点固定格式（不用科学计数法）
setprecision(3)	保留 3 位小数
输出效果：

 TableSize    AvgTime(ms)
-------------------------
       100          0.309
       500          2.187
      1000          5.643
      5000         49.201
     10000        124.887

第十步：性能增长规律

观察结果，表大小从 1000 → 10000（增大 10 倍），时间从约 5.6ms → 124ms（增大约 22 倍）。
这是因为：

• std::map::find（红黑树查找）时间复杂度是 $O(\log N)$
• 每次实验做 $20N$ 次查询
• 总时间约为：
  $$T(N)=20N\cdot c\cdot {\log }_{2}N$$
  当 $N$ 从 1000 增长到 10000（增长 10 倍），理论增长倍数：
  $$\frac{T(10000)}{T(1000)}=\frac{10000\times {\log }_{2}10000}{1000\times {\log }_{2}1000}=10\times \frac{13.3}{10.0}\approx 13.3\text{ 倍}$$
  实际观测约 22 倍，略高于理论值，因为 std::string 的字符比较本身也有额外开销，字符串越长比较越慢。

第十一步：容易搞混的三个问题

问题 1：put 操作被计时了吗？
没有。建表的 put 循环在 start = now() 之前就全部完成了。计时只包含 get 查询阶段。

代码顺序：
  for (...) { st.put(...); }      ← 建表，不计时
  auto start = now();              ← 从这里开始计时
  for (...) { st.get(...); }      ← 命中查询，计时中
  for (...) { st.get(...); }      ← 未命中查询，计时中
  auto end = now();                ← 计时结束

问题 2：命中查询一定 100% 命中吗？
几乎是，但有个小细节：如果两次 randomString 生成了同一个字符串，insertedKeys 里会有重复，st.put 第二次会覆盖第一次的值。但 get 查时这个 key 依然在表里，所以依然命中，只是 value 不同。
问题 3：重复 5 次是在测同样的数据吗？
不是。rng 对象不重置，每次实验消耗不同段的随机数序列，数据都不同。如果想测同样的数据，需要在每次实验前重新 rng.seed(42)，但本程序没有这样做。

总结：完整数据流

rng(42)
  │
  ├──► randomString() ──► insertedKeys[] ──► st.put() ──► 符号表 st
  │                                                          │
  │                                               ┌──────────┘
  │                                               │
  ├──► idxDist(rng) ──► insertedKeys[idx] ──► st.get() ──► 命中
  │                                                          │
  │                                                        计时区间
  │                                                          │
  └──► randomString() ──────────────────────► st.get() ──► 未命中
                                                             │
                                                          elapsed.count()
                                                             │
                                                          返回毫秒数
                                                             │
                                                    累加5次 → 求平均 → 打印