查詢演算法之——符號表（引入篇）
符號表的主要目的是用來儲存鍵值對，也就是將一個鍵和一個值關聯起來，它的主要操作為插入和查詢。
這篇只是為下一篇文章作為拋磚引玉，為不熟悉符號表的朋友做了一個大體的介紹，在文章的結尾列出了符號表的基本操作，有一定了解的朋友可以跳的下一篇文章（二叉查詢樹）。
首先我們必須討論幾個基本問題，這在之後的思想中將會一直用到：
1、重複的鍵
符號表不允許出現重複的鍵，當向表中插入的鍵值對的鍵已經出現在標中，當前加入的鍵值對會覆蓋原有的鍵值對，也就是進行了更新。
2、空鍵或空值
鍵不能為空，這在java機制中會產生異常。我們還規定，值也不能為空。（get（）方法能通過查詢鍵返回其關聯的值，當鍵不存在時get（）方法會返回null）
這個規定有兩個作用：
第一、我們能判斷一個鍵值對是否存在符號表中。
第二、我們可以將null作為put（）的第二個引數來實現刪除操作，
3、刪除操作
刪除操作的實現有兩種思路：即時刪除和延時刪除，延時刪除就是上面提到的，先將其值置位為空，然後在某個時刻刪除所有值為空的鍵。即時刪除也就是立即從表中刪除指定的鍵。（本文中將使用即時刪除）
4、鍵的等價性
鍵可以是任意型別（我們將其設定為泛型），可以是integer，double和string等等，java已經為他們實現了equals（）方法來判斷相等，如果是自定義的鍵，則需要重寫equals（）方法。
下面我們進入正題：
一、無序連結串列中的順序查詢
顧名思義，無序連結串列就是通常意義上的連結串列，只是連結串列的節點被定義為了鍵值對的形式，無序連結串列每次插入操作會在頭部插入一個新節點，而查詢操作是從連結串列的頭部開始一個個地遍歷符號表並使用equals（）方法來進行匹配。這種方法的效率是非常低的（它的查詢操作是線性級別的），查詢第一個鍵需要1次比較，第二個鍵需要2次比較...因此平均比較次數為（1+2+...+n）/n =(n+1)/2~n/2。它無法適用於大型符號表。
1 public class SequentialSearchST<Key, Value> {// 基於無序連結串列
2private int n;// number of key-value pairs
3private Node first;
4
5private class Node {// 連結串列節點的定義
6Key key;
7Value val;
8Node next;
9
10public Node(Key key, Value val, Node next) {
11this.key = key;
12this.val = val;
13this.next = next;
14}
15}
16
17public Value get(Key key) {// 查詢給定的鍵，返回關聯的值
18for (Node x = first; x != null; x = x.next) {
19if (key.equals(x.key)) {
20return x.val;
21}
22}
23return null;
24}
25
26public void put(Key key, Value val) {// 查詢給定的鍵，找到就更新其值，沒找到將其插入最前
27// **********************
28if (key == null) {
29throw new IllegalArgumentException("first argument to put() is null");
30}
31if (val == null) {
32delete(key);
33return;
34}
35// *********************防禦性程式碼，這保證了任何鍵的值都不為空
36for (Node x = first; x != null; x = x.next) {
37if (key.equals(x.key)) {
38x.val = val;
39return;
40}
41}
42first = new Node(key, val, first);// 插入最前
43n++;
44}
45 }
二、有序陣列中的二分查詢
如果能用上二分查詢的思想，我們就能把查詢的效率提升到對數級別（當然前提是陣列有序）
這時插入和查詢演算法都發生了改變，為了讓陣列前提有序，插入時我們會用rank（）方法來確定鍵的位置，再將此位置後的鍵後移一位，最後插入鍵。rank（）返回的是鍵在符號表中排名。在這裡如果鍵存在rank（）將返回鍵在有序陣列中的下標。
在這裡我們用兩個陣列分別儲存鍵值對的鍵和值，同一鍵值對在陣列中的下標是一樣的。
1 public class BinarySearchST<Key extends Comparable<Key>, Value> {// 有序查詢表（基於有序陣列）
2private Key[] keys;
3private Value[] vals;
4private int n = 0;// 用於記錄符號表中鍵值對的個數
5
6public BinarySearchST(int capacity) {// 動態調整大小
7keys = (Key[]) new Comparable[capacity];
8vals = (Value[]) new Object[capacity];
9}
10
11public boolean contains(Key key) {
12if (key == null) {
13throw new IllegalArgumentException("argument to contains is null");
14}
15return get(key) != null;
16}
17
18public int size() {
19return n;
20}
21
22public int size(Key lo, Key hi) {
23if (lo == null) {
24throw new IllegalArgumentException("first argument to size() is null");
25}
26if (hi == null) {
27throw new IllegalArgumentException("second argument to size() is null");
28}
29if (lo.compareTo(hi) > 0) {
30return 0;
31}
32if (contains(hi)) {
33return rank(hi) - rank(lo) + 1;
34} else {
35return rank(hi) - rank(lo);
36}
37}
38
39public Key min() {
40if (isEmpty()) {
41throw new NoSuchElementException("called min with empty symbol table");
42}
43return keys[0];
44}
45
46public Key max() {
47if (isEmpty()) {
48throw new NoSuchElementException("called max with empty symbol table");
49}
50return keys[n - 1];
51}
52
53public Value get(Key key) {
54if (key == null) {
55throw new IllegalArgumentException("argument to get is null");
56}
57if (isEmpty()) {
58return null;
59}
60int i = rank(key);
61if (i < n && keys[i].compareTo(key) == 0) {
62return vals[i];
63}
64return null;
65}
66
67private int rank(Key key) {// 基於有序陣列的二分查詢（迭代）
68if (key == null) {
69throw new IllegalArgumentException("argument to rank is null");
70}
71int lo = 0, hi = n - 1;
72while (lo <= hi) {
73int mid = lo + (hi - lo) / 2;
74int cmp = key.compareTo(keys[mid]);
75if (cmp > 0) {
76lo = mid + 1;
77} else if (cmp < 0) {
78hi = mid - 1;
79} else {
80return mid;
81}
82}
83return lo;// 找不到的情況
84}
85
86public Iterable<Key> keys() {
87return keys(min(), max());
88}
89
90private Iterable<Key> keys(Key lo, Key hi) {
91if (lo == null) {
92throw new IllegalArgumentException("first argument to keys() is null");
93}
94if (hi == null) {
95throw new IllegalArgumentException("second argument to keys() is null");
96}
97Queue<Key> queue = new Queue<Key>();
98if (lo.compareTo(hi) > 0) {
99return queue;
100}
101for (int i = rank(lo); i < rank(hi); i++) {
102queue.enqueue(keys[i]);
103}
104if (contains(hi)) {
105queue.enqueue(keys[rank(hi)]);
106//queue.enqueue(hi);
107}
108return queue;
109}
110
111private boolean isEmpty() {
112// TODO Auto-generated method stub
113return n == 0;
114}
115
116public void put(Key key, Value val) {
117if (key == null) {
118throw new IllegalArgumentException("first argument to put is null");
119}
120if (val == null) {
121delete(key);
122return;
123}
124int i = rank(key);
125if (i < n && key.compareTo(keys[i]) == 0) {//已有元素進行更新
126vals[i] = val;
127return;
128}
129for (int j = n; j > i; j--){//鍵值對後移
130keys[j] = keys[j-1];
131vals[j] = vals[j-1];
132}
133keys[i] = key;
134vals[i] = val;
135n++;
136}
137
138public void delete(Key key) {
139if (key == null) {// 避免空指標錯誤
140throw new IllegalArgumentException("argument to delete is null");
141}
142if (isEmpty()) {
143return;
144}
145int i = rank(key);
146if (i == n || key.compareTo(keys[i]) != 0) {
147return;
148}
149for (int j = i; j < n - 1; j++) {//元素前移
150keys[j] = keys[j + 1];
151vals[j] = vals[j + 1];
152}
153n--;
154keys[n] = null;
155vals[n] = null;
156}
157 }
我們預設使用的二分查詢是迭代進行，下面給出遞迴的形式：
1public int rank(Key key,int lo,int hi) {
2if(hi<lo) {
3return lo;
4}
5int mid=lo+(hi-lo)/2;
6int cmp=key.compareTo(keys[mid]);
7if(cmp<0) {
8return rank(key,lo,mid-1);
9}elseif(cmp>0) {
10return rank(key,mid+1,hi);
11}else {
12return mid;
13}
14}
如果理解了迭代的形式，就能很容易改寫出遞迴了。
用物件的陣列代替兩個平行陣列（求指點）：
定義一個以鍵和值為屬性的物件，用物件陣列來代替兩個平行陣列，由於本人學術不精，未能完成，主要問題是不知如何建立不同型別屬性的泛型陣列（key繼承了comparable而value繼承了object）。在此提出問題，希望高人指點！
1 public class BSST<Key extends Comparable<Key>, Value> {
2class Item{//內部類
3Key key;
4Value val;
5}
6private Item[] item;
7private int n = 0;
8public BSST(int capacity) {// 動態調整大小
9item = (Item[]) new Object[capacity];//出現型別轉換錯誤
10 //item = (Item[]) new Comparable[capacity];//出現型別轉換錯誤
11
12}
13 }
四、符號表的基本操作
符號表的基本操作遠遠不止本文提到的rank（）、put（）、get（）、delete()。下面將他們列出來，瞭解個大概，在下一篇文章中將會一一實現他們。
boolean contains(Key key):判斷key是否存在於符號表中
int size(Key lo,Key hi)：返回lo到hi之間的鍵值對數量
Key min()：返回最小鍵
Key max()：返回最大鍵
Key floor(Key key)：返回小於等於key的最大鍵
Key ceiling(Key key)：返回大於等於key的最小鍵
Key select(int k)：返回排名為k的鍵
Iterable<Key> keys(Key lo,Key hi)：返回一個佇列，包含lo-hi之間的所有鍵（已排序）
rank(select(k))==k ture
select(rank(key))==key ture