算法基础-散列表与开放寻址

散列表

散列表是一种动态的集合,它支持插入,检索,删除等字典操作.散列表是数组的扩展,一般的数组可以在 O(1) 的时间复杂度内进行随机读取,而散列表则使用一个特殊的函数来为各个元素分组在查找元素,只需要用特殊函数计算一次,就可以知道元素存放的位置

散列表的基本结构是一个关键字数组和链表,任意元素通过哈希函数计算出一个关键字,通过关键字可以直接定位到一个具体链表,然后往链表末尾添加该元素

struct HashTable{
    int length;
    Node* keyList;
};
 
struct Node{
    void* value;
    Node* next;
};

当关键字全集 U 较小时,可以使用直接寻址表.例如需要存放的元素为 1 到 10 的数字,则可以创建一个长度为 10 的数组,每个数字对应唯一一个数组元素,例如数字 5 对应数组 a[4],如果不存在数字 6,则 a[6] 的值为 NULL

当关键字全集 U 较大特别大时,内存中已经无法容下一个散列表,此时应该对关键字进行函数计算,例如除余,将所有关键字依照余数分类.此时会出现重复,对于重复项,我们只需要往列表的末尾延申就行

除法散列表的哈希函数为

h(k)=k\ mod\ m

将传入的关键字转化成数字以后,进行求余,这样哈希函数的值域就会被严格限制在 $[0,m-1]$

乘法散列表的哈希函数为

h(k)=\lfloor m(kA-\lfloor kA \rfloor) \rfloor

将关键字乘上一个常数 $A$ ,然后取小数部分,乘上 $m$ ,最后向下取整

如果存在不相同的元素 $k_1,k_2$ ,使得 $h(k_1) = h(k_2)$ ,则这两个元素会被映射到散列表的同一个地址,此时称为哈希冲突

在开放寻址法中,如果需要往散列表中插入一个新的元素,则需要用一种方法按顺序探查散列表,直到找到一个空槽来存放新元素.当查找元素时,也应该按照相同的方法探查整个散列表,直到找到一个空槽,这时可以证明该元素不存在.因为如果它存在的话,那么它应该会在当前空槽的位置

为了解决冲突问题,需要对散列函数进行扩展,将探查次数作为自变量加入到原散列函数中

即在原扩展函数的基础上,引入了探查次数,当第一次探查时,i 为 0,就是原散列函数值,而从第二次开始,每次探查时 i 都会加一,直到找到一个空槽

如果对于不同的 $k_1$ 和 $k_2$ ,使得这两个元素出现冲突时,后续的探查次序完全一致,则说明槽位出现集群,即大量元素被按照某一规律储存,后序探查时又会按顺序一个一个遍历,这样就造成了效率低下

线性探查在遇到冲突时,会按顺序探查下一个槽的位置

h'(k,i)=[h(k)+i]\ mod \ m

假设一个散列表共有10个槽位,第一次探查的槽位是 $T(2)$ ,那么下一次就是 $T(3)$

该方法会导致被占用的槽位出现集群,即一大串连续占用的槽位,因此平均查找时间也会大大增加

二次探查使用二次函数来探查空的槽位

h'(k,i)=[h(k)+c_1i+c_2i^2]\ mod \ m

该方案的优点是不会出现连续集群,但是仍有一个缺点：如果 $h(k_1) = h(k_2)$ ,那么后序的探查顺序也会完全一致,这会造成轻度的集群,称为“二次集群”

双重散列使用两个哈希函数来防止出现集群

h'(k,i)=[h_1(k)+ih_2(k)]\ mod \ m

这样的好处是难以出现不同的 $k$ 值对应相同的槽位,也就避免了集群的出现