4.1. 词典 ADT¶

计算机程序最常见的目标就是存储和取回数据。 本书很大一部分内容是关于如何高效地组织数据记录集合， 以便能够快速地存储和取回它们。 本节我们描述这样一个集合的简单接口，称为 词典 。 词典 ADT 提供了在集合中存储记录、查找记录和删除记录的操作。 这个 ADT 为我们比较各种数据结构提供了一个标准基础。 粗略地说，任何支持插入、查找和删除的数据结构都可以称为"词典"。

词典依赖于 查找键 和 可比较 对象这两个概念。 为实现词典的查找功能，我们将要求键是 全序 的。 对天然是多维的字段（例如二维或三维空间中的点）进行排序， 如果我们想利用其多维特性，会带来特殊的机会。 这个问题由 空间数据结构 处理。

下面是用代码定义的一个简单抽象词典类。

/** 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");

就目前的写法而言，这个示例的一个问题是， 词典依赖于程序员自觉保持键的一致性。 这些词典本应拥有 同构 元素。 但没有什么能阻止程序员向姓名词典中插入一个整数键， 或者用一个整数查找键去查找。 这个问题可以通过使用 C++ 模板或 Java 泛型来处理。

词典的基本操作是查找与给定键相匹配的记录。 这就引出了如何从记录中 提取键 的问题。 我们通常假定词典实现存储 键值对 ， 以便能够提取与该词典中某条记录相关联的键。

词典类的 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 操作留下的空缺。

搜索树 是能够在 \(\Theta(\log n)\) 时间内 执行插入、查找和删除这三种关键操作的结构。