理论建构

散列表

通过红黑二叉查找树的实现，我们已经让查找算法足够高效，对于一个庞大的数据集，平衡二叉树和红黑树对于查找的时间复杂度已经达到了 $O(lgN)$ ；但是有没有一种更高效的查找算法，让时间复杂度降低到常数级别呢？答案是肯定的，试想一下，假如我们可以直接将想要查找的键作为符号表的索引，那么我们每次的查找都只需要在存放这种索引的符号表中直接对该索引保存的键值对进行引用就好了，这样每次查找的时间就可以压缩到接近常数级别。因此，我们需要一个函数，这个函数需要足够高效，可以通过简单的计算，将输入的键映射到数组的某一个索引中。该函数我们称之为散列函数。

散列函数

假设我们有一个大小为M的数组，那么我们需要的散列函数需要满足下列特性：

  1. 均匀性：该散列函数能够均匀并独立地将所有键映射到 0 ~ (M-1)之间
  2. 高效性：计算简便
  3. 一致性：等价的键需要映射到同一个数

具体实现上，我们既可以通过自己设计，使我们的散列函数满足上面的三个特性；也可以通过java对于固有数据类型提供的hashcode()方法得到对应的hash值，并利用该hash直接对键进行均匀散列。

当然，对于自定义的数据类型，以上第二种方法无法直接使用，需要对hashcode() 方法进行设计，返回一个合理的hash值。

\\ 自定义散列函数，以String为例
private static final int R = 2; // 二进制
private static int M = 31; // 散列值分布在（0, M-1）之间

public static int stringHash(String s) {
    int hash = 0;
    for (int i = 0; i < s.length(); i++)
        hash = (R * hash + s.charAt(i)) % M;
    return hash;
}

\\ 利用hashcode()方法
private int M = 31;
private int hash(Key key) {
    return (key.hashCode() & 0x7fffffff) % M; // 保证散列值的非负性
}

碰撞处理

实际对散列值计算的过程中，我们无法保证每个不同的键得到的散列值都是唯一的，因此，必须要将同一个散列值中不同的键区分开来，即需要进行碰撞处理。

基本上碰撞处理有两种处理思路，即分别使用数组和链表的方法。使用链表的方法被称为拉链法，使用数组的方法称为先行探测法。

拉链法

使用拉链法进行碰撞处理，简单来说，就是将每个散列值对应的多个键值对储存成SequentialSearchST() 链表，这样我们在对同一散列值内部进行查找时就可以用SequentialSearchST() 的内部方法，具体实现如下：

private int M;
private int N; // 键值对总数
private SequentialSearchST<Key, Value>[] st;

public SanlieSearch() {
    this(997);
}

public SanlieSearch(int M) {
    this.M = M;
    st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
    for (int i = 0; i < M; i++) {
        st[i] = new SequentialSearchST();
    }
}

public int hash(Key x) {
    return (x.hashCode() & 0x7fffffff) % M; 
}

public Value get(Key key) {
    return (Value) st[hash(key)].get(key);
}

public void put(Key key, Value val) 
 st[hash(key)].put(key, val);
    N++;
}

public Value delete(Key key) {
    Value val = get(key);
    st[hash(key)].delete(key);
    return val;
}

虽然这种方法在每个散列值对应的链表中只是采用顺序查找，但是由于总的键值对已经被均匀散布在散列表中，每个链表并不长，查找的时间成本很低。假如散列表大小为M，储存N个键值对，那么平均查找次数为N/M；当M很大（与N相比为常数关系），那么算法的时间复杂度就接近一个常数。

先行探测法

考虑到通过散列函数计算之后，得到的散列表并非每一个索引都被填充了键值对，因此我们可以利用这些空置的索引，将那些散列值重复（即数组中对应索引已被占用）的键值对填充到那些没有被填充的数组空间中。

在这种情况下，我们需要创建两个散列表，分别储存键和值。储存时需要根据数组填充情况扩大数组的大小，并根据散列值（索引）对应储存的键分为以下三种情况：

  1. 储存的键为null，插入新的键值对
  2. 储存的键与该键相等，替换值
  3. 储存的键与该键不等，像右移动索引（遇到边界返回到0索引），值到发现索引对应储存的键为null；
private int M = 16;
private int N;
private Key[] keys;
private Value[] vals;

public SanlieSearch() {
    keys = (Key[]) new Object[M];
    vals = (Value[]) new Object[M];
}

public SanlieSearch(int cap) {
    keys = (Key[]) new Object[cap];
    vals = (Value[]) new Object[cap];
}

private int hash(Key key) {
    return (key.hashCode() & 0x7fffffff) % M;
}

private void resize(int cap) {
    SanlieSearch<Key, Value> t;
    t = new SanlieSearch<Key, Value>(cap);
    for (int i = 0; i < M; i++)
        if (keys[i] != null)
            t.put(keys[i], vals[i]);
    keys = t.keys;
    vals = t.vals;
    M = t.M;
}

public void put(Key key, Value val) {
    if (N >= M / 2) resize(2 * M);
    int i;
    for (i = hash(key); keys[i] != null; i = (i + 1) % M)
        if (keys[i].equals(key)) {
            vals[i] = val;
            return;
        }
    keys[i] = key;
    vals[i] = val;
    N++;
}

public Value get(Key key) {
    for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
        if (keys[i].equals(key))
            return vals[i];
    return null;
}

该算法的时间复杂度与扩充数组的时机有关，通常情况下，我们保证数组的利用率不超过1/2，那么查找的平均应在3/2到5/2之间，仍为常数量级。