散列表

2017-09-25  本文已影响0人  wayyyy

什么散列

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

举个例子:如果所有元素都是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+12,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

上一篇下一篇

猜你喜欢

热点阅读