《算法导论》11.3 除法散列法、乘法散列法 11.4 开放寻址法

散列函数

一、除法散列法

1、含义：通过k除以m的余数，将关键字k映射到m个槽的某一个上，即散列函数为：h(k) = k mod m，例如m = 12,所给关键字为100，则h(k) = 4。
2、在运用除法散列法的时候，要注意避免使用某些m的值，例如不推荐m=2^p，因为h(k)就是k的p个最低位的数字的h，例如225mod4 = 125mod4 = 25 mod 4。
3、选一个不太接近二的整数幂的素数，是一个非常好的选择。

二、乘法散列法

1、步骤：
（1）用关键字k呈上常数A（0 （2）第二步，用m乘以这个值，然后向下取整，总之散列函数为

2、优点：对于m的选择并不是特别关键，一般选择它为2的某个幂次（m = 2^p）

如图，关键字k的w位表示乘上s = A*2^w的w位值。在乘积的低w位中，p个最高位构成了所需的散列值h(k),在乘积的低w位中，p个最高位构成了h(k)。

开放寻址法

一、基本内容

1、基本内容：在开放寻址法中，所有元素都放在散列表里。也就是说，每个表项要么包含动态集合的一个元素，要么包含NIL。当查找某个元素的时候，要系统性检查所有表项，直到找到所需的元素，或者直到最终查明元素不再表中。
2、优势：可以将用作链接的链表存放在散列表没有用到的槽里，但是开放寻址法本身的优势就是在于它不用指针，而是计算出要存储的槽序列。于是不用指针而省下的空间可以用来提供更多槽，减少冲突。
3、探查：为了使用开放寻址法插入一个元素，需要连续地检查散列表，称为“探查（probe）”，直到找到适合的位置插入。
（1）如何探查？
我们将散列函数扩充，使之包含探查号（从零开始）以作为其第二个输入参数，这样散列函数就变为
，对每一个关键字k，使用开放寻址法的探查序列（prove sequence）

这是<0,1,…m-1>的一个排列，使得每一个表位最终都有机会成为用来插入新关键字的槽。
（2）插入关键字伪代码

HASH-INSERT(T,k)
i = 0
repeat
	j = h(k,i)
	if T[j] == NIL;//如果T[j]为NIL的话，将k填入，返回位置j即可；
		T[j] = k
		return j
	else i = i+1
until i==m
error "hash table overflow"
1
2
3
4
5
6
7
8
9
10

思路：假设伪代码中散列表T的元素是无卫星数据的关键字；关键字k等同于包含关键字k的元素。每个槽包含一个关键字或NIL。
（3）查找关键字伪代码

HASH-SEARCH(T,k)
i = 0
repeat
	j = h(k,i)
	if(T[j] == k)//找到了就直接返回
		return j
	i = i+1
until T[j]==NIL or i==m	//如果T[j]=NIL就说明k不在表中，k在表中的话就得在此处
return NIL
1
2
3
4
5
6
7
8
9

二、线性探查和二次探查

1、线性探查

（1）给定一个普通的散列函数
，称之为辅助散列函数，线性探查方法采用的散列函数为

给定一个关键字k，从T[h’(k)]探查到T[m-1]，再绕到T[0]，T[1]直到T[h’(k)-1]，所以一共有m个不容的探查序列。
（2）线性探查比较容易实现，但是容易出现一次群集的问题，因为当一个空槽之前有i个满的槽时，该槽下一个被占用的概率为(i+1)/m，连续被占用的槽会越来越多，平均查找时间也会越来越大。

二、二次探查

（1）采用如下形式的散列函数：

其中h’为辅助散列函数，c1和c2为正的辅助常数，i = 0,1,…m-1。初始的探查位置为T[h’(k)]，后续的探查位置要加一个偏移量，该偏移量以二次的方式依赖于i。为了充分利用散列表，要限制c1c2的值；
（2）如果两个关键字的初始探查位置相同，那么它们的探查序列也相同，因为h(k1,0)=h(k2,0)蕴含h(k1,i) = h(k2,i)。这有可能造成二次群集。初始探查位置决定整个序列，有m个不同的探查序列被用到（和线性探查一样）。

三、双重散列

（1）用于开放寻址法的最好方法之一，采用如下形式散列函数：

h1和h2均为辅助散列函数，初始探查位置为T[h1(k)]，后续加上偏移量h2(k)再模m。
（2）为了可以查找整个散列表，值h2(k)必须要和表的大小互素：第一种办法是取m为2的幂，设计一个总产生奇数的h2；第二种办法是取m为素数，并设计一个总是返回比m小的正整数的函数h2。例如，取m为素数，

m’略小于m。
（3）举个例子：k=123456，m=701，m’ = 700，则由h1(k)=80,h2(k)=257，可知我们第一个探查位置为80，然后检查每第257个槽，直到找到这个关键字，或者遍历完所有的槽没找到。
（4）
图中描述的是双重散列法的插入，这里散列表的大小是13，h1(k)=k mod 13,h2(k) = 1+(k mod 11)。因为14 mod 13 = 1，14 mod 11 = 3，因此在探查了槽1和槽5后，关键字14插入到槽9中。