抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

散列表

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

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

1
2
3
4
5
6
7
8
9
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 mh(k)=k\ mod\ m

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

乘法散列表

乘法散列表的哈希函数为

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

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

哈希冲突

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

开放寻址法

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

散列函数的扩展

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

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

集群

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

线性探查

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

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

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

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

二次探查

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

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

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

双重散列

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

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

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

评论