9.3.1哈希函数

一般情况，需建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。

9.3.2哈希函数的构造方法

 除留余数法

     H(key) = key MOD p     p≤m (表长)

例

假设哈希表长度m=13,采用除留余数法哈希函数建立如下关键字集合的哈希表：

{16,74,60,43,54,90,46,31,29,88,77}。

 解：n=11,m=13,除留余数法的哈希函数为f(k)=k mod p,p应为小于等于m的素数,假设p取值13。则有：

    f(16)=3,f(74)=9,f(60)=8,f(43)=4,

    f(54)=2,f(90)=12,f(46)=7,f(31)=5,

    f(29)=3, f(88)=10,f(77)=12。

9.3.3处理冲突的方法

1. 开放定址法

    为产生冲突的地址H(key)求得一个地址序列：

        H0, H1, H2, …, Hs     1≤s≤m-1

其中：H0 = H(key)

      Hi = ( H(key) + di ) MOD m  i=1, 2, …,s

n 增量 di 有三种取法：

(1) 线性探测再散列：di = c´i。最简单的情况  c=1

(2) 平方探测再散列：di = 12, -12, 22, -22, …,

(3) 随机探测再散列：di 是一组伪随机数列

2. 再哈希法

n 出现冲突时，采用多个哈希函数计算散列地址，直到找到空单元为止。或者用另一个哈希函数作为步长进行探测，找到下一个空单元。

如：H1(key) = key MOD 11

         H2(key) = ( key+ MOD 9)＋1

n 示例：给出一组表项关键字{ 22, 41, 53, 46, 30, 13, 01, 67 }。散列函数为：H(x)＝(3x) % 11。散列表为 HT[0..10]，m = 11。因此，再散列函数为 RH(x) = (7x) % 10 +1。

       Hi = ( Hi-1 + (7x) % 10 +1 ) % 11,  i = 1, 2, ¼

3. 链地址法

将所有哈希地址相同的记录都链接在同一链表中。链地址肯定不会产生二次聚集。