符号表
符号表是一种存储键值对的数据结构，支持两种操作：插入(put)，即将一组新的键值对存入表中；查找(get)，即根据给定的键得到相应的值。
1 API
为了保证代码的一致性，简要说明具体实现中的几个设计决策：
1）每个键只对应着一个值。
2）当用例代码向表中存入键值对和表中已有的键（及关联的值）冲突时，新的值会替代旧的值。
这些规则定义了关联数组的抽象形式。
3）键不能为空。
4）键不能关联着空值。这样做可以有两个结果：①可以用get()方法是否返回空来测试给定键是否存在于符号表中。②可以将空值作为put()方法的第二个参数存入表中来实现删除。
5）删除操作：①延时删除：将键对应的值置为空，然后在某个时候删除所有值为空的键。put(key.null)是delete(key)的一种简单的（延时型）实现。②实时删除：delete()。
6）便捷方法
7）迭代：使用key()方法来返回一个Interable对象以便用例遍历所有的键。
2 有序符号表
3 用例举例
符号表的典型问题：
1）混合使用查找和插入的操作。
2）大量的不同键。
3）查找操作比插入操作多的多。
4）虽然不可预测，但是查找和插入操作使用的模式并非随机。
4 无序链表的顺序查找
符号表的一种简单实现为使用链表：put()和get()方法都是使用equals()方法来一个一个地顺序遍历符号表中所有键。
其中符合欧标实现使用了一个私有内部Node类来在链表中保存键和值。get()的实现会顺序地搜索链表查找给定的键（找到则返回相关联的值）。put()的实现也会顺序地搜索链表查找给定的键，如果找到则更新相关联的值，否则用给定的键值对创建一个新的结点，插入到链表的开头。
public class SequentialSearchST<Key, Value>
{
private Node first; // first node in the linked list
private class Node
{ // linked-list node
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
public Value get(Key key)
{ // Search for key, return associated value.
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key))
return x.val; // search hit
return null; // search miss
}
public void put(Key key, Value val)
{ // Search for key. Update value if found; grow table if new.
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key))
{ x.val = val; return; } // Search hit: update val.
first = new Node(key, val, first); // Search miss: add new node.
}
}
在一个(无序的)链表符号表中，有N个键值对的查找和插入，这两个都需要N个比较，而搜索结果在最坏的情况下进行N次比较。特别地，在一空表插入N个不同的键需要使用~N2/2比较。
5 有序数组的二分查找
有序符号表API的数据结构是一对平行的数组，一个存储键和一个存储值。
下面给出二分查找（基于有序数组）。
public class BinarySearchST<Key extends Comparable<Key>, Value>
{
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int capacity)
{ // See Algorithm 1.1 for standard array-resizing code.
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}
public int size()
{ return N; }
public Value get(Key key)
{
if (isEmpty()) return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) return vals[i];
else return null;
}
public 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;
}
public void put(Key key, Value val)
{ // Search for key. Update value if found; grow table if new.
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0)
{ vals[i] = val; return; }
for (int j = N; j > i; j--)
{ keys[j] = keys[j-1]; vals[j] = vals[j-1]; }
keys[i] = key; vals[i] = val;
N++;
}
public void delete(Key key)
// See Exercise 3.1.16 for this method.
//基于二分查找的有序符号表的其他操作
public Key min()
{ return keys[0]; }
public Key max()
{ return keys[N-1]; }
public Key select(int k)
{ return keys[k]; }
public Key ceiling(Key key)
{
int i = rank(key);
return keys[i];
}
public Key floor(Key key)
// See Exercise 3.1.17.
public Key delete(Key key)
// See Exercise 3.1.16.
public Iterable<Key> keys(Key lo, Key hi)
{
Queue<Key> q = new Queue<Key>();
for (int i = rank(lo); i < rank(hi); i++)
q.enqueue(keys[i]);
if (contains(hi))
q.enqueue(keys[rank(hi)]);
return q;
}
}
//其中，rank()算法的递归实现为：
public 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;
}
有序数组的符号表索引轨迹：
命题B1：在N个键的有序数组中，进行二分查找最多需要进行lgN+1次比较。
命题B2：向大小为N的有序数组中插入一个新的元素在最坏的情况下需要访问~2N次数组，因此向一个空符号表中插入N个元素最坏需要访问~N2次数组。
6 预览
接下来学习6种符号表。
