应用

一、引言

• 符号表的历史与现代作用：
  • 早期：从机器语言数字地址到汇编语言符号名称。
  • 现代：支持科学数据、网络信息、互联网基础设施（如DNS路由）。
• 应用场景：
  • 科学：基因组学中的分子标记。
  • 网络：搜索、数字图书馆。
  • 基础架构：文件共享、流媒体。

二、符号表实现选择

1. 性能总结：
   • 顺序查询：O(N)，简单但慢。
   • 二分查找：O(lgN)查找，O(N)插入。
   • 二叉查找树：平均O(lgN)，最坏O(N)。
   • 红黑树：稳定O(lgN)，支持有序操作。
   • 拉链法散列表：平均O(1)，依赖均匀散列。
   • 线性探测法：平均O(1)，使用率敏感。
2. 选择建议：
   • 散列表：首选，简单高效，适用于标准键类型。
   • 红黑树：需最坏情况保证或有序操作时使用。
3. 改进方向：
   • 原始数据类型：减少引用开销（如拉链法）。
   • 重复键：支持多值绑定（如交易系统）。

三、集合API

1. 定义：
   • SET：无值符号表，仅维护键集合。
   • 方法：add()、delete()、contains()等。
2. 变体：
   • 有序SET：支持min()、max()等。
   • 无序HashSET：仅基本操作。
3. 应用：过滤器：
   • Dedup：去重，保留首次出现的键。
   • 白名单：只输出名单中的键。
   • 黑名单：输出不在名单中的键。

四、字典类用例

1. 特点：动态构建符号表，支持查询和更新。
2. 典型应用：
   • 电话黄页：人名→电话。
   • 字典：单词→定义。
   • 账户：账号→余额。
   • 基因组：密码子→氨基酸。
   • 文件系统：文件名→地址。
   • DNS：域名→IP。
3. 实现：LookupCSV，从CSV文件构建字典，查询键值。

五、索引类用例

1. 特点：键关联多个值，反向索引支持值查键。
2. 典型应用：
   • 基因组：氨基酸→密码子。
   • 交易：账号→交易列表。
   • IMDB：电影→演员。
   • 搜索：关键字→网页。
3. 实现：LookupIndex，构建正向和反向索引。
4. 反向索引：
   • IMDB：演员→电影。
   • 图书：术语→页码。
   • 文件搜索：关键字→文件。
5. 工具：FileIndex，为文件集构建单词索引。

六、稀疏向量

1. 背景：
   • 矩阵-向量乘法，标准实现O(N²)。
   • 稀疏矩阵（如PageRank）非零项少，需优化。
2. 实现：SparseVector，用HashST存非零项。
   • 时间：O(N + 非零项数)。
   • 空间：远小于N²。
3. 意义：
   • Google PageRank：N~10亿，提升亿倍效率。
   • 科学计算：广泛用于稀疏数据处理。
4. 优化建议：结合原始数组，测试性能瓶颈。