几个概念
- 哈希函数:一个把查找表中的关键字映射成该关键字对应的地址的函数,记为H(K)。
- 冲突:对不同的关键字可能得到同一哈希地址的现象,即key1 != key2,而H(key1)=H(key2)。
- 同义词:发生冲突的不同关键字。
- 哈希表:根据关键字直接进行访问的数据结构,建立了关键字与存储地址之间的一种直接映射关系。
哈希函数的构造方法
(1)直接定址法
取关键字或关键字的线性函数值为哈希地址,即H(key)=key或H(key)=a*key+b。
这种方法对于不同的关键字不会发生冲突,但关键字分布不连续,空位多,会造成存储空间的浪费。
(2)除留余数法
取关键字被某个不大于哈希表表长length的数p除后所得的余数为哈希地址,即H(key)=key % p,p<=length。
p一般取一个不大于length但最接近或等于length的质数。
(3)平方取中法
取关键字平方后的中间几位为哈希地址。
(4)数字分析法
设关键字是r进制数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干位组成哈希地址。
(5)折叠法
将关键字分割成位数相同的几部分,然后取这几部分的叠加和(舍去进位)作为哈希地址。
当关键字位数很多,而且关键字中每一位上数字分布大致均匀是适用。
处理冲突的方法
- 开放定址法
H~i~ = (H(key) + d~i~) % length,i = 1,2,3,...,length。
其中:H(key)为哈希函数;length为哈希表表长;d~i~为增量序列。
对于d~i~有几种不同的取法:
(1)d~i~ = 1,2,3,...,length-1,称为线性探测再散列;
(2)d~i~ = 1^2^,-1^2^,2^2^,-2^2^,3^2^,...,+-k^2^(k<=length/2),称为二次探测再散列;
(3)d~i~ = 伪随机数序列,称为伪随机探测再散列。
- 再哈希法
H~i~ = RH~i~(key),i = 1,2,3,...,length。
RH~i~均为不同的哈希函数,即在同义词产生冲突时计算另一个哈希函数地址,直到冲突不在发生。
- 链地址法
将所有关键字为同义词的记录存储在同一线性表中。