构造散列函数的两个基本原则
直接定址法
取关键字的某个线性函数值为散列地址，即f(key)=a*key+b。
数字分析法
数字分析法通常适合处理关键字位数比较大的情况。
平方取中法
平方取中法是将关键字平方之后取中间若干位数字作为散列地址。
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址。
除留余数法
此方法为最常用的构造散列函数方法，对于散列表长为m的散列函数计算公式为：
f(key) = key mod p(p<=m)
事实上，这个方法不仅可以对关键字直接取模，也可以通过折叠、平方取中后再取模。
随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址，即：f(key) = random(key)。
这里的random是随机函数，当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
视不同的情况采用不同的散列函数
现实中，应该视不同的情况采用不同的散列函数，参考方向：
·计算散列地址所需的时间
·关键字的长度
·散列表的大小
·关键字的分布情况
·记录查找的频率
处理散列冲突的方法
开放定址法
所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
它的公式是：
fi(key) = (f(key)+di) MOD m (di=1,2,…,m-1)
可以修改di的取值方式，例如使用平方运算来尽量解决堆积问题：
fi(key) = (f(key)+di) MOD m (di=1²,-1²,2²,-2²…,q²,-q²,q<=m/1)
还有一种方法是，在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法：
fi(key) = (f(key)+di) MOD m (di是由一个随机函数获得的数列)
再散列函数法
fi(key) = RHi(key) (i=1,2,3,…k)