7.4. 字典 ADT¶
7.4.1. 字典 ADT¶
计算机程序最常见的目标就是存储和取回数据。本书很大一部分内容是关于如何高效地组织数据记录集合，以便能够快速地存储和取回它们。本节我们描述这样一个集合的简单接口，称为 字典 。字典 ADT 提供了在集合中存储记录、查找记录和删除记录的操作。这个 ADT 为我们比较各种数据结构提供了一个标准基础。粗略地说，任何支持插入、查找和删除的数据结构都可以称为"字典"。
字典依赖于 查找键 和 可比较（comparable） 对象这两个概念。 为实现字典的查找功能，我们将要求键是 全序 的。 对天然是多维的字段（例如二维或三维空间中的点）进行排序， 如果我们想利用其多维特性，会带来特殊的机会。 这个问题由 空间数据结构 处理。
下面是用代码定义的一个简单抽象字典类。
/** The Dictionary abstract class. */
public interface Dictionary {
/** Reinitialize dictionary */
public void clear();
/** Insert a record
@param key The key for the record being inserted.
@param elem The record being inserted. */
public void insert(Comparable key, Object elem);
/** Remove and return a record.
@param key The key of the record to be removed.
@return A maching record. If multiple records match
"k", remove an arbitrary one. Return null if no record
with key "k" exists. */
public Object remove(Comparable key);
/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public Object removeAny();
/** @return A record matching "k" (null if none exists).
If multiple records match, return an arbitrary one.
@param key The key of the record to find */
public Object find(Comparable key);
/** @return The number of records in the dictionary. */
public int size();
}
/** The Dictionary abstract class. */
public interface Dictionary<K extends Comparable<K>, E> {
/** Reinitialize dictionary */
public void clear();
/** Insert a record
@param k The key for the record being inserted.
@param e The record being inserted. */
public void insert(K key, E elem);
/** Remove and return a record.
@param k The key of the record to be removed.
@return A maching record. If multiple records match
"k", remove an arbitrary one. Return null if no record
with key "k" exists. */
public E remove(K key);
/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public E removeAny();
/** @return A record matching "k" (null if none exists).
If multiple records match, return an arbitrary one.
@param k The key of the record to find */
public E find(K key);
/** @return The number of records in the dictionary. */
public int size();
}
方法 insert 和 find 是这个类的核心。方法 insert 接受一条记录并将其插入字典。方法 find 接受一个键值，并从字典中返回某个其键与所提供的值相匹配的记录。如果字典中有多条记录具有该键值，则不规定返回哪一条。
方法 clear 只是重新初始化字典。方法 remove 与 find 类似，只是它还会把从字典中返回的记录删除。同样，如果字典中有多条记录匹配所需的键，则不规定实际删除并返回的是哪一条。方法 size 返回字典中元素的数目。
剩下的方法是 removeAny 。它与 remove 类似，只是它不接受键值。相反，它从字典中删除一条任意记录（如果存在的话）。这个方法的目的是让用户能够遍历字典中的所有元素（当然，在此过程中字典会变为空）。如果没有 removeAny 方法，字典用户就无法访问他们尚不知道键值的字典记录。有了 removeAny 方法，用户就可以处理字典中的所有记录，如下面的代码片段所示。
while (dict.size() > 0) {
Object it = dict.removeAny();
doSomething(it);
}
还有其他一些似乎更自然的遍历字典的方法，例如使用 "first" 和 "next" 函数。但并非我们想用来实现字典的所有数据结构都能高效地完成 "first"。例如，哈希表实现无法高效地定位表中键值最小的记录。通过使用 RemoveAny ，我们获得了一种提供通用访问的机制。
给定一个存储某种特定类型记录的数据库，我们可能想用多种方式查找记录。例如，我们可能想把工资单记录存储在一个允许按 ID 查找的字典中，同时把这些相同的记录存储在第二个允许按姓名查找的字典中。
下面是工资单记录的一个实现。
/** A simple payroll entry with ID, name, address fields */
public class Payroll {
private Integer ID;
private String name;
private String address;
/** Constructor */
Payroll(int inID, String inname, String inaddr) {
ID = inID;
name = inname;
address = inaddr;
}
/** Data member access functions */
public Integer getID() { return ID; }
public String getname() { return name; }
public String getaddr() { return address; }
}
类 Payroll 有多个字段，每个字段都可以用作查找键。只需改变键的类型，并在每条记录中使用适当的字段作为键值，我们就能定义一个以 ID 字段为查找键的字典、一个以姓名字段为查找键的字典，以及一个以地址字段为查找键的字典。下面是一个示例，其中 Payroll 对象存储在两个单独的字典中，一个使用 ID 字段作为键，另一个使用姓名字段作为键。
// IDdict organizes Payroll records by ID
Dictionary IDdict = new UALDictionary();
// namedict organizes Payroll records by name
Dictionary namedict = new UALDictionary();
Payroll foo1 = new Payroll(5, "Joe", "Anytown");
Payroll foo2 = new Payroll(10, "John", "Mytown");
IDdict.insert(foo1.getID(), foo1);
IDdict.insert(foo2.getID(), foo2);
namedict.insert(foo1.getname(), foo1);
namedict.insert(foo2.getname(), foo2);
Payroll findfoo1 = (Payroll)IDdict.find(5);
Payroll findfoo2 = (Payroll)namedict.find("John");
就目前的写法而言，这个示例的一个问题是， 字典依赖于程序员自觉保持键的一致性。 这些字典本应拥有 同构（homogeneity） 元素。 但没有什么能阻止程序员向姓名字典中插入一个整数键， 或者用一个整数查找键去查找。 这个问题可以通过使用 C++ 模板或 Java 泛型来处理。
字典的基本操作是查找与给定键相匹配的记录。 这就引出了如何从记录中 提取键（comparable） 的问题。 我们通常假定字典实现存储 键值对 ， 以便能够提取与该字典中某条记录相关联的键。
字典类的 insert 方法支持键值对的实现，因为它接受两个参数：一条记录以及该记录在该字典中关联的键。
既然我们已经定义了字典 ADT，并确定了为字典条目存储键值对这一设计方法，就可以考虑实现它的方式了。两种可能的方式是使用基于数组的线性表或链表。下面是使用（未排序的）基于数组的线性表实现的字典。
// Dictionary implemented by unsorted array-based list.
public class UALDictionary implements Dictionary {
private static final int defaultSize = 10; // Default size
private AList list; // To store dictionary
// Constructors
UALDictionary() { this(defaultSize); }
UALDictionary(int sz) { list = new AList(sz); }
// Reinitialize
public void clear() { list.clear(); }
// Insert an element: append to list
public void insert(Comparable k, Object e) {
KVPair temp = new KVPair(k, e);
list.append(temp);
}
// Use sequential search to find the element to remove
public Object remove(Comparable k) {
Object temp = find(k);
if (temp != null) { list.remove(); }
return temp;
}
// Remove the last element
public Object removeAny() {
if (size() != 0) {
list.moveToEnd();
list.prev();
KVPair e = (KVPair)list.remove();
return e.value();
}
else { return null; }
}
// Find k using sequential search
// Return the record with key value k
public Object find(Comparable k) {
for(list.moveToStart(); list.currPos() < list.length();
list.next()) {
KVPair temp = (KVPair)list.getValue();
if (k.compareTo(temp.key()) == 0) {
return temp.value();
}
}
return null; // "k" does not appear in dictionary
}
// Return list size
public int size() { return list.length(); }
}
考察类 UALdict （UAL 表示"未排序的基于数组的线性表"），我们很容易看出 insert 是一个常数时间操作，因为它只是把新记录插入到线性表的末尾。然而， find 和 remove 在平均情况和最坏情况下都需要 \(\Theta(n)\) 时间，因为我们需要进行顺序查找。方法 remove 尤其必须触及线性表中的每条记录，因为一旦找到所需记录，其余记录就必须在线性表中向下移动以填补空缺。方法 removeAny 删除线性表中的最后一条记录，所以这是一个常数时间操作。
作为替代方案，我们可以用链表来实现字典。其实现与 UALDictionary 的实现相当类似，各函数的开销在渐近意义下应当相同。
另一种替代方案是用有序线性表来实现字典。这种方法的优点是，我们或许能够通过使用二分查找来加速 find 操作。为此，我们首先必须定义 List ADT 的一个变体以支持有序线性表。有序线性表与未排序线性表有些不同，它不允许用户控制元素插入的位置。因此， insert 方法在有序线性表中必须与在未排序线性表中相当不同。同样，也不允许用户向线性表追加元素。由于这些原因，有序线性表无法通过从 List ADT 直接继承来实现。
对于长度为 \(n\) 的线性表，有序线性表中 find 的开销是 \(\Theta(\log n)\) 。这比未排序线性表中 find 的开销有了很大改进。遗憾的是， insert 的开销从未排序线性表中的常数时间变为有序线性表中的 \(\Theta(n)\) 时间。字典 ADT 的有序线性表实现是否比未排序线性表实现更高效，取决于要执行的 insert 和 find 操作的相对数量。如果使用的 find 操作远多于 insert 操作，那么用有序线性表来实现字典可能是值得的。在两种情况下， remove 在最坏和平均情况下都需要 \(\Theta(n)\) 时间。即使我们使用二分查找来减少删除前查找记录的时间，我们仍然需要在线性表中向下移动其余记录，以填补 remove 操作留下的空缺。
搜索树（search tree） 是能够在 \(\Theta(\log n)\) 时间内 执行插入、查找和删除这三种关键操作的结构。
