符号表 | Wafer's Note

1. 符号表

符号表是一个储存键值对的表，同时还有插入和删除的功能。

1.1 符号表的设计

符号表不允许重复的键
键值对是唯一的，一个键只对应一个值
符号表不允许空键和空值
这是因为空键会导致 Runtime Exception
不允许空值可以让我们通过更少的 API 来实现更多的类似插入删除的操作
我们可以通过 get() 来测试一个键是否是空键
通过 put() 的空值来删除这个键
只通过 compareTo() 方法来去判断两个键的相等性
如果我们混合使用 equal() 和 compareTo() 方法，那么这将会导致很多不必要的浪费
为了避免这种使用不同方法所造成的浪费，我们决定只使用 compareTo() 来去判断相等性

1.2 API

这里展现了我们应该使用在符号表的 API ，这些 API 主要对键值对进行操作；
之后的内容将基于这里给出的 API 来进行。

1.2.1 关键的 API

最为关键的符号表 API 是 put() 和 get()

/**
* Put the key and value pair into the symbols table.
* @parma key The key you want to insert, when it is null, delete the key from table.
* @parma value The value you want to insert
*/
void put(Key key, Value value)

/**
* Get the value of the specfic key in the table.
* @parma key The key you specify
* @return The value of the specific key, if the value doesn't exist, return null
*/
Value get(Key key)

1.2.2 在有序符号表中的其他方法

这些 API 是应用于有序符号表的
这里只展示了一些关键方法，还有一些冗余方法用于更方便的操作，这里不予展示

API 包括：

min() 和 max()
floor() 和 ceiling()
rank() 和 select()
keys()

这里只展示了 rank(), select() 和 keys() 方法，其他的方法比较简单，而且其作用也很容易通过名字进行推断。
所以在这里不予显示

// Rank & Select
/**
* Get the number of the keys which are less than the specific one. Also called the RANK
* @parma Key key The specific key
* @return The number of keys in the table which are less than the specific one.
*/
int rank(Key key)

/**
* Get the key which is rank k
* @parma int k The rank of the key
* @return The specific key
*/
Key select(int k)

// keys()

/**
* Get the all keys inside the table.
* @return An Iterable Set of keys, such as List or Queue
*/
Iterable<Key> keys()

/**
* Get the set of the range of [lo..hi]
* @parma Key lo The low range of the keys.
* @parma Key hi The high range of the keys.
* @return The Iterable Set of the keys.
*/
Iterable<Key> keys(Key lo, Key hi)

2. 在无序表中的顺序查找

当我们实现一个符号表的时候，我们通常使用链表的形式来实现；

使用这样的一个数据结构时，我们只能以顺序的形式进行搜索，仅仅通过在单链接链表中遍历所有的节点

2.1 实现

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

    private class Node {
        // The linked List 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) {
        // get the specific key, return the corrsponding value
        for(Node x = first; x != null; x = x.next) {
            if(key.equals(x.key)) {
                return x.val;   // hit
            }
        }
        return null;    // Not hit
    }

    public void put(Key key, Value value) {
        for(Node x = first; x != null; x = x.next) {
            if(key.equals(x.key)) {
                x.val = val;
                return;     // hit
            }
        }
        // Not hit, create new node
        // Add  at the beginning
        first = new Node(key, val, first);

    }
}

2.2 性能

在一个具有 $N$ 个节点的符号表中，使用顺序查找方法，在最坏情况下，需要 $N$ 次的比较。

特别的是，插入 $N$ 个节点，需要 $\sim N^2/2$ 次的比较

2.3 结论

我们可以看到，使用链表实现符号表时，它需要使用顺序查找方法，这样子使得查找的效率变得很低下；

这样子的实现方式，并不能满足我们现今对大数据处理的需求。

3. 在有序符号表中的二分查找

为了实现更快的查找性能，我们需要转用数组来实现符号表；

对于一个有序符号表来说，我们可以使用二分查找的方法来进行搜索；
后面会看到，使用二分查找将会大大提高我们的搜索效率

3.1 实现

我们使用两个平行的数组来分别储存键和值；

然后我们使用 rank() 方法来帮助我们找到一个特定的键值对

/**
* These method all base on the rank() method
* Which return the number of the keys which are less than the spcific one
* Or the right position of the specific key
*/

public Value get(Key key) {
    if (isEmpty()) return null;
    int i = rank(key);
    if (i< N && keys[i].compareTo(key) == 0) {
        return vals[i];     // hit
    }
    else {
        return null;    // Not hit
    }
}

public void put(Key key, Value value) {
    // The specific position of the key
    int i = rank(key);
    if (i < N && keys[i].compareTo(key) == 0) {
        // Update: 2017-02-12
        vals[i] = val; return;
    }
    // Not hit, create new key-value pair
    for (int j = N; j > i; j--) {
        // MOVE THE DATA FORWARD
        keys[j] = keys[j - 1];
        vals[j] = vals[j - 1];
    }
    keys[i] = key;
    vals[i] = val;
    N++;
}

对于 rank() 方法的一些需要注意的点：
这个方法的返回值是小于这个键的所有键的个数
换句话来说就是这个键在数组中的排名，也就是它的位置
重要的是，由于 get() 和 put() 方法也使用了

/**
* Using the Binary Searching method, due to the ordered talbe.
*/
public int rank(Key key) {
    // Notice that, the lo, hi, mid is the
    // POSITION of the array
    int lo = 0, hi = N - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // Use this format to avoid the overflow
        int cmp = key.compareTo(keys[mid]);
        if (cmp < 0) {
            hi = mid - 1;
        }
        else if(cmp > 0 ) {
            lo = mid + 1;
        }
        else {
            return mid;
        }
    }
    return lo;
}

二分查找是很简单的，通过在一个有序的序列中比较中间位置的数据元素，从而逐步缩减查找范围，达到减少比较次数的作用。

需要注意的是：

使用 mid = lo + (hi - lo) / 2; 来避免溢出
为了理解这点，你需要明白，lo, hi 和 mid 只是键值的位置，而不是键值的值。
我们只需要获取中间元素的位置，如果一个数组的元素总数很大，那么使用 hi + lo 就会导致溢出，使得 mid 的结果甚至都不在 [lo...hi] 之间。
为了防止溢出，或者说为了保证 mid 的结果落在 [lo...hi] 之间，那么我们就需要使用另一种计算方式；
即，通过步长的方式来获取中间位置，通过使用 lo + 步长 的方式，可以有效的避免溢出的出现。
所以，我们使用 mid = lo + (hi - lo) / 2 来获取中间位置。
当数据元素小于 5 时，使用顺序查找来降低出错率
顺序查找比二分查找更不容易出错。
当数据元素小于 5 的时候，顺序查找和二分查找并没有什么大的性能差异，此时使用顺序查找来降低出错率是可以接受的。

3.2 性能

在一个 $N$ 个键值的符号表中，使用二分查找，需要不超过 $lgN + 1$ 次的比较

但是在同时需要插入和删除的操作的时候，二分查找的效率还是远远不能满足我们的需求

如果你需要在一个 $N$ 个元素个数组中插入一个元素，你需要 $\sim 2N$ 次的数组访问；

而且如果你需要插入 $N$ 个元素到一个空表里，你需要 $\sim N^2$ 次的数组访问。

3.3 结论

在有序符号表中使用二分查找，可以将时间复杂度减少到 $logN$ 级别。

对于一个静态的符号表（即不允许插入和删除元素的表），在查找之前将其进行排序是值得的；

但是这种形式的查找还是不能满足我们对于快速的查找的同时支持快速的插入和删除操作。