• 符号表
  • API
  • 有序符号表
  • 成本模型
• 无序链表中的顺序查找
  • 实现
  • 性能
• 有序数组中的二分查找
  • 实现
  • 性能

现代计算机和网络使人们能够访问海量的信息，而且各种计算设备正在源源不断地生成新的信息，高效检索这些信息的能力就成了处理它们的重要前提。接下来学习几种经典的查找算法。

符号表

符号表指的是一张用于存储信息的抽象的表格，主要目的就是将一个键和一个值联系起来，可以将一个键值对插入到符号表，也可以从符号表的所有键值对中按照键直接找到对应的值，符号表也被称为字典。

API

符号表最基本的操作是：插入、查找，此外还包括几种方便算法实现的操作。要实现符号表，首先要定义其背后的数据结构，并指明创建并操作这种数据结构以进行插入、查找所需的算法。
符号表的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<Key> keys()  //表中所有键的集合
}

设计的符号表将会遵循以下规则：符号表的实现使用了泛型；每个键只能对应一个值，如果向表中存入的键值对已经在表中存在，则用新的值覆盖旧值，所以表中不存在重复的键；也不允许存入空或空值，只有在表中找不到键对应的值时，get方法会返回null。

有序符号表

符号表根据其中键是否有序分为有序符号表和无序符号表，有序符号表中基于键的有序性可以实现更多有用的操作。

Key floor(Key key)  //获取小于等于key的最大键
Key ceiling(Key key)  //获取大于等于Key的最小键
int rank(Key key) //获取小于Key的键的数量
Key select(int k)  //获取排名为k的键
Key max()  //获取最大的键
Key min()  //获取最小的键

获取最大、最小键的操作使得有序符号表具有了与优先队列类似的功能，不同的是优先队列中可以存在重复的键但符号表不行。
rank和select方法可以用来检验一个新的键是否插入到合适的位置。对于0到size()-1中的所有i都有i=rank(select(i))，且key=select(rank(key))。floor和ceiling类似于对实数的向下取整、向上取整操作。

成本模型

符号表中插入、查找都需要将一个值与符号表中的键进行比较，在学习符号表的实现时，会统计比较的次数来分析一种实现的成本，如果一种实现的比较次数很少，便考虑其访问数据结构的次数。

无序链表中的顺序查找

可以使用链表作为符号表的简单实现，每个结点存储一个键值对。get()方法会遍历链表，将要查找的键依次与链表中的结点比较，匹配成功就返回结点的值，否则返回null；put()方法也会遍历链表，如果找到匹配的结点，就用要插入的值覆盖匹配结点的值，否则就在链表头部添加一个新的结点。

实现

public class SequentialSearchST<Key, Value> {
    private Node first;
    private int n;

    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) {
        if (key == null)
            throw new IllegalArgumentException("argument to get() is null");
        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 value) {
        if (key == null)
            throw new IllegalArgumentException("first argument to put() is null");

        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                 x.val=value;
                 return;
            }
        }
        first = new Node(key, value, first);
        n++;
    }
    
    ...
}

性能

对于一个含有N个键值对的基于无序链表的符号表来说：
未命中的查找，需要N次比较，因为要遍历并比较链表中的所有键；
插入操作，如果待插入的元素没在符号表中，也需要N次比较；
对于命中的查找，最坏情况为N次比较，但平均情况下，命中的查找不需要这么多次比较。可以通过计算查找表中每个键的总次数，将其除以N来估算一次命中查找的平均比较次数，这种方法假设对符号表中每个键进行查找的可能性都相同，也称为随机命中。虽然实际应用中，不可能做到完全随机，但也基本吻合。
在随机命中模式下，查找的总次数=第一个键的比较次数+第二个键的比较次数+…+第N个键的比较次数=1+2+…+N=N*(N+1)/2;平均比较次数=(N+1)/2。相当于与一半的元素进行比较。
向空表中插入N个不同的键时，每次插入都需与已经插入的所有键比较，所以也需要1+2+…+N=N*(N+1)/2次比较。增长数量级为平方级别。

