Question

hash函数的构造方法

Answer 1

常用的构造哈希（hash）函数的方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数发、随机数法。

1、直接定址法

取关键字或关键字的某个线性函数值为哈希地址。即：H(key)=key或H(key)=akey+b。其中a和b为常数（这种哈希函数叫做自身函数）。

2、数字分析法

假设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

3、平方取中法

取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关。

4、折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法（folding)。关键字位数很多，而且关键字中每一－位上数字分布大致均匀时，可以采用折叠法得到哈希地址。

5、除留余数发

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key) = key MOD p, pm。这是一种最简单，也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模（MOD),也可在折叠，平方取中等运算之后取模。

6、随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数。通常﹐当关键字长度不等时采用此法构造哈希函数较恰当。

冲突的处理：

哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2，但H（K1）＝H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址，解决冲突的方法：

1、链接法（拉链法）：将具有同一散列地址的记录存储在一条线性链表中。例，除留余数法中，设关键字为（18,14,01,68,27,55,79），除数为13，散列地址为（5,1,1,3,1,3,1）。

2、开放定址法：如果h(k）已经被占用，按如下序列探查：（h(k)+p⑴）％TSize,(h(k)+p⑵）％TSize，…，（h(k)+p(i))%TSize，…其中，h(k)为哈希函数，TSize为哈希表长，p(i）为探查函数。

在h(k)+p(i-1)）％TSize的基础上，若发现冲突，则使用增量p(i)进行新的探测，直至无冲突出现为止。

根据探查函数p(i）的不同，开放定址法又分为线性探查法（p(i) = i : 1,2,3，…），二次探查法（p(i)=(-1)^(i-1)*((i+1)/2)^2，探查序列依次为：1, -1,4, -4, 9…）。

随机探查法（p(i):随机数），双散列函数法（双散列函数h(key)，hp (key）若h(key）出现冲突，则再使用hp (key）求取散列地址。探查序列为：h(k),h(k)+ hp(k），…，h(k)+ i*hp(k））。

3、桶定址法：桶为一片足够大的存储空间。桶定址为表中的每个地址关联一个桶。如果桶已经满了，可以使用开放定址法来处理。例如，插入A5,A2,A3,B5,A9,B2,B9,C2，采用线性探查法解决冲突。