符號表聽不懂烁落，但有個更簡單的名字——字典。主要目的就是將一個鍵和一個值聯(lián)系起來膜赃。我們通過查詢鍵來找到對應(yīng)的值挺邀。

符號表是一種存儲鍵值對的數(shù)據(jù)結(jié)構(gòu)，支持插入和查找操作财剖。

符號表中不允許重復(fù)的鍵悠夯，當重復(fù)的時候新值會代替舊值癌淮。

鍵不能空躺坟。

鏈表的形式實現(xiàn)符號表

平均成本（查找 N/2 插入N）

public class SequentialSearchST<Key,Value> {
    private Node first;
    private class Node{   //結(jié)點，存放鍵值對和下一個結(jié)點指針
        Key key;
        Value val;
        Node next;
    public Node(Key k,Value v,Node n) {
        key=k;
        val=v;
        this.next=n;
    }
  }
    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;    //倘若原先有重復(fù)的鍵則更新其值
            }
        }
        first=new Node(key, val, first);  //否則就新建一個結(jié)點
    }   
}

用數(shù)組實現(xiàn)有序序號表

平均成本（查找 lgN 插入N）

public class BinarySearchST<Key extends Comparable<Key>,Value> {
    private Key[]keys;
    private Value[]vals;
    private int N;
    public BinarySearchST(int a) {
        keys=(Key[])new Comparable[a];
        vals=(Value[])new Object[a];
    }
    public int size() {
        return N;
    }
    public boolean isEmpty() {
        return N==0;
    }
    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 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 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--) {          //序號i之后的元素往后移動一格
            keys[j]=keys[j-1];
            vals[j]=vals[j-1];
        }
        keys[i]=key;
        vals[i]=val;
        N++;
    }


    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) {     //返回key對應(yīng)的值
        int i=rank(key);
        return keys[i];
    }

}