《算法》（第4版）第3章读书笔记

我们使用符号表来描述一张抽象的表格，将信息存在其中，然后通过指定的键来查找信息。键和值的具体意义取决于不同的应用。符号表中可能保存很多信息和键，因此实现一张符号表也很难。

本章主要讲了使用三种经典的数据类型来实现高效的符号表

符号表的API

无序链表的顺序查找

符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对，如算法中的代码所示。get()的实现即为遍历链表，用equals()方法比较需被查找的键和每个结点中的键。如果匹配成功我们就返回相应的值，否则我们返回null。put()的实现也是遍历链表，用equals()方法比较需被查找的键和每个结点中的键。如果匹配成功我们就用第二个参数指定的值更新和该键相关联的值，否则我们就用给定的键值对创建一个新的结点并将其插入到链表的开头。这种方法也被称为顺序查找：在查找中我们一个一个地顺序遍历符号表中的所有键并使用equals()方法来寻找与被查找的键匹配的键。

具体代码

public class SequentialSearchST<Key, Value> {

    private int n;           

    private Node first;      // 链表首结点

    private class Node {

        private Key key;

        private Value val;

        private Node next;

        public Node(Key key, Value val, Node next)  {

            this.key  = key;

            this.val  = val;

            this.next = next;

        }

    }

    public SequentialSearchST() {

    }

    public int size() {

        return n;

    }

    public boolean isEmpty() {

        return size() == 0;

    }

    public boolean contains(Key key) {

        if (key == null) throw new IllegalArgumentException("argument to contains() is null");

        return get(key) != null;

    }

    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 val) {

        if (key == null) throw new IllegalArgumentException("first argument to put() is null");

        if (val == null) {

            delete(key);

            return;

        }

        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++;

    }

二分查找（迭代）

一般情况下二分查找都比顺序查找快得多，它也是众多实际应用程序的最佳选择。当然，二分查找也不适合很多应用。例如，它无法处理Leipzig Corpora数据库，因为查找和插入***作是混合进行的，而且符号表也太大了。如我们所强调的那样，现代应用需要同时能够支持高效的查找和插入两种***作的符号表实现。也就是说，我们需要在构造庞大的符号表的同时能够任意插入（也许还有删除）键值对，同时也要能够完成查找***作。

/**

 * 算法3.2 二分查找（基于有序数组）

 * Created by huazhou on 2015/11/29.

 */

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 int size(){

        return N;

    }

    public boolean isEmpty() {

        return size() == 0;

    }

    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      (cmp < 0) hi = mid - 1;

            else if (cmp > 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){

        if (isEmpty()) return;

        // compute rank

        int i = rank(key);

        // key not in table

        if (i == N || keys[i].compareTo(key) != 0) {

            return;

        }

        for (int j = i; j < N-1; j++)  {

            keys[j] = keys[j+1];

            vals[j] = vals[j+1];

        }

        N--;

        keys[N] = null;  // to avoid loitering

        vals[N] = null;

        // resize if 1/4 full

        if (N > 0 && N == keys.length/4) resize(keys.length/2);

    }

}

基于二叉树的查找符号表

/**

 * 算法3.3 基于二叉查找树的符号表

 * Created by huazhou on 2015/12/1.

 */

public class BST<Key extends Comparator<Key>, Value> {

    private Node root;  //二叉查找树的根结点

    private class Node{

        private Key key;    //键

        private Value val;  //值

        private Node left, right;   //指向子树的链接

        private int N;  //以该结点为根的子树中的结点总数

        public Node(Key key, Value val, int N){

            this.key = key;

            this.val = val;

            this.N = N;

        }

    }

    public int size(){

        return size(root);

    }

    private int size(Node x){

        if(x == null){

            return 0;

        }

        else{

            return x.N;

        }

    }

}

二叉查找树分析

查找树的运行时间取决于树的形状，树的形状取决于键被插入的先后顺序，一棵含有N个节点的树是完全平衡的，最坏情况是搜索路径上有n个节点

哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

使用哈希查找有两个步骤:

使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突

处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