哈希表(散列表)查找的详解

    xiaoxiao2021-03-25  6

    前言

    博客编写人:Willam 博客编写时间:2017/3/29 博主邮箱:2930526477@qq.com(有志同道合之人,可以加qq交流交流编程心得)

    1、哈希表查找介绍

    哈希表的代码实现

    我之前介绍两种方向的查找算法:

    静态查找算法(折半查找、插值查找、斐波那契查找、分块查找)动态查找算法(二叉排序树、平衡二叉树、B-树、B+树)

    但是,这些查找算法都是通过从表头开始,挨个挨个的比较记录,才得到我们需要查找的关键字的内存存储位置,然后我们现在就想是否可以直接通过关键字key就可以得到我们的内存地址了?这个肯定是有的,那就是今天我们要介绍的哈希表查找。

    哈希表查找过程中,我们是通过记录存储位置和关键字构建一个确定的关系f,使得每个关键字key对应一个存储位置f(key),我们称这个为散列技术。其中,这个f我们称为散列函数或者哈希函数。

    通过散列技术将记录存储在一块连续的存储空间中,这块连续的空间称为散列表或者哈希表。

    2、有关哈希表查找的思考

    思考一:哈希表查找的场景

    哈希表最适合查找与给定的值相等的记录。但是比如如果我们需要在一个十几个同学的哈希表中,查找某个同学,如果使用关键字“男”去查找,你会发现会出现很多条记录,无法达到我们的要求。 另外,我们需要查找一个班级18~28岁之间的同学,也是无法使用哈希表查找完成的,想要对记录进行排序,也是不可行的。.

    思考二:哈希函数计算某两个关键字的值相等,咋办? 其实,这个问题也是我们在建立哈希表时,需要解决的一个最大的问题,我们称这个问题为:冲突,就是两个关键字通过哈希函数得到的存储地址是一样的,这个时候,我们就需要通过冲突解决办法,来解决冲突,在解决冲突的同时也要保证我们的查找和插入效率问题,这个我们在后面会一一介绍。同时为了避免冲突,我们的散列函数也是很重要的,下面我们就介绍几种散列函数的构造方法

    3、散列函数的构造方法

    直接定址法

    其实就是直接通过取关键的字的某个线性值作为散列地址:

    f(key)=a*key+b,(a,b为常数)

    例如:我们要存储0-100岁的人口统计表,就可以采用散列函数为:

    f(key)=key 数字分析法 假设某公司的员工登记表以员工的手机号作为关键字。手机号一共11位。前3位是接入号,对应不同运营商 的子品牌;中间4位表示归属地;最后4位是用户号。不同手机号前7位相同的可能性很大,所以可以选择后4 位作为散列地址,或者对后4位反转(1234 -> 4321)、循环右移(1234 -> 4123)、循环左移等等之后作 为散列地址。

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

    平方取中法 假设关键字是1234,平方之后是1522756,再抽取中间3位227,用作散列地址。平方取中法比较适合于不 知道关键字的分布,而位数又不是很大的情况。

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

    比如关键字是9876543210,散列表表长是3位,将其分为四组,然后叠加求和:987 + 654 + 321 + 0 = 1962,取后3位962作为散列地址。

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

    除留取余数法 此方法为最常用的构造散列函数方法。 f(key) = key mod p (p≤m),m为散列表长。

    这种方法不仅可以对关键字直接取模,也可在折叠、平方取中 后再取模。根据经验,若散列表表长为m,通常p为小于或等于表长(最好接近m)的最小质数,可以更好的 减小冲突。

    随机数法 f(key) = random(key),这里random是随机函数。

    当关键字的长度不等时,采用这个方法构造散列函数是比较合适的。

    选取散列函数的参考:

    1. 计算散列地址所需的时间; 2. 关键字长度; 3. 散列表大小; 4. 关键字的分布情况; 5. 查找记录的频率。

    OK,到这里我们已经知道构造散列函数的方法,下面我们就要介绍如何处理冲突这个问题了。

    4、处理散列表的冲突问题的方法

    开放地址法

    开放地址就是一旦发生冲突,就去寻找下一个空的散列地址,只有散列表足够大,空的散列地址总能找到,并且记录它。至于如何寻找下一个空的散列地址,有三种方法:

    1. 线性探测法

    公式如下:

    f(key)=(f(key)+d)%m ,其中d取(0,1,2,3,4.....,m-1),m为散列表的长度

    如上图所示,散列表的长度为12,而且我们现在已经插入了部分数据了,下面我们继续插入37,。然后,我们使用散列函数计算37的散列地址:

    f(37)=f(37)=1

    但是我们发现1这个位置已经存放了35,那么我们就继续寻找下一个空的散列地址。

    f(37)=(f(37)+1)=2

    发现2这个地址没有内容,所以把37插入到这个位置,得如下图的结果:

    线性探测来解决冲突问题,会造成冲突堆积。所谓的冲突堆积就是比如说刚才的37,它本来是属于下标1的元素,现在却占用了下标为2的空间,这会造成待会我们需要存放本来要放在下标为2的元素时,再次发生冲突,这个冲突会一直传播下去,造成查找和插入效率都大大减低。

    2 .二次探测法

    公式如下:

    f(key)=(f(key)+d)%m, ,其中d取(0^21^2,-1^2,2^2,-2^2,3^2,-3^2,4^2,-4^2...,q^2,-q^2),q<=m/2,m为散列表的长度

    其实,这个是对线性探测的一个优化,增加了平方可以不让关键字聚集在某一块区域

    例如,我们对刚才的那个散列表,插入一个元素:7,通过二次探测的散列函数计算得到的散列地址为:

    f(7)=f(7)=7

    但是,我发现下标为7的位置已经存放了元素:67,所以我需要寻找下一个存储地址:

    f(7)=(f(7)+1^2)=8

    哎呀,突然发现下标为8的地址也存放了56这个元素,所以我们只能继续往下寻找下一个存储地址:

    f(7)=(f(7)+(-1^2))=6

    嗯,发现下标为6的这个地址空间还是空的,所以我就把7插入到这个位置,得到如下结果:

    3.随机探测法

    公式:

    f(key)=(f(key)+d)%m, d为随机数列,而m为表长

    在实际程序中应预先用随机数发生器产生一个随机序列,将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序,从而可以避 免或减少堆聚。

    再散列函数法(多重散列法)

    公式如下:

    f(key)=RH(key),

    其中RH就是不同的散列函数,这些散列函数可以是我们介绍的所有散列函数,只要其中一个发生了冲突,就马上换一个散列函数,知道冲突解决。缺点就是增加了很多计算时间

    链地址法

    所谓的链地址法,其实就是当发生冲突时,我还是把它存放在当前的位置,只是每个位置都是使用链表来存放同义词,这个思路和图的邻接表存储方式很相似。如下图所示:

    公共溢出区法 所谓的公共溢出区法,其实就是把那些冲突的元素直接追加到另外一个溢出表中,如下图所示:

    所以,我们在查找的时候,如果在基本表没哟找到,那么就只能去溢出表中进行顺序查找。这个方法比较适合冲突元素少的情况。

    总结: 刚刚我们介绍了,几种冲突的解决办法,在实际的应用中,我们需要根据实际的情况,选择合适的冲突解决办法。

    哈希表的代码实现

    转载请注明原文地址: https://ju.6miu.com/read-200104.html

    最新回复(0)