7.5 数据结构——散列表的查找_基于链地址法的散列查找

7.5.1 散列表的基本概念

基本思想：记录的存储位置与关键字之间存在对应关系，Loc(i) = Hash(key)。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。这种对应关系f称为散列函数，又称为哈希（Hash）函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash Table）。

冲突：不同的关键字映射到同一个散列地址上。

使用散列表要解决好两个问题：

（1）构造好的散列函数，①所构造的散列函数尽可能简单，以便提高转换速度；②所构造的散列函数对关键字计算出的地址，应在散列地址中集中且均匀分布，以减少空间浪费。

（2）制定一个好的解决冲突的方案，查找时，如果从散列函数计算出的地址查不到关键字，应当一句解决冲突的规则，有规律地查询其它相关单元。

7.5.2 构造散列函数的方法

考虑因素：①执行速度，②关键字的长度，③散列表大小，④关键字的分布情况，⑤查找效率。

根据元素集合的特性构造：

（1）n个数据元素仅占用n个地址，虽然散列查找是以空间换取时间，但还是希望散列表的地址空间尽可能小。

（2）无论用什么方法存储，目的都是均匀地存放元素，避免冲突。

构造方法：

（1）直接定址法，（2）数字分析法，（3）平法取中法，（4）折叠法，（5）除留余数法，（6）随机数法

直接定址法：  Hash(key) = a*key + b （a、b为常数）

优点：以关键字key的某个线性函数为散列地址，不会产生冲突。

缺点：要占用连续空间，空间利用率低。

例：{100，300，500，700，800，900}，散列函数Hash(key) = key / 100. (a = 1/100, b = 0)。

 除留余数法： Hash(key) = key mod p (p是一个整数)

关键：如何选取合适的p?

技巧：设表长为m，取小于等于m的质数

例：{15，23，27，38，53，61，70}，散列函数：Hash(key) = key mod 7

7.5.3 处理冲突的方法

方法：（1）开放定址法，（2） 链地址法，（3）再散列法，（4）建立一个公共溢出区

1、开放定址法：

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。

例如：除留余数法，Hi = (Hash(key) + di) mod n di为增量序列

常用方法：

线性探测法： di 为 1，2，...，m-1线性序列

二次探测法： 二次序列

伪随机探测法：di为伪随机序列

线性探测法： Hi = (Hash(key) + di) mod m (1 <= i <= m)，其中m为散列表长度，di为增量序列，一旦冲突，就找下一个地址，直到找到空地址为止。

例：关键字集为{47，7，29，11，16，92，22，8，3}，散列表长度m = 11，散列函数为Hash(key) = key mod 11，拟用线性探测法处理冲突。

解析：

（1）47、7均是由散列表得到没有冲突的散列地址；

（2）Hash(29) = 7，散列地址有冲突，需要寻找下一个空的散列地址，由H1 = (Hash(29) + 1) mod 11 = 8，散列地址8为空，因此将29存入到8的位置；

（3）11、16、92均是由散列表得到没有冲突的散列地址；

（4）22、8、3同样在散列地址上有冲突，也需要由Hi找到空的散列地址。

二次探测法：

关键字集为{47，7，29，11，16，92，22，8，3}，设散列函数为Hash(key) = key mod 11，

Hi = (Hash(key) + di) mod m，其中m为散列表长度，m要求是某个4k+3的质数，di为增量序列。

伪随机探测法：Hi = (Hash(key) + di) mod m (1 <= i <= m) ，其中m为散列表长度，di为伪随机序列。

2、链地址法

基本思想：相同散列地址的记录链成一单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表头指针存储起来，形成一个动态的结构。

例如：一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），散列函数为Hash(key) = key mod 13。

 链地址法建立散列表的步骤：

（1）取数据元素的关键字key、计算其散列函数值（地址），若该地址对应的链表为空，则将该元素插入此链表，否则执行步骤（2）解决冲突。

（2）根据选择的冲突处理方法，计算关键字key的下一个存储地址，若该链表对应的链表不为空，则利用链表的头插法或尾插法将该元素插入此链表中。

7.5.4 散列表的查找

给定值查找值k，查找过程：

 7.5.5 散列的查找效率分析

使用平均查找长度ASL来衡量查找算法，ASL取决于（1）散列函数，（2）处理冲突的方法，（3）散列表的装填因子α

α = 表中填入记录数 / 哈希表的长度

α越大，表中记录数越多，说明表填得越满，发生冲突得可能性就越大，查找是比较次数越多。

 链地址法

 线性探测法

 伪随机数法