HASH函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
为简单起见，假定关键码是定义在自然数集合上，常见的哈希函数构造方法有：
1、直接定址法
以关键字Key本身或关键字加上某个数值常量C作为散列地址的方法。散列函数为：h(Key)= Key+C，若C为0，则散列地址就是关键字本身。
2、除余法
选择一个适当的正整数m，用m去除关键码，取其余数作为地址，即：h(Key)= Key % m，这个方法应用的最多，其关键是m的选取,一般选m为小于某个区域长度n的最大素数（如例1中取m=13），
为什么呢？就是为了尽力避免冲突。假设取m=1000 ，则哈希函数分类的标准实际上就变成了按照关键字末三位数分类，这样最多1000类，冲突会很多。
一般地说，如果 m 的约数越多，那么冲突的几率就越大。而素数的约数是最少的，因此我们选用大素数。记住“素数是我们的得力助手”。
3、数字分析法
常有这样的情况：关键码的位数比存储区域的地址的位数多，在这种情况下可以对关键码的各位进行分析，丢掉分布不均匀的位留下分布均匀的位作为地址。
本方法适用于所有关键字已知，并对关键字中每一位的取值分布情况作出了分析。
【例】 对下列关键码集合（表中左边一列）进行关键码到地址的转换，要求用三位地址。
分析：
键码是9位的，地址是3位的，需要经过数字分析丢掉6位。丢掉哪6位呢？显然前3位是没有任何区分度，第5位1太多、第6位基本都是8和9、第7位都是3、4、5，这几位的区分度都不好，而相对来说，第4、8、9位分布比较均匀，所以留下这3位作为地址（表中右边一列）。
4、平方取中法
将关键码的值平方，然后取中间的几位作为散列地址。具体取多少位视实际要求而定，取哪几位常常结合数字分析法。
【例】
将一组关键字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100，1002001，0012321)，若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。
5、折叠法
如果关键码的位数比地址码的位数多，而且各位分布较均匀，不适于用数字分析法丢掉某些数位，那么可以考虑用折叠法。折叠法是将关键码从某些地方断开，分关键码为几个部分，其中有一部分的长度等于地址码的长度，然后将其余部分加到它的上面，如果最高位有进位，则把进位丢掉。
一般是先将关键字分割成位数相同的几段（最后一段的位数可少一些），段的位数取决于散列地址的位数，由实际需要而定，然后将它们的对应位叠加和（舍去最高位进位）作为散列地址。
6、基数转换法
将关键码值看成在另一个基数制上的表示，然后把它转换成原来基数制的数，再用数字分析法取其中的几位作为地址。一般取大于原来基数的数作转换的基数，并且两个基数要是互质的。
