7.1.4　哈希查找

1. 哈希技术的关键问题

① 哈希函数的设计；② 处理冲突的方法。

2. 哈希函数的构造方法

(1) 直接定址法：H(key)=key或H(key)=a·key+b

(2) 数字分析法。数字分析法又称为数字选择法,适用于下述场合:事先知道所有可能出现的键值,并且键值的位数比散列地址的位数多。在这种情况下可以对键值的各位进行分析,选择分布较均匀的若干位组成散列地址。

(3)除留余数法。除留余数法是一种简单有效的构造法。这种方法不要求事先知道全部键值。其作法：选择一个适当的正整数P，以键值除以P所得的余数作为散列地址，即令哈希函数H为：H(key) ＝ key % p

(4) 平方取中法。取关键字平方后的中间几位为哈希地址。

(5) 基数转换法。将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址，这方法又称为折叠法(folding)。

(6) 随机数法。选择一个随机函数random，以键值在该函数下的值作为散列地址：

H(key)=random(key)

3. 处理冲突的方法

(1)开放定址法；(2)再哈希法；(3)链地址法；(4)建立一个公共溢出区。

4. 效率分析

采用平均长度度量，查找关键字的比较次数取决于冲突的概率，有以下三个因素：(1)哈希函数是否均匀；(2)处理冲突的方法；(3)哈希表的装填因子。