本文共 2071 字,大约阅读时间需要 6 分钟。
一、基本概念
- 主要有散列函数和散列表的定义,以及散列函数的关键字冲突现象。
1、散列函数:
将查找表中关键字映射称关键字对应的地址的函数
,记为Hash(key)=Addr
。
2、冲突与同义词
- 冲突:
指散列函数将不同关键字映射到同一块地址上
。 - 同义词:
指导致散列函数发生冲突的不同关键字
。
3、散列表
- 散列表,
指根据关键字而直接进行访问的数据结构
,即散列表建立了关键字和存储地址之间的直接映射关系
。 - 理想的散列表的时间复杂度为常数阶,与散列表中的元素个数无关。
二、构造散列函数
- 构造散列函数的方法有:
直接定址法、除留余数法、数字分析法和平方取中法
。 - 无论是哪种方法都必须达到: ①
散列函数定义域必须满足涵盖所有待存储的关键字,值域大小与散列表大小即地址范围相关
; ② 散列函数计算出来的值,即地址应遵从等概率、均匀分布在整个地址空间中,以减少冲突
; ③ 散列函数应尽可能简单,应具有高效性,快速计算出任一关键字对应的地址
。
1、直接定址法
直接取关键字的某个线性函数值为散列地址
,此时散列函数为: H(key) = key 或 H(key) = a*key + b
- 适于
关键字分布基本连续
的情况,不适于关键字分布不连续的情况——空位较多,浪费存储空间。
2、除留余数法
最简单、常用的方法
- 若散列表长 m,取不超过 m 的最大质数 p,按照:
H(key) = key%p
- 将关键字转换成散列地址。此时,p 的选取将制约着算法的效率。
3、数字分析法
- 若关键字为 r 进制数,r 个数码在每位上出现的概率不一样,此时选择数码分布较均匀的若干位作为散列地址。
- 此法适用于已知的关键字集合,若更好关键字,则需要重构散列函数。
4、平方取中法
取关键字平方的中间几位作为散列地址
,取多少位视具体情况而定。此法得到的散列地址与关键字的每位都有关系,故散列地址分布较均匀,适用于关键字每位取值都不够均匀或均小于散列地址所需的位数。
三、处理冲突的操作
- 所有处理散列函数产生的冲突的关键字的操作,基本都是遵循:
为该关键字寻找下一个可使用的空的散列地址
。
1、开放定址法
- 指
可存放新表项的空闲地址既向他同义词表项开放,又向它的非同义词表项开放
,递推公式: Hi = (H(key) + di)%m - di 表示增量序列,具体增量序列便有具体的对应方法:
线性探测法、平方探测法、再散列法或伪随机序列法
。
1.1、线性探测法
- di 为从零开始的、公差为一的等差递增序列时,当发生冲突,则
顺序查看表中下一单元,直到找到可用的空闲单元或查遍全表;因此当探查到表尾地址时,并不是结束循环而是回到表首
。 - 此法的缺点在于容易产生
大量元素在相邻的散列地址上堆积起来
,从而降低查找效率。
1.2、平方探测法
- 也叫
二次探测法
。 - 当 di=02, 12, -12, 22, -22, … , k2, -k2 (k<=m/2)时。
- 此时,散列表长度必须是一个可以表示成
4k+3
的素数。 - 该法优点在于能够较好地处理冲突,且不发生元素的在某一段散列地址上的堆积;但不能探测到散列表上所有单元,至少能探测到一半单元,是其不足之处。
1.3、再散列法
- 又叫
双散列法
。 - 当 di = Hash2(key) 时。
- 使用两个散列函数,当第一个散列函数发生冲突时,用第二个散列函数计算该关键字的地址增量,表达式如下: Hi = (H(key) + i*Hash2(key))%m
- 初始探测位置为 H0 = H(key)%m。i 表示冲突次数,初始为 0.
- 此法经过 m-1 次探测就会遍历表中所有位置,回到初始位置。
1.4、伪随机序列法
1.5、注意事项
- 使用开放定址法,不能随便删除存储单元中的内容即已有元素,否则会造成其他具有相同散列地址的元素的查找地址。此时,若要删除元素,则需要附设一个删除标记,进行逻辑删除,但多次删除后散列表似乎看起来很满,实际上却又许多位置并未利用,故而需要定期维护散列表,把附设有删除标记的元素进行物理删除。
2、拉链法
- 此法的思想是,
将发生冲突的同义词存储在同一个线性链表中
,该线性链表由散列地址唯一标识。 - 此法适用于经常进行插入和删除操作的情况。
四、散列查找
- 散列表的查找过程与构造过程类似,根据给定的关键字用对应的散列函数计算出相应的散列地址,其过程步骤一般如下: 初始化:Addr=Hash(key); ① 检测表中地址为 Addr 的位置上是否有记录,若无则返回查找失败;若有则将元素值与key进行比较,若相等则返回查找成功,否则转到步骤②; ② 用给定的处理冲突的方法计算下一个散列地址,并把 Addr 置为此地址,转入①。
五、影响散列表效率的因素
- 影响散列表查找效率的因素有
散列函数、处理冲突的方法和装填因子
。 - 装填因子 α:定义为 α=(表中记录数n)/(散列表长度m)
- 散列表的平均查找长度依赖于散列表的装填因子,装填因子越大则装填的记录越满,而发生冲突的可能性也越大;反之,则发生冲突的可能性越小。
转载地址:http://yhqgn.baihongyu.com/