3.1 Elementary Symbol Tables

API

符号表的主要目的就是将一个键和一个值联系起来。
定义：符号表是一种存储键值对的数据结构，支持两种操作：

插入（put）,即将一组新的键值对插入表中；
查找（get），即根据给定的键得到相应的值。

规则：

每个键只对应一个值（表中不允许存在重复的键）
每当用例代码向表中存入新的键值对和表中已有的键（及关联的值）冲突时，新的值对代替旧的值。

键不能为空，不允许有空值。
删除操作：

延时删除： put(key ,null)
即时删除：立刻从表中删除指定的键

键的等价性:
Java的一条最佳实践就是维护所有Comparable类型中compareTo()方法和equals()方法的一致性。也就是说，任何一种Comparable类型的两个值a和b都要保证(a.compareTo(b)==0)和a.equals(b)的返回值相等。

用例举例

简单的符号表测试用例：

public static void main(String[] args)
{
    ST<String,Integer> st
    st = new ST<String,Integer>();
    for(int i = 0;!StdIn.isEmpty();i++)
    {
        String key =  StdIn.readString();
        st.put(key,i);
    }
    for(String s : st.key())
        StdOut.println(s + " " + st.get(s));  
}

FrequencyCounter测试用例:

public class FrequencyCounter{
    public static void main(String[] args)
    {
        int minlen = Integer.parseInt(args[0]);//最小键长
        ST<String,Integer> st = new ST<String,Integer>();
        while(!StdIn.isEmpty())
        {
            String word = StdIn.readString();
            if(word.length() < minlen) continue;//忽略较短的单词
            if(!st.contains(word)) st.put(word,1);
            else   st.put(word,st.get(word) + 1);
        }
        String max = " ";
        st.put(max,0);
        for(String s : st.keys())
            if(st.get(word) > st.get(max))
                max = word;
        StdOut.println(max + " " + st.get(max));
    }
}

无序链表的顺序查找：

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

在含有N对键值的基于（无序）链表的符号表中未命中的查找和插入操作都需要N次比较。

有序数组中的二分查找：

public class BianrySearchST<Key extends Comparable<Key>,Value>
{
	private Key[] keys;
	private Value[] vals;
	private int N;
	public BianrySearchST(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(com < 0)       hi = mid - 1;
			else if(com > 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)
}

在N个键的有序数组中进行二分查找最多需要(lgN + 1)次比较(无论是否成功)。
Inserting a new key into an ordered array uses ~ 2N array accesses in the worst case, so inserting N keys into an initially empty table uses ~ N^2 array accesses in the worst case.

Exercise

Write a client program GPA.java that creates a symbol table mapping letter grades to numerical scores, as in the table below, then reads from standard input a list of letter grades and computes and prints the GPA (the average of the numerical scores of the corresponding grades).
```
A+    A     A-    B+    B     B-    C+    C     C-    D     F
4.33  4.00  3.67  3.33  3.00  2.67  2.33  2.00  1.67  1.00  0.00
```
Develop a symbol-table implementation ArrayST.java that uses an (unordered) array as the underlying data structure to implement our basic symbol table API

3.1 Elementary Symbol Tables

API

用例举例

Exercise

Creative Problems

Web Exercise