散列表

散列表又可以称之为哈希表，是实现字典操作的一种有效数据结构

最坏情况下查找元素时间为O(n)，但是平均时间为O(1)

适用于静态关键字集合，如程序设计语言中的保留字集合，CD-ROM上的文件名集合

直接寻址法

当全域U比较小时，直接寻址是一种简单有效的技术，用数组表示动态集合，记为T[0..m]，其中每个位置称为槽。

直接寻址法就是将元素直接放在槽中，如果不放，则需要用某种方法表示槽为空。

操作：

typedef struct node {
    int key;
} *NODE;

NODE direct_address_search(NODE T[], int k) { //查找
    return T[k];
}


void direct_address_insert(NODE T[], int x) { //插入
    T[x->key] = x;
}

void direct_address_delete(NODE T[], int x) { //删除
    T[x->key] = NULL;
}

直接寻址的缺点：当要储存的关键字比可能要储存的关键字小的多时，那么被分配的大部分空间会被浪费，那么需要散列函数列重新计算关键字的值T(h(k))，再放到槽里，h(k)可以称之为散列值。

存在的问题：当两个散列值映射到同一槽中时，形成了冲突。

为了解决冲突，有两种方法，一：通过精心设计的散列函数来尽量减少冲突的次数，二：需要有解决冲突的办法。

解决冲突的办法

链接法

在链接法中，把散列到同一槽中的所有元素都放在一个链表中，如图

装载因子等于n/m，n为存放的元素个数，m位槽的个数

一次不成功或成功的查找的平均时间都为O(1+n/m)

开放寻址法

在开放寻址法中，散列表可能被填满，以至于不能插入新的元素。该方法导致结果是装填因子不会超过1

优点：不需要用指针，而是计算要存取的槽序列，于是不需要存储指针而节省的空间，是的可以用同样的空间来提供更多的槽，潜在减少冲突，提高了检索速度

为了使用开放寻址法插入一个元素，需要连续的检查散列表，称为探查

int hash_insert(NODE T[], int k) { //插入
    int i = 0, j;
    while(i != m) {
        j = h(k, i); // h为探查序列
        if(T[j] != NULL) {
            T[j] = k;
            return j;
        }else{
            i = i + 1；
        }
    }
    print("hash table overflow\n");
}

int hash_search(NODE T[], int k) { //查找
    i = 0;
    while(T[i] != NULL || i != m) {
        j = h(k, i); //探查序列
        if(T[j] == k) {
            return j;
        }
        i = i + 1;
    }
    return NULL;
}

从开放寻址法散列表中删除一个元素是比较困难的。解决办法是删除时候用delete代替NULL标记槽。

为此在必须删除关键字的应用中，更常见的做法是使用链接法解决冲突。

有三种技术来计算开放寻址法中的探查序列：

1.线性探查

散列函数 h(k,i) = (h’(k) + i) mod m, i = 0,…,m-1 。h’为辅助散列函数

该方法存在一次群集的现象，当一个空槽前有i个满的槽时，该空槽下一次会有很大概率被占用，以至于被占用的槽越来越长，平均查找时间也会越来越大。

2.二次探查

散列函数 h(k,i) = (h’(k) + bi + ci*i) mod m, i = 0,…,m-1。 b，c为正的辅助常数。

该方法存在二次群集的现象

3.双重散列

二重散列是用于开放寻址法的最好方法之一，因为他所产生的排列具有随机选择排列的许多特性

散列函数 h(k,i) = (h1’(k) + i*h2(k)) mod m, i = 0,…,m-1。 h1和h2为辅助散列函数

初始探测位置为T[h1(k)]，然后每次移动i*h2(k) mod m 。

完全散列

该方法最坏情况下访问时间为O(1)

该散列结构如图:

采用一级散列表和二级散列表，在同一槽位的元素进行二级散列

精心设计散列函数

除法散列法

函数表示 h(k) = k mod m;

在进行除法散列法时，m不应为2的幂，如何m=2的p次幂，h(k)就是k的p个最低位数字，所以一个不太接近
2的整数幂的素数，常常是m的一个较好选择

乘法散列法

函数表示 h(k) = int(m(kA mod 1))

kA mod 1 代表取kA的小数部分，即kA-int(kA)

进行乘法散列法时，对于m的取值不是很关键，一般选择2的某个幂，因为在大多数计算机上比较容易实现

全域散列法

随机地选择散列函数，使之独立于要存储的关键字，不管别人选什么关键字，其平均性能都很好，这就是全域散列

文章目录

散列表