Hash冲突之开放地址法

慧能

一尘,国庆节过完了,还记得Hash函数吗?

当然记得了,Hash函数就是将任意长度的输入转化成固定长度的输出的一类函数

一尘

比如说我的输入是任意一个自然数(0,1,2,3...),而我要求经过一个函数后我的输出的数的范围要在0-9这样一个范围之间。

很容易想到,我们可以使用Hash函数:

其中key就是输入

在哈希表(散列表)里,Hash函数的作用就是将关键字Key转化为一个固定长度数组的下标,以便存取键值对<Key,Value>

慧能

不错,还记得,那当多个键(key)经过Hash函数处理后落在了同一个位置时怎么办呢?

我记得上次师傅给我讲过链地址法

一尘

链地址法可看:神速Hash

开放地址法

慧能

记性不错,但还有一种方法叫开放地址法

哦?开放地址

一尘

所谓开放地址法就是发生冲突时在散列表(也就是数组里)里去寻找合适的位置存取对应的元素。

这个合适的位置该怎么找呢?

一尘

慧能

问的好,为师给你说说几种方法

线性探测法

最容易想到的就是当前位置冲突了,那我就去找相邻的下一个位置。

就拿放入元素举例吧,当你放入<a,101>到下标为2的位置后,另一个<c,103>键值对也落入了这个位置,那么它就向后依次加一寻找合适的位置,然后把<c,103>放入进去。

我们把这种方法称作线性探测法,我们可以将Hash以及寻找位置的过程抽象成一个函数:

所以关键字要进行查找或者插入,首先看(hash1(key)+0)%7 位置是自己最终的位置吗?如果有冲突,就探测(查看)下一个位置:(hash1(key)+1)%7。依次进行

所谓探测,就是在插入的时候检查哪个位置可以插入,或者查找时查找哪个位置是要查找的键值对,本质就是探寻这个键值对最终的位置。

但是这样会有一个问题,就是随着键值对的增多,会在哈希表里形成连续的键值对

这样的话,当插入元素时,任意一个落入这个区间的元素都要一直探测到区间末尾,并且最终将自己加入到这个区间内。这样就会导致落在区间内的关键字Key要进行多次探测才能找到合适的位置,并且还会继续增大这个连续区间,使探测时间变得更长,这样的现象被称为“一次聚集(primary clustering)”

这可如何是好

一尘

平方探测法

慧能

我们可以在探测时不一个挨着一个地向后探测,我们可以跳跃着探测,这样就避免了一次聚集。

其实我们可以让它按照 i^2 的规律来跳跃探测

这样的话,元素就不会聚集在某一块区域了,我们把这种方法称为平方探测法

同样我们可以抽象成下面的函数:

其实可以扩展到更一般的形式:

虽然平方探测法解决了线性探测法的一次聚集,但是它也有一个小问题,就是关键字key散列到同一位置后探测时的路径是一样的。

这样对于许多落在同一位置的关键字而言,越是后面插入的元素,探测的时间就越长。

这种现象被称作“二次聚集(secondary clustering)”,其实这个在线性探测法里也有。

这种现象出现的原因是由于对于落在同一个位置的关键字我们采取了一个依赖 i 的函数(i或者i^2)来进行探测,它不会因为关键字的不同或其他因素而改变探测的路径。那么我们是不是可以让探测的方法依赖于关键字呢?

双散列

答案是可以的,我们可以再弄另外一个Hash函数,对落在同一个位置的关键字进行再次的Hash,探测的时候就用依赖这个Hash值去探测,比如我们可以使用下面的函数:

经过hash1的散列后,会定位到某一个地址,如果这个地址冲突,那么就按照1*hash2(key)、2*hash2(key)... 的偏移去探测合适的位置。

由于Hash2函数不同于Hash1,所以两个不同的关键字Hash1值和Hash2值同时相同的概率就会变得非常低。

这样就避免了二次聚集,但同时也付出了计算另一个散列函数Hash2的代价。

如果hash2(key)=0,那探测不就一直在原地不动,失效了吗?

一尘

慧能

聪明,所以hash2函数在选择的时候要避免这种情况。

原来解决冲突还有这种方法,看来国庆后要加倍努力了。

一尘

慧能

嗯嗯,看好你

-END-

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-10-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏coding for love

JS入门难点解析2-JS的变量提升和函数提升

(注1:如果有问题欢迎留言探讨,一起学习!转载请注明出处,喜欢可以点个赞哦!) (注2:更多内容请查看我的目录。)

1133
来自专栏CSDN技术头条

不到40行代码构建正则表达式引擎

原文:Build a Regex Engine in Less than 40 Lines of Code (作者:Nick Drane ,翻译:Diwei) ...

1976
来自专栏皮皮之路

【JDK1.8】Java 8源码阅读汇总

3897
来自专栏企鹅号快讯

30分钟学会用Python编写简单程序

参与文末每日话题讨论,赠送异步新书 异步图书君 学习目标 知道有序的软件开发过程的步骤。 了解遵循输入、处理、输出(IPO)模式的程序,并能够以简单的方式修改它...

60710
来自专栏老马说编程

计算机程序的思维逻辑 (9) - 强大的循环

循环 上节我们介绍了流程控制中的条件执行,根据具体条件不同执行不同操作。本节我们介绍流程控制中的循环,所谓循环就是多次重复执行某些类似的操作,这个操作一般不是...

2068
来自专栏博岩Java大讲堂

Java集合--Queue队列介绍

3618
来自专栏郭霖

Android最佳性能实践(三)——高性能编码优化

在前两篇文章当中,我们主要学习了Android内存方面的相关知识,包括如何合理地使用内存,以及当发生内存泄露时如何定位出问题的原因。那么关于内存的知识就讨论到这...

20910
来自专栏北京马哥教育

Python 的正则表达式彩蛋

虽然我觉得在 Python 的标准库里的确有不少很恶心的库,但是 re 库肯定不属于这种。尽管它真的有年头没有更新了,但是在我看来,仍不失为动态语言中最好的库...

2907
来自专栏鸿的学习笔记

python新手应注意的一些小问题

最重要的是看你公司喜欢哪个版本的python。。。。对于你个人而言,python2与python3的差别你可以忽略。。。。 一.注意pep8的编程风格,请记住...

4542
来自专栏九彩拼盘的叨叨叨

如何给函数取个合适的名字

Quora 和 Ubuntu Forums thread 上的 4500 个程序员对上面的问题进行投票。49%的程序员认为给函数,变量等命名是最难的任务。

712

扫码关注云+社区

领取腾讯云代金券