5 散列(Hash)表

Wu Jun 2019-12-25 15:59:04
01 数据结构与算法 > 数据结构 > 03 查找

1 散列表查找定义

2 散列表查找步骤

  1. 在存储时,通过散列函数计算记录的散列地址,并按此散列地址存储该记录。
  2. 当查找时,通过同样的散列函数计算记录的散列地址,按此散到地址访问该记录 。

散列技术最适合的求解问题是查找与给定值相等的记录。

不适合一个关键字对应很多记录,不适合范围查找

3 散列函数的构造方法

好的散列函数两个原则:

  1. 计算简单
  2. 散列地址分布均匀

如果关键字是字符串,可以(通过ASCII 码或者 Unicoæ 码等)转化为某种数字来对待

1 直接定址法

需要事先知道关键字的分布情况,适合查找表较小且连续的情况。简单,但不常用。

取关键字的某个线性函数值为散列地址,即 f(key) = a * key + b (a、b 为常数)。

2 数字分析法

适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀,就可以考虑用这个方法。

抽取方法是使用关键字的一部分来计算散列存储位置的方法

3 平方取中法

平方取中法比较适合于不知道关键字的分布,而位数又不是很大的情况。

先平方,再取中间几位

4 折叠法

折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况。

折叠法是将关键字从左到右分割成位数相等的几部分,然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。

有时可能这还不能够保证分布均匀,不妨从一端向另一端来回折叠后对齐相加。

5 除留余数法

最常用的构造散列函数方法。

对于散列表长为 m 的散列函数公式为: f(key) = key mod p (p <= m)

不仅可以对关键宇直接取模,也可在折叠、 平方取中后再取模。

根据前辈们的经验,若散列表表长为 m , 通常 p 为小于或等于表长(最好接近 m ) 的最小质数或不包含小于 20 质因子的合数。

6 随机数法

合适关键字的长度不等。

选择一个随机数(伪随机),取关键字的随机函数值为它的散列地址。也就是 f(key) = random(key) 。

4 处理散列冲突的方法

1 开放定址法

开放定址法就是一旦发生了冲突, 就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。

$f_i( key ) = ( f ( key ) + d_i ) MOD m$

2 再散列函数法

事先准备多个散列函数,每当发生散到地址冲突肘,就换一个散列函数计算

3 链地址法

将所有关键字为同义词的记录存储在一个单链表中,在散列表中只存储所有同义词子表的头指针。

4 公共溢出区法

为所有冲突的关键字建立了一个公共的溢出区来存放

在查找时,对给定值通过散列函数计算出散列地址后,先与基本表的相应位置进行比对,如果相等,则查找成功;如果不相等,则到溢出表去进行顺序查找。

5 散列表查找实现

散列表的装填因子 = 填入表中的记录个数 / 散列表长度。