散列表之开放寻址法

在开放寻址法(open addressing)中，所有的元素都存放在散列表中。也就是说，每个表项或包含动态集合的一个元素，或包含 NIL。当查找某个元素时，要系统地检查所有的表项，直到找到所需的元素，或者最终查明该元素不在表中。不像链接法，这里既没有链表，也没有元素存放在散列表以外。因此在开放寻址法中，散列表可能会被填满，以至于不能插入任何新的元素。该方法导致的一个结果便是装载因子绝对不会超过 1。

开放寻址方式的好处在于它不用指针，而是计算出要存取的槽序列。于是，不用存储指针而节省的空间，使得可以用同样的空间来提供更多的槽，潜在地减少了冲突，提高了检索速度。

为了使用开放寻址法插入一个元素，需要连续地检查散列表，或称为探查（probe），直到找到一个空槽来存放待插入的关键字为止。

线性探查

给定一个普通的散列函数 h‘: U‘→{0, 1, …, m – 1}，称之为辅助散列函数，线性探查方法采用的散列函数为：

h(k, i) = (h'(k) + i) mod m, i = 0, 1, …, m – 1

线性探查方法比较容易实现，但它存在着一个问题，称为一次群集。随着连续被占用的槽不断增加，平均查找时间也随之不断增加。群集现象很容易出现，这是因为当一个空槽前有 i 个满的槽时，该空槽为下一个将被占用的概率是(i + 1) / m。连续被占用的槽就会变得越来越长，因而平均查找时间也会越来越大。

二次探查

二次探查采用如下形式的散列函数：

h(k, i) = (h'(k) + c1* i + c2 * i * i) mod m

其中 h'是一个辅助散列函数，c1 和 c2 为正的辅助常数， i = 0, 1, …, m – 1。初始探查位置为 T[h'(k)]，后续的探查位置要加上一个偏移量，该偏移量以二次的方式依赖于探查序号 i。这种探查方法的效果要比线性探查好得多，但是，为了能够充分利用散列表， c1、c2 和 m 的值要受到限制。

此外，如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的，这是因为 h(k1, 0) = h(k2, 0)蕴含着 h(k1, i) = h(k2, i)。这一性质可导致一种轻度的群集，成为二次群集。

双重散列

双重散列是用于开放寻址法的最好的方法之一，因为它所产生的排序具有随机选择排列的许多特性。双重散列采用如下形式的散列函数：

h(k, i) = (h1(k) + i * h2(k)) mod m

其中 h1 和 h2 均为辅助散列函数。初始探查位置为 T[h1(k)]，后续的探查位置是前一个位置加上偏移量 h2(k)模 m。因此，不像线性探查或二次探查，这里的探查序列以两种不同方式依赖于关键字 k，因为初始探查位置、偏移量或者二者都可能发生变化。

为了能查找整个散列表，值 h2(k)必须要与表大小 m 互素。有一种简便的方法确保这个条件成立，就是取 m 为 2 的幂，并设计一个总产生奇数的 h2。另一种方法是取 m 为素数，并设计一个总是返回较 m 小的正整数的函数 h2。例如，我们可以取 m 为素数，并取

h1(k) = k mod m，h2(k) = 1 + ( k mod m')

其中 m‘略小于 m（比如 m-1）。

最后，开放寻址法散列表的实现：

    #include <stdlib.h>
    #include <stdio.h>

    #define m           17
    //#define HASH(k)    k % m       //除法散列法

    #define A           0.85
    //#define HASH(k)    (int)(m * (k * A - (int)(k * A)))         //乘法散列法

    #define c1          7
    #define c2          5
    //#define h(k, i)     (HASH(k) + i) % m       //线性探查
    //#define h(k, i)     (HASH(i) + c1 * i + c2 * i * i) % m         //二次探查

    #define h1(k)       k % m
    #define h2(k)       1 + (k % (m - 1))
    #define h(k, i)     (h1(k) + i * h2(k)) % m       //双重散列

    #define DEL         -65535

    int
    hash_insert(int *T, int k)
    {
        /*
         * 在散列表中插入一个元素，不断的探查
         * 以找到一个空槽可以插入，或者探查了
         * 整个散列表，输出错误信息并退出
         */
        int     i, j;

        for (i = 0; i != m; i++) {
            j = h(k, i);
            if (T[j] == NULL || T[j] == DEL) {
                T[j] = k;
                return(j);
            }
        }

        fprintf(stderr, "hash table overflow\n");
        exit(1);
    }

    int
    hash_search(int *T, int k)
    {
        /*
         * 在散列表中查找一个元素，不断进行
         * 探查，直到找到该元素，或者探查到
         * 了一个空槽，或者找遍了整个散列表
         */
        int     i, j;

        for (i = 0; i != m; i++) {
            j = h(k, i);
            if (T[j] == k) {
                printf("found value: %d in key: %d\n", k, j);
                return(j);
            } else if (T[j] == NULL) {
                break;
            }
        }

        fprintf(stderr, "can't find value: %d\n", k);
        return(NULL);
    }

    int
    hash_delete(int *T, int k)
    {
        /*
         * 删除一个元素的时候并不将它置为NULL，
         * 因为这有可能会使得在查找的时候找不到
         * 后续的元素，查找在删除的地方就中断了。
         * 可以在删除的时候将其置为一个特殊的值，
         * 以避免这种情况。这里用的是DEL。
         */
        int     i, j;

        for (i = 0; i != m; i++) {
            j = h(k, i);
            if (T[j] == k) {
                T[j] = DEL;
                return(0);
            }
        }

        fprintf(stderr, "can't find %d in hashtable\n", k);
        exit(1);
    }

    void
    print_hash(int *T)
    {
        int     i;

        printf("---------------hashtable---------------\n");
        for (i = 0; i < m; i++) {
            if (T[i] != NULL && T[i] != DEL)
                printf("key: %2d, value: %4d\n", i, T[i]);
            else
                printf("key: %2d, value: NULL\n", i);
        }
        printf("------------------end------------------\n\n");
    }

    int
    main(void)
    {
        /*
         * 用数组实现的简单的开放寻址法的散列表
         */
        int     i;
        int     T[m];

        for (i = 0; i < m; i++) {
            T[i] = NULL;
        }

        hash_insert(T, 28);
        hash_insert(T, 438);
        hash_insert(T, 923);
        hash_insert(T, 239);
        hash_insert(T, 29);
        hash_insert(T, 31);
        hash_insert(T, 32);
        hash_insert(T, 39);
        hash_insert(T, 2);
        hash_insert(T, 24);
        hash_insert(T, 432);

        print_hash(T);

        hash_delete(T, 239);
        hash_delete(T, 31);
        hash_delete(T, 28);

        printf("\nafter delete 239, 31, 28...\n\n");

        print_hash(T);

        hash_search(T, 438);
        hash_search(T, 239);

        exit(0);
    }

散列表之开放寻址法

目录

线性探查

二次探查

双重散列