3-1 Symbol Tables

发表于   |   分类于

为了方便查找，人们设计出符号表（symbol table）这样一个抽象数据类型：在其中存储信息（value），之后可以通过指明一个键（key）来访问这个信息。符号表有时候也可以称为字典，有时也可以称为索引。

符号表的主要目标是把一个值（value）与一个键（key）联系起来。用户可以插入 “键-值” 对（insert/put），也可以通过一个键来找到一个值（search/get）。除此之外，为方便使用，符号表还提供了其他一些方法。

API

class ST <Key, Value> :
                    ST()                          # create a symbol table
              void put(Key key, Value val)       # put key-value pair into the table(remove key from table if value is null)
                Value get(Key key)                  # value paired with key(null if key is absent)
              void delete(Key key)               # remove key (and its value) from table
           boolean contains(Key key)             # is there a value paired with key?
           boolean isEmpty()                     # is the table empty?
               int size()                        # number of key-value pairs in the table
    Itertable<Key> keys()                        # all the keys in the table

重复的键

我们采用以下约定：

  • 每个键只联系着一个值
  • 当用户插入一个 “键-值” 对时，如果这个键已经在符号表中，则新的值会替换旧的值

空键

键不能为空（NULL）

空值

我们采取如下约定：没有键与空值联系到一起。这个约定可以产生两个我们想要的效果：

  1. 我们可以通过判断 get() 方法是否返回一个空值来确定表中是否已经定义了某个键

  2. 我们可以用 put() 方法，让第二个参数为 null，来实现删除操作

删除

  • 消极删除

我们将要删除的键与空值联系到一起，之后再删除所有这样的键（清空内存）

  • 积极删除

我们总是立即从表中删除键

有序符号表（ordered symbol tables）

API

class ST <Key extends Comparable<Key>, Value> :
                    ST()                          # create a symbol table
              void put(Key key, Value val)       # put key-value pair into the table(remove key from table if value is null)
                Value get(Key key)                  # value paired with key(null if key is absent)
              void delete(Key key)               # remove key (and its value) from table
           boolean contains(Key key)             # is there a value paired with key?
           boolean isEmpty()                     # is the table empty?
               int size()                        # number of key-value pairs in the table
               Key min()                         # smallest key
               Key max()                         # largest key
               Key floor(Key key)                # largest key less than or equal to key
               Key ceiling(Key key)              # smallest key greater than or equal to key
               int rank(Key key)                 # number of keys less than key
               Key select(int k)                 # key of rank k
              void deleteMin()                   # delete smallest key
              void deleteMax()                   # delete largest key
               int size(Key lo, Key hi)          # numbers of keys in [lo..hi]
    Itertable<Key> keys(Key lo, Key hi)          # keys in [lo..hi], in sorted order
    Itertable<Key> keys()                        # all the keys in the table, in sorted order
Minimum and maximum

和优先队列很相似，主要区别在于优先队列允许相同的键，而符号表中不允许

性能测试

当我们研究符号表的效率时，有两个测量尺度很重要：

  • 总单词数
  • 不同的单词数（distinct）

我们的目标是设计出一种符号表的实现，可以处理大规模数据的 许多次 get() 和 put() 操作。
目前，我们假设以下环境：

  • 查找和插入操作是混合的（intermixed）
  • 互异（distinct）的单词数不是个小数目
  • 查找次数远大于插入次数是很可能的
  • 查找和插入的顺序不是随机的，尽管不可预测

下面有两种实现：

实现一：无序链表的顺序查找（sequential search in an unordered linked list）

对于 get() 操作，我们顺序遍历链表，比较元素的键。如果找到匹配的，则返回元素的值；如果没找到匹配，则返回 null。

对于 put() 操作，我们顺序遍历链表，比较元素的键。如果找到匹配的，则更新元素的值；如果没找到匹配，则新建一个节点，并把它插入到链表头部。

————————————————————————

对于一个大小为 N，基于无序链表实现的符号表，查找失败和插入均需要 N 次比较，而查找命中在最坏情况下需要 N 次比较，平均需要 ~N/2 次。在实际应用中，插入 N 个键互异的元素到一个初始为空的链表实现的符号表中需要 ~N2/2 次比较操作

————————————————————————

实现二：有序数组的二分查找（Binary search in an ordered array）

有序符号表的底层实现是两个平行的数组，一个用来存储键，另一个用来存储值。这种实现的核心是 rank() 方法。

实现 get() 方法，我们用 rank() 得到欲查找键在数组中应该排的位置，如果和该处的键相同，直接访问；否则返回 null

实现 put() 方法，我们用 rank() 得到欲查找键在数组中应该排的位置，如果和该处的键相同，更新对应的 value 值；如果不同，则将所有更大的键后移一位，将新键插入到这里

默认使用大小可自动变的数组 (array resizing)

我们使用二分查找来实现 rank()，rank() 满足以下特点：

  • 如果键在符号表中，rank() 返回它在符号表中的索引，这个数字和表中比它小的键的总数是相同的。

  • 如果键不再符号表中，rank() 也返回表中比它小的键的总数

    // 递归的二分查找
int rank(Key key, int lo, int hi)
{
    if (hi < lo) return lo;
    int mid = lo + (hi - lo) / 2;
    int cmp = key.compareTo(keys[mid]);
    if      (cmp < 0)
        return rank(key, lo, mid-1);
    else if (cmp > 0)
        return rank(key, mid+1, hi);
    else return mid;
}

//循环的二分查找
int rank(Key key)
{
    int lo = 0, hi = N-1;
    while(lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(keys[mid]);
        if      (cmp < 0)    hi = mid - 1;
        else if (cmp > 0)    lo = mid + 1;
        else return mid;
    }
    return lo;
}

————————————————————————

对于一个 N 键有序数组，二分查找法每次查找使用不超过 lgN+1 次比较操作（无论查找匹配或失败）

————————————————————————

对于一个 N 键有序数组，插入一个新键在最差情况下需要用 ~2N 次数组访问（array access），所以将 N 个键插入到一个初始为空的数组中最差需要 ~N2 次数组访问

————————————————————————

两种实现的开销比较 & 其他实现的比较

Cost summary for basic symbol-table implementations

algorithm worst-case
search		 worst-case
insert		 average-case
search hit		 average-case
insert		 efficiently
support ordered
operations
sequential search
(unordered linked list)		 N N N/2 N no
binary search
(ordered array)		 lgN 2N lgN N yes

Pros and cons of symbol-table implementations

underlying
datastructure		 implementations pros cons
linked list
(sequential search)		 _SequentialSearchST_ best for tiny STs slow for large STs
ordered array
(binary search)		 _BinarySearchST_ optimal search
and space,
order-based ops		 slow insert
binary search tree _BST_ easy to
implement,
order-based ops		 no guarantees
space for links
balanced BST _RedBlackBST_ optimal search
and insert,
order-based ops		 space for links
hash table SeparateChainingHashST
LinearProbingHashST		 fast search/insert
for common types
of data		 need hash for each type
no order-based ops
space for links/empty