哈希函数(二)-基数转换法、哈希冲突、开放地址法

哈希函数(二)-基数转换法、哈希冲突、开放地址法

基数转换法

基数转换法:将关键字看成另一种进制的数再转换成原来进制的数,然后选其中几位作为哈希地址。

比如,将关键字看作是13进制的数,再将其转变为10进制的数,然后将其作为哈希地址。

以343246为例,计算方式如下:

(343246)13=3∗135+4∗134+3∗133+2∗132+4∗131+6∗130=(1235110)10


哈希冲突

哈希冲突不同的关键字通过同一个哈希函数可能得到同一哈希地址,即 key1 ≠ key2,而 Hash(key1) = Hash(key2),这种现象称为哈希冲突。

理想状态下,我们的哈希函数是完美的一对一映射,即一个关键字(key)对应一个值(value),不需要处理冲突。但是一般情况下,不同的关键字 key 可能对应了同一个值 value,这就发生了哈希冲突。

设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类:「开放地址法」和「链地址法」

开放地址法

开放地址法:指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时,处理冲突时需要尝试另外的单元,直到找到空的单元为止。

当发生冲突时,开放地址法按照下面的方法求得后继哈希地址,H(i)=(Hash(Key)+F(i))%m,i=1,2,3,…,n(n≤m−1)

  • H(i) 是在处理冲突中得到的地址序列。即在第 1 次冲突(i = 1)时经过处理得到一个新地址 H(1),如果在 H(1) 处仍然发生冲突(i = 2)时经过处理时得到另一个新地址 H(2) …… 如此下去,直到求得的 H(n) 不再发生冲突
  • Hash(key) 是哈希函数,m 是哈希表表长,取余目的是为了使得到的下一个地址一定落在哈希表中
  • F(i) 是冲突解决方法,取法可以有以下几种:
    • 线性探测法F(i)=1,2,3,…,m−1
    • 二次探测法F(i)=12,−12,22,−22,…,n2(n≤m/2)
    • 伪随机数序列F(i) = 伪随机数序列

开放地址法举例

举例说明一下如何用以上三种冲突解决方法处理冲突,并得到新地址 H(i)。例如,在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录(哈希函数为 Hash(key) = key % 11)。

现在将插入关键字为 38 的新纪录,根据哈希函数得到的哈希地址为 5,产生冲突。接下来分别使用这三种冲突解决方法处理冲突。

哈希函数(二)-基数转换法、哈希冲突、开放地址法
  • 使用线性探测法:得到下一个地址 H(1)=(5+1)%11=6,仍然冲突;继续求 出 H(2)=(5+2)%11=7,仍然冲突;继续求出 H(3)=(5+3)%11=8,8 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 8 的位置。
哈希函数(二)-基数转换法、哈希冲突、开放地址法
  • 使用二次探测法:得到下一个地址 H(1)=(5+1∗1) ,仍然冲突;继续 求出 H(2)=(5−1∗1) ,4 对应的地址为空,处理冲突过程结束,记录 填入哈希表中序号为 4 的位置。
哈希函数(二)-基数转换法、哈希冲突、开放地址法
  • 使用伪随机数序列:假设伪随机数为 9,则得到下一个地址H(1)=(9+5),3 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 3 的位置。
哈希函数(二)-基数转换法、哈希冲突、开放地址法
原文来自的https://zhuanlan.zhihu.com/p/496515259 ,如有侵权请联系作者修行黑钻VIP永久会员删除,谢谢!
(4)
上一篇 2023年2月7日 23:39
下一篇 2023年3月1日 23:25

相关推荐

发表回复

登录后才能评论

评论列表(1条)

  • 我是自愿种绣球花的的头像
    我是自愿种绣球花的 2023年2月19日 12:15

    学习

在线客服 QQ交流群
返回顶部