大量、高效地检索信息是现代计算机和网络的一大特点，这些检索操作大都是由各种查找算法实现的，如果没有高效的查找算法，现代计算机更高级的功能也就无从谈起。
对于经典查找算法，我们需要建立一种新的抽象：符号表（或被称为字典），并且用三种数据类型来实现它：二叉查找树、红黑树和散列表。
符号表
一个基本的符号表包括键（Key）和对应的值（Value）。对于符号表来说，如果把符号表看作一个个小黑屋，“键”就好像是一个通往对应的“值”的窗口，检索、删除、查找等操作都是通过键来完成。一种简单的符号表API如下：
规则：
- 符号表不允许重复的键，但可以用不同的键来存储同一个值
- 键和值都不能为空
- 当值为空时，认为该键值对已删除，因此可以用
get(key) != null来判定一个键是否有对应的值；并且将一个键对应的值设为空也是删除该键值对的方法 - 符号表通常是对键可迭代的，这也方便用例处理表中的所有键值
- 键通常是Comparable的对象
这类符号表通常有如下特性：
- 混合使用查找和插入的操作
- 大量的不同键
- 查找操作比插入操作多得多
- 虽然不可预测，但查找和插入操作的使用模式并非随机
无序链表的顺序查找
put(): 遍历链表，用equals()方法比较需被查找的键和每个结点中的键，若匹配成功则用第二个参数更新和该键相关的值，否则用给定的键值对创建一个新的结点并将其插入到符号表的开头；get(): 遍历链表，用equals()方法比较被查找的键和结点中的键，找到则返回对应值，若没有找到或对应值为null则返回null；delete(): 遍历链表，用equals()方法比较被查找的键和结点中的键（实际上应查找该结点的下一个结点的键），找到则将该结点的next指针指向下下个结点；如果目标结点是链表的第一个结点，则直接将链表的第一个结点的指针指向第二个结点；否则不进行操作keys(): 遍历整个链表，将所有的键存储到可迭代对象中。
public class SequencialSearch<Key extends Comparable<Key>, Value> {
private Node first;
private int size;
private class Node {
Key key;
Value val;
Node next;
private Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
public SequencialSearch() {
first = new Node(null, null, null);
}
public void put(Key key, Value val) {
// 保护，防止val为null
if (val == null) delete(key);
Node temp = first;
for (int i = 0; i < size; i++) {
if (temp.key.equals(key)) {
temp.val = val;
return;
}
temp = temp.next;
}
Node oldFirst = first;
first = new Node(key, val, oldFirst);
size++;
}
public Value get(Key key) {
Node temp = first;
for (int i = 0; i < size; i++) {
if (temp.key.equals(key)) {
return temp.val;
}
temp = temp.next;
}
return null;
}
public boolean contains(Key key) {
return get(key) != null;
}
public void delete(Key key) {
Node temp = first;
if (temp.key.equals(key)) {
first = first.next;
size--;
return;
}
for (int i = 0; i < size - 1; i++) {
if (temp.next.key.equals(key)) {
temp.next = temp.next.next;
size--;
return;
}
temp = temp.next;
}
}
public Iterable<Key> keys() {
Node temp = first;
Key[] keys = (Key[]) new Object[size];
for (int i = 0; i < size; i++) {
keys[i] = temp.key;
temp = temp.next;
}
return List.of(keys);
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
}
有序数组的二分查找
增加辅助方法rank()，它返回表中小于给定的键的数量；
修改put()方法，每一次put()操作都要保证符号表有序，通过rank()找到要更改的键的位置并进行增改；
因为我们这次得到的数组是有序的，我们也可以很容易地使用rank()来改进相关的delete()和get()方法
public class BinaryFind<Key extends Comparable<Key>, Value> {
private Key[] keys;
private Value[] vals;
private int size;
public BinaryFind(int capacity) {
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}
public int size() {
return size;
}
public Value get(Key key) {
if (isEmpty()) return null;
int i = rank(key);
if (i < size && keys[i].compareTo(key) == 0) return vals[i];
else return null;
}
public boolean isEmpty() {
return size == 0;
}
public int rank(Key key) {
int lo = 0, hi = size - 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 < size && keys[i].compareTo(key) == 0) {
vals[i] = val;
return;
}
for (int j = size; j > i; j--) {
keys[j] = keys[j - 1];
vals[j] = vals[j - 1];
}
keys[i] = key;
vals[i] = val;
size++;
}
public void delete(Key key) {
if (!contains(key) || isEmpty()) return;
int i = rank(key);
for (int j = --size; j > i; j--) {
keys[j - 1] = keys[j];
vals[j - 1] = vals[j];
}
}
public Key ceiling(Key key) {
int i = rank(key);
return keys[i];
}
public Key floor(Key key) {
int i = rank(key);
if (i < size && key.compareTo(keys[i]) == 0) return keys[i];
else return keys[i - 1];
}
public Key min() {
return keys[0];
}
public Key max() {
return keys[size - 1];
}
public Key select(int k) {
return keys[k];
}
public boolean contains(Key key) {
return get(key) != null;
}
public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> q = new Queue<Key>();
for (int i = rank(lo); i < rank(hi); i++)
q.enqueue(keys[i]);
if (contains(hi))
q.enqueue(keys[rank(hi)]);
return q;
}
}
注：由于二分查找的高效来自于能够快速通过索引取得任何子数组的中间元素，因此单链接的链表无法使用二分查找法，我们需要更复杂的链式结构来将二分查找的效率和链表的灵活性结合起来，这也就是二叉查找树（参看我的下一篇博客）的动机。