3.1　符号表

符号表是一种存储键值对的数据结构，支持两种操作：插入（put），即将一组新的键值对存入表中；查找 （get），即根据给定的键得到相应的值

3.1.1　API

public class ST <Key, Value>
ST()创建一张符号表
void put(Key key, Value val)将键值对存入表中（若值为空则将键 key 从表中删除）
Value get(Key key)获取键 key 对应的值（若键 key 不存在则返回 null）
void delete(Key key)从表中删去键 key （及其对应的值）
boolean contains(Key key)键 key 在表中是否有对应的值
boolean isEmpty()表是否为空
int size()表中的键值对数量
Iterable keys()表中的所有键的集合
void delete(Key key)put(key, null);
boolean contains(key key)return get(key) != null;
boolean isEmpty()return size() == 0;

3.1.4　无序链表中的顺序查找

适用于小型问题；对于大型符号表很慢

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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); // 未命中，新建结点
    }
}

3.1.5　有序数组中的二分查找

最优的查找效率和空间需求，能够进行有序性相关的操作；插入操作很慢

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class BinarySearchST<Key extends Comparable<Key>, Value>
{
    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.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)
    { // 查找键，找到则更新值，否则创建新的元素
        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++;
    }
}