9.4.2　散列函数构造方法

1.直接定址法

取关键字或关键字的某个线性函数值为哈希地址。即

其中，a和b为常数（这种哈希函数叫作自身函数）。

2.数字分析法

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

3.平方取中法

取关键字平方后的中间几位作为哈希地址，较常见。

4.折叠法

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

5.除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，即

这是一种最简单，也是常用的构造哈希函数的方法。

6.随机数法

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