什么散列

散列是提供对任何有名项提供存取操作和删除操作的列表。这种结构的目的是提供常数时间的基本操作。

举个例子：如果所有元素都是16-bits且不带正负号的整数，范围是0-65535。那么简单运用一个 array 就可以满足上面的期望。首先配置一个arrayA.，拥有65536个元素，初值全部为0，每个元素值代表相应元素出现的次数。如果插入元素i，就执行A[i]++，如果删除元素i，就执行A[i]--，如果搜素元素就检查A[i]是否为0。以上的每一个操作都是常数时间。这种解法的额外负担是array的空间和初始化时间。

绘图1.jpg

但是这种解法存在2个现实的问题：

• 如果元素很多，那么要准备的数组大小就很大，空间占用太大。
• 如果元素是其他的类型（非整型），那么就不能作为数组索引。

第一个问题：
我们是可以采用一个映射函数，将大数转换为小数，比如给定整数x，那么
x % array.size()，那么就会得到一个范围在 [ 0，array.size() - 1 ] 之间的数，也可以作为数组索引，但这会引入新的问题：如何解决碰撞冲突的问题。

第二个问题：
我们可以将一个非整数类型的转换为整型，比如字符串"string"，转换为ASCII编码。

线性探测

当用散列函数计算出元素的插入位置，而该位置已经不能使用时，最简单的办法就是循序往下一一寻找，直到找到一个可用的位置为止。
元素的删除则可以采用"惰性删除"，也就是标记删除记号，实际删除则待散列表重新整理时再进行。

线性探测.jpg

但线性探测会有一个不好的现象是：如图最后状态中，除非元素进过散列函数计算之后直接得出位置在#4 ~ #7，否则#4 ~ #7永远不可能会被优先考虑，因为(8 9 0 1 2已被占，遇到冲突会线性巡访整个表格) #3一直会被优先考虑。
这样会暴露出一个问题：主集团(primary clustering)陷阱。散列表中是一大团被用过的方格，插入操作极有可能在主集团所形成的泥泞中奋力爬行，不断解决碰撞问题，最后再找到空位置。然而插入之后又助长了主集团的长度。

public class LinearProbingHashST<Key, Value> {
    private int n;            // 当前key-value元素对数
    private int m;            // 线性表（key-value）的总长度
    private Key[] keys;     // the keys
    private Value[] vals;   // the values

    public void put(Key key, Value val) {
        .....省略参数的有效性判断
        // 如果已经用掉50%，则扩容，减小主集团的影响
        if (n >= m / 2)
          resize(2 * m);      // resize里面会重新计算散列值，插入元素
    
        // 线性探测过程
        for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
            // 如果已经存在key，则更新value
            if (keys[i].equals(key)) {
                vals[i] = val;
                    return;
            }
        }
        keys[i] = key;
        vals[i] = val;
        n++;
    }
    
    public void delete(Key key) {
        ...... 省略参数有效性判断
        // find position i of key
        int i = hash(key);
        while (!key.equals(keys[i]))
            i = (i + 1) % m;
        
      // delete key and associated value
        keys[i] = null;
        vals[i] = null;

        // rehash all keys in same cluster
        i = (i + 1) % m;
        while (keys[i] != null) {
            // delete keys[i] an vals[i] and reinsert
            Key keyToRehash = keys[i];
            Value valToRehash = vals[i];
            keys[i] = null;
            vals[i] = null;
            n--;
            put(keyToRehash, valToRehash);
            i = (i + 1) % m;
        }
        n--;
        // halves size of array if it's 12.5% full or less
        if (n > 0 && n <= m / 8)
            resize(m / 2);
    }
}

二次探测

二次探测主要用于解决主集团的问题。
其命名由来是因为解决碰撞的方程式：F(i) = i^2是一个二次方程式。更明确的说，如果散列函数计算出新元素位置H，而该位置实际上已经被使用，那么我们就依次尝试H+1^2，H+22，H+3^2......而不是像线性探测一样依序尝试：H+1，H+2，H+3.......

二次探测.jpg

二次探测可以消除主集团，但却可能造成次集团：两个元素经散列函数计算出来的位置若相同，那么插入时所探测的位置也相同，形成某种浪费。

但总体来说，还是二次探测相比于线性探测，仍然值得选择。

开链法

开链法是在每一个表格元素中维护一个list，散列函数分配某一个list，然后再那个list身上执行元素的插入，搜寻，删除等操作。虽然针对list是一种线性搜索，但list够短。速度还是很快。

开链法jpg

散列函数

参考资料
[1] 《STL源码剖析》侯捷
[2] 《算法》4th [美] Robert Sedgewick，Kevin Wayne