9.4.2 构造哈希函数的方法

　　若对于关键字集合中的任意一个关键字，经哈希函数映象到地址集合中任何一个地址的概率相等，则称此类哈希函数为均匀的哈希函数。对数值型的关键字，常用的构造均匀的哈希函数的方法有如下几种：

　一、直接定址法

　　取关键字本身或关键字的某个线性函数值作为哈希表的地址。
　　即 Hash(key)=key 或 Hash(key)=a key+b （a 和 b 均为常数）
　　直接定址所得地址集的大小和关键字集的大小相同，关键字和地址一一对应，决不会产生冲突。但实际应用中能采用直接定址的情况极少。
　		  

　　从理论上讲，哈希函数的构造本无定则可言，因为Hash（哈希）的原义是"杂凑"。但从实用上说，设定的哈希函数不仅要求其函数值必须落在预设的表长范围内，而且应对当前所讨论的关键字集合尽可能少地产生冲突，称这样的哈希函数为"好"的哈希函数。

　　例如，对于关键字(学号)为02000至02999的哈希表，可取关键字的后三位为哈希函数。

  
  　二、数字分析法

　　如果可能出现的关键字的数位相同，且取值事先知道，则可对关键字进行分析，取其中"分布均匀"的若干位或它们的组合作为哈希表的地址。
　　例如已知80个记录的关键字为8位十进制数（右图列出其中部分），假设哈希表的表长为100，即地址为00～99。由于关键字中的第 1、2、3 和 8 位取值集中在某几个数上，则应取其余四位中的任意两位或其中两位与另两位之叠加和（舍去进位）作为哈希地址。
  
①
②
③
④
⑤
⑥
⑦
⑧
0
2
1
4
6
5
3
2
0
2
1
7
2
2
4
2
0
2
2
8
7
4
2
7
0
2
2
0
1
3
6
7
0
2
2
2
8
8
1
7
0
2
2
3
2
9
8
2
0
2
3
5
4
1
5
2
0
2
3
6
8
5
3
5
0
2
3
1
9
3
2
7
0
2
3
9
5
7
1
5
．
．
．
　
  
  　三、平方取中法

　　如果关键字的所有各位分布都不均匀，则可取关键字的平方值的中间若干位作为哈希表的地址。由于一个数的平方值的中间几位数受该数所有位影响，将使随机分布的关键字得到的哈希函数值也随机。
   　例如：下列八进制数的关键字及其哈希地址
关键字
(关键字)2
哈希地址
0100
0010000
010
1100
1210000
210
1200
1440000
440
1160
1370400
370
2061
4310541
310
2062
4314704
314
2161
4734741
734
2162
4741304
741
2163
4745651
745
…