精华内容
下载资源
问答
  • 根据设定的哈希函数及处理冲突方法将查找表中各数据元素存储在一段有限的连续空间中,即得哈希表。 这里有两个比较重要得问题:哈希函数的构造、处理冲突方法哈希函数的构造方法 1、直接定址法 直接根据数据...

    哈希表

    哈希表的思想就是在待查记录的关键字值和它的存储位置之间建立一个确定的对应关系则查找时不必再进行关键字值间的比较。
    根据设定的哈希函数及处理冲突的方法将查找表中各数据元素存储在一段有限的连续空间中,即得哈希表。

    这里有两个比较重要得问题:哈希函数的构造、处理冲突的方法。

    哈希函数的构造方法

    1、直接定址法

    直接根据数据的值来映射到地址,比如对数字10、11、12、13…可以将其映射到一块连续的内存中。

    2、数字分析法

    根据数据的某些数字(比如百位和十位数字)来映射到地址。

    3、平方取中法

    若关键字比较短,则可先对关键字值求平方,然后取运算结果的中间几位为哈希地址。

    4、折叠法

    将关键字值分割成位数相同的几个部分,然后取这几部分的叠加和(舍去进位)作为哈希地址。

    5、除留余数法

    H(key)=key%13

    处理冲突的几种方法

    处理冲突是指对于一个待插入哈希表的数据元素,若按给定的哈希函数求得的哈希地址已被占用,则按一定规则求下一哈希地址,如此重复,直至找到一个可用的地址以保存该元素。

    1、开放地址法

    在这里插入图片描述
    基本思想是,如果映射的地址被占用了,在哈希函数值的基础上加上指定数值,这样就可以把冲突的地址给错开,然后重新开辟新的地址用来存储。根据增量值的不同,分为线性探测再散列和二次探测再散列。

    线性探测例子:
    下面在映射18时,发现18%7=4,但是哈希表的4已经被占用,对4进行加1,映射到5,发现5是空的,放到位置5即可。
    在这里插入图片描述
    当值为34时,发现哈希函数值为6,但是已经被占用,这时对其加1,发现0的位置再次被占用,那就在此基础上再次加1(实际就是加2),发现1位置是空的,正好可以放置元素。
    在这里插入图片描述
    这个例子也是如此:
    在这里插入图片描述

    关于二次探测方式,和线性探测方式相似~
    在这里插入图片描述

    比如对68来说,68%11=2,结果2处被占用,这时对2+12=3,结果发现3也被占用,这时对3-12=2,发现2再次被占用,这时对2+2^2=6,6位置未被占用,放入即可。

    2、链地址法

    将所有按给定的哈希函数求得的哈希地址相同的关键字存储在同一线性链表中,且使链表按关键字有序(比如大小等属性)。
    在这里插入图片描述

    3、公共溢出区

    若关键字所对应的哈希地址已被占用,则保存到公共溢出区中。一般在开辟地址的时候会产生哈希地址和公共溢出区两块~
    在这里插入图片描述在这里插入图片描述

    4、再哈希法

    再哈希法的基本思想是同时构造多个不同的哈希函数:
    Hi=RH1(key),i=1,2,3,…k
    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)…,直到冲突不再产生。这种方法不易产生聚焦,但增加了计算时间~

    如在哈希表中查找元素

    在哈希表中查找数据元素的过程与将数据元素插入哈希表的过程基本一致,即:
    根据待查关键字值,按给定的哈希函数,求哈希地址;若该地址上无数据元素,则查找失败。
    若地址上有数据元素则进行关键字值间的比较;
    若相等,则查找成功;
    若不等,则按冲突处理方法求下一可能的存储地址。

    虽然哈希表在关键字值与存储位置间建立了映像,但由于冲突的存在,查找时仍需进行关键字之间的比较,因此仍以查找成功时的平均查找长度和查找不成功时的比较次数作为衡量查找效率的依据。

    展开全文
  • 哈希方法中使用的转换函数称为哈希函数,按这个思想构造的表称为哈希表(散列表) 从上面的概念,构建哈希表关键是有哈希函数。那么我们来看看常见的哈希函数有哪些? 常见哈希函数: 直接定制法: 取...

    哈希的概念: 

    哈希表查找的基本思想是:根据当前带查找数据的特征,以记录关键字为自变量,设计一个哈希函数,以该函数按关键码计算该元素的存储位置,并按此存放;查找时,有同一个函数对给定值key计算地址,将key与地址单元中元素关键码进行比较,确定查找是否成功。哈希方法中使用的转换函数称为哈希函数,按这个思想构造的表称为哈希表(散列表)

     

    从上面的概念,构建哈希表关键是有哈希函数。那么我们来看看常见的哈希函数有哪些?

     

    常见哈希函数:

    直接定值法:

    • 取关键字的某线性函数为哈希地址:Hash(Key) = A*Key +B ;

    eg: 4 6 7 8 9          Hash(Key) =Key

            4   6 7 8 9

     

                                                          0            1         2      3          4         5          6          7            8              9 

    直接定制法,比较好的一点就是简单,直接映射;  不过也有缺点:映射的数据集合应该是分布集中,连续的 

     eg:1    100000000000

    如果只映射两个数1和一个超大的数,直接映射,我们需要开很大的空间,并且空间严重浪费,这就是直接定制法的巨大缺陷

     除留余数法:

    •        假设散列长度为m,取一个不大于m但最接近或者等于m的质数p作为除数
    •        按照哈希函数 Hash(key) =key%p,将关键码转换成哈希地址

     

     除留余数法,很大程度解决了直接定制法的空间浪费问题。

     不常用的哈希函数

     平方取中法

    •             先计算关键字的平方,再抽取中间的几个数作为哈希地址

      eg :          

    关键字 平方 哈希地址(抽取了中间3位)
    1234 1522765 227
    4321 18671041 710(671也可以)

     用平方取中法,关键字的位数不能太大。太大的话,最早的情况,平方之后如果超过long  long,很难操作

    折叠法

    •   将关键字从左到右分隔成位数相等的几部分(最后一部分位数可以短一些)
    •  再将这几部分叠加求和,并按散列表表长,取后几位最为散列地址   

     

     折叠法可以适用于关键字位数较大的情况

     随机数法:

    •  选择一个随机函数,取关键字的随机函数值为哈希地址;
    • 即Hash(key)=random(key)
    • 通常应用于关键字长度不等时采用这种方法

     数字分析法:

    •       如果有n个d位数,每一位上可能由r中不同的符号,这种r中不同的符号在各个位上出现的概率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀,只有某几种符号常见。
    • 我们就可以根据散列表的大小,选择其中各个符号分布均匀的若干位作为散列地址。
    • 通常用于关键字位数表加大,并且实现直到关键字的若干位分布均匀的情况

     总之,设计哈希函数的目的,一是为了映射到哈希表上,二是为了减少产生哈希冲突的可能性(无法完全避免哈希冲突) 

     

    可能刚才提到哈希冲突,大家有点迷惑什么是哈希冲突?

    接下来,我们就讨论一下哈希冲突及其解决方法。我们主要讨论的哈希函数为直接定制法和除余留数法。

    哈希冲突

    哈希的概念简单的说就是将关键字映射到表(哈希表)上的某个位置,查询的时候,到这个位置上去找;

    那哈希冲突呢? 冲突,就是我们常说的矛盾。即多个关键字,经过哈希函数计算,映射到相同的位置,此时就有了矛盾,这个位置该存哪个关键字呢!这也就是我们说的哈希冲突 

     以我们上文用到的除余留数法为例,理解哈希冲突

     上面我们也提到了哈希冲突是不可避免的(当然,直接定值法,进行一 一映射的情况,可以视为特殊),所以我们需要解决方法:

    哈希冲突的解决方法

    闭散列(开放定址法):

     当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把关键字存放到冲突位置中的“下一个”空位置中去。

                如何寻找下一个空位置呢?

       线性探测:

               从发生冲突的位置开始,依次向后探测,直到寻找下一个空位置为止

      二次探测:

             从发生冲突的位置开始,找下一个空位置,查找空位置的方法为H_{i}=(H_{0}+i^2)%mH_{0}+i^2)%m,i=1,2,3........;m是哈希表大小,H_{0}是经过关键字计算后的出的哈希地址

    开散列(链地址法、开链法)

     对关键字集合用散列函数计算散列地址,具有相同地址的关键码归于同一个子集合,每一个子集和称为一个桶,各个桶中的元素通过一个单链表连接起来,各链表的头结点存储在哈希表中。

    举例理解上面三种解决哈希冲突的方法

    线性探测:

    从4这个位置开始查找下一个空位置,到5这个位置的时候,发现没有关键字存放,则把444放在5这个位置,倘若又要插入4444,则又要从4这个位置查找下一个空位置,发现6这个位置没有关键字存放,则把4444放到6这个位置;

     

    看图解:

     二次探测:

    当插入444时,i=1,经过计算,判断5的位置是否有关键字存放,发现没有,则将444存放在5这个位置

    当在插入4444时,i=2,经过计算,判断8的位置是否有关键字存放,发现没有,则将4444存放在8这个位置

     

     开链法:

    桶结构,将相同关键字存放在一个桶上。

     

     

     

    注:如果本篇博客有任何错误和建议,欢迎伙伴们留言,你快说句话啊!

     

     

    展开全文
  • 目录哈希函数的构建: 哈希表:通过关键码来映射到值的一个数据结构; 哈希函数:键与值映射的一个映射关系; 哈希函数的构建: 常用方法: 1、直接寻址法:f(x) = kx+b (k、b都是常数) ,一旦确定了哈希函数,那么...

    哈希表:通过关键码来映射到值的一个数据结构;
    哈希函数:键与值映射的一个映射关系;

    哈希函数的构建:

    常用方法
    1、直接寻址法:f(x) = kx+b (k、b都是常数) ,一旦确定了哈希函数,那么添加、获取元素都需要通过这个哈希函数;
    2、除留余数法:f(x) = x%k (k是常数,k <= m (m为存储位置长度)) ;

    其他几种方法:

    方法名 说明 适合情况
    直接寻址法 f(key) = key 或者 f(key) = a*key + b 事先知道关键字的分布情况,查找表较小且连续
    数字分析法 根据实际问题自己创造一个能将关键字散列表的各位置的散列函数 事先知道关键字的分布情况且关键字的若干位分布较均匀
    平方取中法 先把关键字平方,然后取得到的结果的中间几位当哈希值 不知道关键字的分布,而位数又不是很大的情况
    折叠法 把关键字分成较小的几组数据,求和,取得到结果的后几位当哈希值 不知道关键字的分布,且关键字位数较多情况
    除留余数法 f(key) = key%n ( n≤m )m为表长(容量),n 为不大于 m 的素数,或是不含 20 以下的质因子 一般都可以,所以是最常用的方法
    随机数法 f(key) = random(key) 关键字长度不等的时候

    哈希冲突:由于哈希函数构造不当,通过同一个哈希函数把两个不同的数哈希到了同一个位置;m != n ---->f(m) = f(n);哈希冲突无法避免,但可以减少(改变合适的哈希函数还是有可能发生哈希冲突,但冲突的数据会大大减少)。

    解决哈希冲突:
    常用方法
    1、链地址法:数组+链表(散列表)
    2、探测法:① 线性探测:p(i) = i+c ②非线性探测:p(i) = i+random();

    其他几种方法:

    方法名 说明 注解
    开放地址法 一旦发生了冲突,就去寻找下一个地址,只要散列表足够大,空的地址总能够找到,找到则记录存入 找地址的方法有:线性探测法、二次探测法、随机探测法
    再散列函数法 发生散列地址冲突时,换一个散列地址计算,相信总会有一个函数是可以解决冲突的 这种方法可以使关键字不产生聚集,但增加了计算时间
    链地址法 数组+链表 这种方法绝不会出现找不到地址的情况,但是查找时要遍历链表
    公共溢出区法 就是把冲突的关键字放在一个新表中 这个方法的查找性还是比较高的
    展开全文
  • 哈希函数的构造方法有:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法; 处理冲突方法: 开放地址法(线性探测、二次探测、伪随机探测)、链地址法、多重散列法 开放定址法解决冲突的做法...

    哈希函数的构造方法有:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法;

    处理冲突的方法:

    开放地址法(线性探测、二次探测、伪随机探测)、链地址法、多重散列法

    开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定 的关键字,或者碰到一个开放的地址(即该地址单元为空)为止。 

    与开放定址法相比,拉链法有如下几个优点: 
    (1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短; 
    (2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况; 
    (3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间; 
    (4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。  

    展开全文
  • 哈希函数冲突解决

    2019-03-03 22:19:51
  • 哈希表是key-value类型的数据结构, 可以理解为一个键值需要按照一定规则存放的数组, 而哈希函数就是这个规则 字典本质上是一个散列表(总有空白元素的数组, python至少保证1/3的数组是空的), 字典中的每个键都占用一...
  • 哈希函数H(K)=3Kmod11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按下述两种解决冲突方法构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和...
  • 3. 解决哈希冲突方法:数组扩容,设计优秀的哈希函数,开放寻址法和链表法为哈希值找到合适的映射。 4. 开放寻址法,插入、查找、删除都需要相同的寻址逻辑,所以时间复杂度一样。数组中元素越多,空闲位置越少,...
  • 哈希函数的构造方法 常用的构造哈希函数方法有:  1.直接定址法  取关键字或关键字的某个线性函数值为哈希地址。即: H(key)=key 或 H(key)=a·key+b  其中a和b为常数(这种哈希函数叫做自身函数)。 ...
  • HashMap是基于哈希表的Map接口的实现 所以先来了解一下哈希表吧~ 哈希表(散列表)是根据关键码来映射到值的一个数据结构,这个映射函数叫哈希函数...构造哈希函数方法 直接寻址法 取关键字或关键字的某个线性...
  • ②哈希冲突是指哈希函数算出来的地址被别的元素占用了,也就是,这个位置有人了。好的哈希函数会尽量避免哈希冲突。 那么发生了哈希冲突,要怎么解决呢? 解决哈希冲突有以下几种方法: ①开放定址法: 这种方法也...
  • Hash哈希 1.基本概念   Hash,也叫哈希或散列,就是把任意长度...  根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上,并以关键字在地址区间中的象作为记录在表中的存储位置,这种...
  • 哈希函数的构造方法

    2015-03-26 16:30:43
    哈希函数的构造方法 本文阐述了哈希函数的构造方法有很多,但应注意两个原则:第一,函数值应在1至记录总数之间;第二,尽可能避免冲突。 设要存放的数据元素有n个,存放数据元素的内存单元有m个,设计哈希...
  • Java笔试题常见知识点:哈希函数和哈希冲突哈希函数的构造方法有哪些?产生哈希冲突的影响因素有哪些:处理冲突方法1.开放定址法(1)线性探测再散列(2)二次探测再散列2.再哈希法3.链地址法4.建立一个公共溢出区...
  • 常用的哈希函数构造方法
  • 哈希函数的生成方法

    千次阅读 2017-07-30 21:22:49
    本文阐述了哈希函数的构造方法有很多,但应注意两个原则:第一,函数值应在1至记录总数之间;第二,尽可能避免冲突。 设要存放的数据元素有n个,存放数据元素的内存单元有m个,设计哈希函数的目标就是要使通过哈希...
  • 哈希函数的构造方法 1.1直接定址法 取关键字或关键字的某个线性函数值为哈希地址。即: H(key)=key或H(key)=a*key+b (其中a和b为常数。) 由于直接定址所得地址集合和关键字集合的大小相同。因此,对于不同的...
  • 冲突解决办法 对于一个待插入哈希表的数据元素,若按给定哈希函数求得的哈希地址已被占用,则按照一定规则求下一个哈希地址,如此重复,直至找到一个可用的地址保存该元素。 1. 链表 Separate Chaining 写结构体的...
  • 哈希函数+解决冲突方法 构造方法 直接定址法,除留余数法 解决冲突方法 开放定址法:线性探测法,平方探测法 拉链法 1、散列表的若干术语 散列方法(杂凑法) 选取某个函数,依该函数按关键字计算元素的存储位置...
  • 哈希函数构造方法 1.直接定址法 取关键字或关键字的某个线性函数值为哈希地址,即: 或 2.数字分析法 3.平方取中法 取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数方法。一个数平方后的...
  • 注:本文注重对解决哈希冲突方法的介绍,而非对背后原理的介绍。 1、哈希冲突 当两个不同的数经过哈希函数计算后得到了同一个结果,即他们会被映射到哈希表的同一个位置时,即称为发生了哈希冲突。 在此我们不对哈希...
  • 虽然上文有提到怎么解释的开放地址法处理hash冲突,但是当时只是给了个简单的图,没有 详细讲解一下, 我当时有点不明白,回头查查资料,然后亲自动手,整理了一下。 然后我就三幅图详细讲解一下: 什么叫线性探测再...
  • 哈希冲突解决方法

    2019-03-22 10:19:08
    哈希冲突解决方法 哈希法的基本思想 先在元素的关键字k和元素的存储位置p之间建立一个对应关系H,使得p=H(k),H称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为H(k)的单元; 以后当查找关键字为k的...
  • 首先,什么是哈希表?什么又是哈希冲突?...②哈希冲突是指哈希函数算出来的地址被别的元素占用了,也就是,这个位置有人了。好的哈希函数会尽量避免哈希冲突。 那么发生了哈希冲突,要怎么解决呢? 解决哈希冲突...
  • 哈希方法 选取某个函数,依该函数按关键字计算元素的存储位置,并按此...通常关键字的集合比哈希地址集合大得多,所以经过哈希函数变换后,可能将不同的关键字映射到同一个哈希地址上,这种现象称为冲突。 映射到同一

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,796
精华内容 25,118
关键字:

哈希函数解决冲突的方法