符号表

顺序查找（基于无序链表）

非常低效，见p238图3.1.3

public class SequentialSearchST<Key, Value>
{
    private Node first; // 链表首节点
    private class 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)
    { // 查找给定的键，返回关联的值
        for (Node x = first; x != null; x = x.next) 
            if (key.equals(x.key))
                return x.val; // 命中
        return null // 未命中
    }
    public void put(Key key, Value val)
    { // 查找给定的键，找到则更新其值，否则在表中新建结点
        for (Node x = first; x != null; x = x.next) 
            if (key.equals(x.key)) {
                x.val = val;
                return;
            }
        first = new Node(key, val, first); // 未命中,新建结点
    }
}

有序数组中的二分查找

public class BinarySearchST<Key extends Comparable<Key>, Value> // 有序符号表api实现
{
    private Key[] keys;
    private Value[] vals;
    private int N;
    public BinarySearchST(int capacity)
    {
        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.compateTo(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)
    { // 查找键，找到则更新值，否则创建新的元素
        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)
    {
        // TODO
    }
}

更高效的查找

为了将二分查找的效率和链表的灵活性结合起来，我们需要更加复杂的数据结构，二叉树查找

符号表的各种实现的优缺点