哈希函数是一种对应关系，是一个映射，能将关键词转为哈希函数值，便于更快的查询。当然对不同的关键字可能得到同一哈希地址，即，key1!=key2,而f(key1)=f(key2)。这种现象称为冲突。一般情况下，冲突只能尽可能的少，而不能完全避免。
对于关键词集合中任意一个关键词，经哈希函数映射到地址中任何一个地址的概率是相等的，称此类哈希函数为均匀哈希函数，这种算比好的哈希函数。一般而言，构造哈希函数的方法有以下几种：
1.直接地址法
取关键字或关键字的某个线性函数值为哈希地址。H(key)=key ,H(key)=a*key+b
2.数字分析法
以关键字中的若干数位组合成哈希地址。
3.平均取中法。
取关键字平方后中间几位为哈希地址
4.折叠法，取关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
5.除留余数法。取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址，即H(key)=key MOD p ，p<=m
这是一种最简单，也是最常用的构造哈希函数的方法。
6.随机数发。
处理冲突的一些方法。如果又关键字得到的哈希地址为j的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。若得到的另一个哈希地址H1仍然发生冲突，则再求下一个地址H2，若H2任然冲突，再求H3，一次类推。
1.开放地址法
Hi=(H(key)+di) MOD m i=1,2,3…k (k<=m-1)
m为哈希表表长；di为增量序列，可有下列三种取法：1>di=1,2,3…m-1 称为线性探测再散列；2>di=1^2,-1^2,2^2,-2^2,3^2…k^2(k<=m/2)二次探测再散列 3>di=伪随机数序列，伪随机探测再散列。
2.再哈希法
Hi=RHi（key） i=1,2,3.。。k
3.链地址法
4.建立一个公共溢出区。
发表回复