有序数组中的二分查找

基于有序数组的符号表，这里使用的数据结构是一对平行的数组，一个存储键，一个存储值；也可以用一个由键值对构成的数据来实现。

实现

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 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--) {
            keys[j] = keys[j - 1];
            vals[j] = vals[j - 1];
        }
        keys[i] = key;
        vals[i] = val;
        N++;
    }

    public int rank(Key key) {
        // return rankRecursion(key, 0, N - 1);
        return rankIteration(key, 0, N - 1);
    }

    public int rankRecursion(Key key, int lo, int hi) {
        // if (hi <= lo)
        if (hi < lo)
            return lo;
        int mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(keys[mid]);
        if (cmp < 0) {
            return rankRecursion(key, lo, mid - 1);
        } else if (cmp > 0) {
            return rankRecursion(key, mid + 1, hi);
        } else {
            return mid;
        }
    }

    public int rankIteration(Key key, int lo, int hi) {
        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 Iterable<Key> keys() {
        return keys(keys[0], keys[N - 1]);
    }

    public Iterable<Key> keys(Key lo, Key hi) {
        if (lo == null)
            throw new IllegalArgumentException("first argument to keys() is null");
        if (hi == null)
            throw new IllegalArgumentException("second argument to keys() is null");

        Queue<Key> queue = new Queue<Key>();
        if (lo.compareTo(hi) > 0)
            return queue;
        for (int i = rank(lo, false); i < rank(hi, false); i++)
            queue.enqueue(keys[i]);
        if (get(hi) != null)
            queue.enqueue(keys[rank(hi, false)]);
        return queue;
    }
}

这份实现的核心是rank方法，它返回表中小于给定键的键的数量。对于get方法，只要给定的键存在于表中，根据rank方法就可以知道去哪儿找到它；对于put方法，如果给定的键存在于表中，根据rank方法就可以知道去哪儿更新键对应的值，如果键不在表中，根据rank方法也可以知道应该将新的键值插入什么位置。插入的时候，会先将所有更大的键向后移动一格来腾出位置。

由于使用了有序数组，rank方法可以通过二分查找快速地找到键的位置。在查找时，先将被查找的键和子数组的中间键比较，如果被查找的键小于中间键，就在左子数组中继续查找，如果大于中间键，就在右子数组中继续查找，否则中间键就是被命中的键。
rankRecursion和rankIteration分别用递归和迭代实现了这种算法。put方法在插入键值对时，由于使用了rank方法拿到待插入键的排序位置，可以保证符号表一直是有序的。

性能

在N个键的有序数组中进行二分查找时，先找到1个中间元素，然后在剩下的(N-1)/2个元素中继续二分查找，由此可得比较次数的关系式：
C(N)<=C((N-1)/2)+1，其中1为与中间元素的1次比较；
于是C(N)<=C(N/2)+1;
而且有C(0)=0,C(1)=1;
假设N的个数刚好为2的幂，即N=2^n, n=LgN;
则：C(2^n)<=C(2(n-1))+1;
继续迭代直到n=0，可得：C(2^n)<=C(20)+n;
将N=2^n, n=LgN代入上式可得：
C(N)<=1+LgN。
即N的个数刚好为2的幂时，最多需要LgN+1次比较；
推广到一般的情况，可知查找的增长数量级为对数级别。
查找操作的性能在对数级别，是非常快的，但插入操作的性能如何呢？
在最坏的情况下，插入的位置在数组的最开头，所以插入前需要将所有的元素向后移动一格，键、值各一个数组，共需要2N次数组访问，插入前调用rank方法进行了LgN次比较，LgN相比2N较小可忽略，所以插入操作需要访问数组~2N次；
向一个空符号表中插入N个元素，在最坏的情况下，每次都要插入数组的开头，共需2N(N-1)/2，约为~N^2次数组访问，所以插入操作的增长数量级为线性的，构建一个有序符号表则需要平方级别的时间，线性、平方级别的算法无法用于解决大规模的问题。