算法—7.無序鏈表中的順序查找，算法無序

算法—7.無序鏈表中的順序查找，算法無序

1.基本思想

符號表中使用的數據結構的一個簡單選擇是鏈表，每個結點存儲一個鍵值對，如算法中的代碼所示。get()的實現即為遍歷鏈表，用equals()方法比較需被查找的鍵和每個結點中的鍵。如果匹配成功我們就返回相應的值，否則我們返回null。put()的實現也是遍歷鏈表，用equals()方法比較需被查找的鍵和每個結點中的鍵。如果匹配成功我們就用第二個參數指定的值更新和該鍵相關聯的值，否則我們就用給定的鍵值對創建一個新的結點並將其插入到鏈表的開頭。這種方法也被稱為順序查找：在查找中我們一個一個地順序遍歷符號表中的所有鍵並使用equals()方法來尋找與被查找的鍵匹配的鍵。

2.具體算法

/**
 * 算法3.1 順序查找（基於無序鏈表）
 * Created by huazhou on 2015/11/11.
 */
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);  //未命中，新建結點
    }
}

符號表的實現使用了一個私有內部Node類來在鏈表中保存鍵和值。get()的實現會順序地搜索鏈表查找給定的鍵（找到則返回相關聯的值）。put()的實現也會順序地搜索鏈表查找給定的鍵，如果找到則更新相關聯的值，否則它會用給定的鍵值對創建一個新的結點並將其插入到鏈表的開頭。

3.算法分析

命題：在含有N對鍵值的基於（無序）鏈表的符號表中，未命中的查找和插入操作都需要N次比較。命中的查找在最壞情況下需要N次比較。特別地，向一個空表中插入N個不同的鍵需要~N²/2次比較。

證明：在表中查找一個不存在的鍵時，我們會將表中的每個鍵和給定的鍵比較。因為不允許出現重復的鍵，每次插入操作之前我們都需要這樣查找一遍。

推論：向一個空表中插入N個不同的鍵需要~N²/2次比較。

4.總結

查找一個已經存在的鍵並不需要線性級別的時間。一種度量方法是查找表中的每個鍵，並將總時間除以N。在查找表中的每個鍵的可能性都相同的情況下時，這個結果就是一次查找平均所需的比較數。我們將它稱為隨機命中。盡管符號表用例的查找模式不太可能是隨機的，這個模型也總能適應得很好。我們很容易就可以得到隨機命中所需的平均比較次數為~N/2：算法中的get()方法查找第一個鍵需要1次比較，查找第二個鍵需要2次比較，如此這般，平均比較次數為(1+2+...+N)/N=(N+1)/2~N/2。

這些分析完全證明了基於鏈表的實現以及順序查找是非常低效的。

【源碼下載】