散列函数 - wolai 笔记

1.设计目标

让不同的关键字冲突尽可能的少
散列查找是典型的“空间换时间”的算法,只要散列函数设计的合理,则散列表越长,冲突概率越低。

2.直接定值法

直接取关键字的某个线性函数值为散列地址,散列函数为:
H(key)=keyH(key)=a×key+b)H(key) = key\quad 或\quad H(key) = a \times key + b)
式中,ab为常数。这种方法计算最简单,且不会产生冲突。它适合关键字的分布基本连续的情况,若关键字分布不连续,空位较多,则会造成存储空间的浪费

3.除留余数法

一种简单、最常用的方法,假定散列表表长为m,取一个不大于m但最接近或等于m的质数p,利用以下公式把关键字转换成散列地址。散列函数为:
H(key)=key%pH(key) = key\%p
除留余数法的关键是选好p,使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址,从而尽可能减少冲突

4.数字分析法

设关键字是r进制的数(如十进制),而r个数码在各位上出现的频率不一定相同,可能某些位上分布均匀一些,某种数码出现的机会均等;而在某些位上分布不均匀,只有某几种数码经常出现,此时应选取数码分布较为均匀的若干位作为散列地址
这种方法适合已知的关键字集合,若更换了关键字,则需要重新构造新的散列函数。

5.平方取中法

取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。
这种方法得到的散列地址与关键字的每位都有关系,因此使得散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数


Comment