8.3 溢出处理

  • 「线性开放定址法 linear open addressing」「线性探测法 linear probing」 如果将新元素散列到一个已经满的散列桶中,最简单的处理方法是把这个新元素插到最近的未满的散列桶中。首先计算出标识符 xx 的散列函数 f(x)f(x),然后依次检查散列表中的散列桶 ht[(f(x)+j)%M],0jMht[(f(x) + j)\%M], 0 \leq j \leq M,其中 MM 为散列表的大小。检查散列表可能出现如下四种情况:
    1. 散列桶中包含标识符 xx。此时,说明 xx 已经在散列表中。
    2. 散列桶存放的是空串。这说明该散列桶为空,可以将新元素直接插入其中。
    3. 散列桶存放的不是空串,也不是 xx。此时,继续检查下一个散列桶。
    4. 开始检查时的散列桶被第二次检查,且其他散列桶已经被检查过。这说明散列表已满,报告错误状态并退出。
void linear_insert(element item, element ht[])
{
    int i, hash_value;
    hash_value = hash(item.key); // hash(key) 将 key 转为自然数
    i = hash_value;
    while (strlen(ht[i].key)) {
        if (!strcmp(ht[i].key, item.key)) {
            fprintf(stderr, "Duplicate entry\n");
            exit(1);
        }
        i = (i + 1) % TABLE_SIZE;
        if (i == hash_value) {
            fprintf(stderr, "The table is full\n");
            exit(1);
        }
    }
    ht[i] = item;
}
  • 线性开放定址法会导致标识符堆积现象,形成标识符聚类。比如将 acos, atoi, char, define, exp, ceil, cos, float, atol, floor, ctime 依次插入散列函数取值为每个关键字的首字母的散列桶中,由于这些标识符的首字母都比较靠前,因此它们会堆积在一起,造成插入后面的标识符时查找痛的次数较多(如下表)。通过采用 「二次探测法 quadratic probing」 可以在一定程度上减少这些标识符的聚类增长。在线性探测中,散列桶的探测顺序为 (f(x)+i)%b,0ib1(f(x) + i)\% b, 0 \leq i \leq b-1,其中 bb 是散列表中的散列桶个数。与线性探测不同,在二次探测中,使用 ii 的二次函数作为探测增量,即对于所有的 1i(b1)/21 \leq i \leq (b-1)/2,依次检查散列桶 f(x),(f(x)+i2)%bf(x), (f(x) + i^2)\% b(f(x)i2)%b(f(x) - i^2)\% b。当 bb 是形如 4j+34j + 3 (其中 jj 是一个整数)的素数时,二次探测法可以检查到表中的每个散列桶。
散列桶序号 xx 插入时查找桶的次数
0 acos 1
1 atoi 2
2 char 1
3 define 1
4 exp 1
5 ceil 4
6 cos 5
7 float 3
8 atol 9
9 floor 5
10 ctime 9
...
25
  • 还可以通过一个散列函数序列 f1,f2,,fbf_1, f_2, \cdots, f_b 来减少线性探测法产生的聚类现象。这种方法称为 「再散列法 rehashing」。在这种方法中,依次检查散列桶 fi(x),1ibf_i(x), 1 \leq i \leq b
  • 「随机探测法 random probing」 在具有 bb 个散列桶的散列表中查找标识符 xx 时,将依次探测散列桶 f(x),(f(x)+S(i))%b,1ib1f(x), (f(x) + S(i))\% b, 1 \leq i \leq b-1,其中 S(i)S(i) 为伪随机数。随机数产生器必须能够产生从 11b1b - 1 的每个数,且每个数只产生一次。
  • 「拉链法」 由于在插入一个标识符时需要与不同散列值的标识符进行比较,所以线性探测法及其若干变形方法的性能很差。例如上表插入 atol 时需要查找 9 次。「拉链法」则是为每个散列桶都提供一个同义词表,就能够消除这样的标识符比较。在插入一个新元素时,只需计算其散列地址 f(x)f(x),并在其同义词列表上查找即可。由于事先并不知道同义词表的大小,所以采用单向链表存储同义词表。函数 chain_insert 实现了拉链法的插入操作。函数首先计算标识符的散列地址,然后在相应的散列桶对应的单向链表中查找标识符。如果找到该标识符,则输出错误信息并退出。如果该标识符不在单向链表中,就将其插入表的尾部。如果该链表为空,修改表头结点使其指向新插入的表项。
与上表对应的采用拉链法的散列表
[0] -> acos -> atoi -> atol
[1] -> NULL
[2] -> char -> ceil -> cos -> ctime
[3] -> define
[4] -> exp
[5] -> float -> floor
[6] -> NULL
...
[25] -> NULL
void chain_insert(element item, list_pointer ht[])
{
    int hash_value = hash(item.key);
    list_pointer ptr, trail = NULL, lead = ht[hash_value];
    for (; lead; trail = lead, lead = lead -> link) {
        if (!strcmp(lead -> item.key, item.key)) {
            fprintf(stderr, "The key is in the table\n");
            exit(1);
        }
    }
    ptr = (list_pointer)malloc(sizeof(list));
    if (IS_FULL(ptr)) {
        fprintf(stderr, "The memory is full\n");
        exit(1);
    }
    ptr -> item = item;
    ptr -> link = NULL;
    if (trail)
        trail -> link = ptr;
    else
        ht[hash_value] = ptr;
}
  • 在实际中,由于经常地使用具有公共前缀或后缀的标识符,也可能是其他标识符的简单排列,所以选取的标识符存在概率上的不均匀性。因此,在实际中,希望选择的散列函数能够影响散列表的性能。下表中每列表示在查找 8 个不同的散列表过程中访问散列桶次数的平均值。拉链法的性能要优于线性开放定址法。就不同散列函数的性能而言,可以看出质数除余法通常具有较高的性能。因此,对于一般的应用,质数除余法是一种理想的方法。其中的除数应该是一个素数,且没有小于 20 的素因子。另外可以看到,表中还给出了基于关键字随机选取时,散列桶访问次数的理论期望值。
α=nb\alpha = \frac{n}{b} 0.50 0.50 0.75 0.75 0.90 0.90 0.95 0.95
包含的标识符数 33,575 24,050 4,909 3,072 2,241 930 762 500
散列函数 拉链法 开放 拉链法 开放 拉链法 开放 拉链法 开放
平方取中 1.26 1.73 1.40 9.75 1.45 37.14 1.47 37.53
质数取余 1.19 4.52 1.31 7.20 1.38 22.42 1.41 25.79
移位折叠 1.33 21.75 1.48 65.10 1.40 77.01 1.51 118.57
分界折叠 1.39 22.97 1.57 48.70 1.55 69.63 1.51 97.56
数字分析 1.35 4.55 1.49 30.62 1.52 89.20 1.52 125.59
理论值 1.25 1.50 1.37 2.50 1.45 5.50 1.48 10.50

results matching ""

    No results matching ""