Ch3 查找
在本章中, 我们将对一系列 经过实践检验的 经典查找算法进行介绍和讨论. 我们会使用 符号表 描述一张 抽象 的表格, 并假定会将 信息 (值) 存储于其中, 按照指定的 键 检索这些信息. 键 和 值 的具体意义取决于不同的实际应用.
符号表 往往又被称为 字典. 类比于英语字典, 键 就是 单词, 值 就是该单词对应的 定义, 发音和词源等解释. 符号表也可以被称为 索引. 在一本书的索引中, 键 就是 术语, 而 值 就是 书中该术语出现的所有位置.
在说明基本的 API 和两种实现后, 我们会使用三种数据结构: 二叉查找树, 红黑树, 散列表 对符号表进行高效的实现.
3.1 符号表
符号表的主要作用是 将一个键和一个值相关联. 要实现符号表, 首先需要定义其背后的数据结构, 并指明创建并操作这种数据结构, 以实现插入, 查找等操作所需的算法.
定义
符号表 是一种 存储键值对 的数据结构, 支持两种操作: 插入 (将一对新的键值对存入表中) 和 查找 (根据给定的键得到相应的值).
API
显然, 符号表也是一种典型的 抽象数据类型. 其 API 如下:
public class |
ST<Key, Value> |
|
|---|---|---|
ST() |
创建符号表 | |
void |
put(Key key, Value, val) |
将键值对存入表中, 若值为空则将键 key 从表中删除 |
Value |
get(Key key) |
获取键 key 对应的值, 若键不存在则返回 null |
void |
delete(Key key) |
从表中删去键 key 及其对应的值 |
boolean |
contains(Key key) |
检查键 key 在表中是否有对应的值 |
boolean |
isEmpty() |
检查表是否为空 |
int |
size() |
返回表中键值对的数量 |
Iterable<Key> |
keys() |
返回表中所有键的集合 |
我们下面再解释一些具体实现中的一些设计规则.
1. 泛型
和排序一样, 在设计方法时, 我们不指定处理对象的类型. 我们通过 明确指定查找时键和值的类型 区分它们.
2. 键重复的情形
在所有实现中我们都遵循下列规则:
- 键值一一对应.
- 当将要存入的键值对和表中已有的键 (及其关联的值) 相冲突时, 用新值替换旧的.
3. 空键和空值
我们的实现中不允许空键和空值.
4. 删除操作
在符号表中, 删除的实现可以是 延时删除 (将键对应的值置为空, 然后在某个时候删掉所有值为空的键), 或 即时删除 (立刻从表中删除指定的键). 在我们的实现中, 我们采用 即时删除.
5. 便捷方法
为简化用例, 我们再添加两个便捷方法:
| 方法 | 默认实现 |
|---|---|
void delete(Key key) |
put(key, null) |
boolean contains(key) |
return get(key) != null; |
bolean isEmpty() |
return size() == 0; |
6. 迭代
为方便用例处理表中的所有键值, 我们强制所有实现必须包含 Iterable 接口.
7. 键的等价性
对于标准数据类型, 我们可以使用 Java 内置的等价性实现 equals(). 若需要自定义键, 就需要 重写 equals() 方法. 为了确保表的一致性, 最好使用 不可变的数据类型 作为键.
