精华内容
下载资源
问答
  • 哈希冲突

    2019-11-30 15:49:48
    文章目录哈希冲突概念及解决方案哈希冲突的概念哈希冲突的解决方法拉链法再哈希法开放地址法线形勘测再散列二次勘测再散列双散列法伪随机法 哈希冲突概念及解决方案 哈希冲突的概念 哈希算法的目的就是将一串很大的...

    哈希冲突概念及解决方案

    哈希冲突的概念

    哈希算法的目的就是将一串很大的数据根据一定的规则转换为较小的数据。在这个从大到小的转换过程中,不可避免的会出现两个不同的数据在经过哈希算法的计算后生成了相同的哈希值。这个过程我们称之为哈希冲突。
    哈希冲突会带来很多问题,例如在哈希表中,两个不同的key值的哈希值相同,那么当这两个key值所表示的数据中的第一个存放到指定的位置后,第二个就没有地方可以存放了。所以我们在设计使用哈希算法的时候一定不能忽略掉哈希冲突。

    哈希冲突的解决方法

    常用的解决哈希冲突的方法有以下几种:

    拉链法

    拉链法是指当出现哈希冲突时,将具有相同哈希值的key值放进一个链表之中。当进行查找的时候可以通过遍历这个链表中的数据来寻找是否存在和被查找的key值相等的值。这种方法适用于处理冲突比较严重的情况。
    在这里插入图片描述

    再哈希法

    首先构造多个哈希算法Di = H1 (keyi), Di = H2 (keyi)…
    当发生哈希冲突时,将key值通过第二个哈希算法计算哈希值,若还冲突,就继续下去,直到找到不发生冲突的值。

    开放地址法

    开放地址法思想:当发生哈希冲突时,将这个哈希值加上一个增量d,来获取新的哈希值。即:
    Di = (H(key) + d) mod m。这里的m是空间大小,以防止哈希值超出规定范围。
    根据d的取值不同,开放地址法分为以下四种:

    线形勘测再散列

    d的取值为1,2,3,…
    即当发生哈希冲突时,判断当前哈希值H+1这个位置是否会发生哈希冲突,即当前H+1的位置上是否存在数据,如果不存在就将值放在这个位置上,如果存在数据,就判断hH+2。以此类推,直到找到不发生哈希冲突的位置。

    二次勘测再散列

    d的取值为1,-1,22,-(22)…

    双散列法

    定义另一个哈希算法PI = H2(keyI),当发生哈希冲突时,哈希值为(H1(keyi) + H2(keyi) mod m。

    伪随机法

    d的取值为一个伪随机序列依次取值。

    注意:使用开放地址法解决哈希冲突问题时,当删掉某个数据时,不能直接将其删除。因为这样会截断其他具有相同哈希值数据的位置。所以应该用一个标记标记下这个数据已经被删除。

    展开全文
  • 哈希冲突与解决哈希冲突的两种方法1、哈希冲突2、解决哈希冲突的方法(1)链接法(2)开放寻址法①线性探查②二次探查③双重探查 注:本文注重对解决哈希冲突方法的介绍,而非对背后原理的介绍。 1、哈希冲突 当两个...


    注:本文注重对解决哈希冲突方法的介绍,而非对背后原理的介绍。

    1、哈希冲突

    当两个不同的数经过哈希函数计算后得到了同一个结果,即他们会被映射到哈希表的同一个位置时,即称为发生了哈希冲突。
    在此我们不对哈希冲突的危害进行过多的描述,本文的重点是通俗的介绍解决哈希冲突的几种方法。

    2、解决哈希冲突的方法

    解决哈希冲突的方法主要有链接法与开放寻址法。

    (1)链接法

    链接法的构思来源于链表的启发,将被哈希到哈希表同一位置的数通过链表进行连接,使得他们能够在哈希表中共存,从而解决了哈希冲突。链接法解决哈希冲突
    如图所示,被哈希到同一位置的k1、k4;k5、k2、k7;k8、k6这三组数,被按照先后哈希的顺序,以双向链表的形式进行链接,从而共同被保存在哈希表中,解决了哈希冲突。

    (2)开放寻址法

    不同于链接法对哈希表的改变从而解决哈希冲突,开放寻址法的解决方法是通过对哈希函数的改变,从而将被可能发生哈希冲突的数按照一定规律哈希到另一个位置,从而保存在哈希表中。

    需要注意的是,开放寻址法具有一个通用的位置计算公式,即
    hi(x)= ( Hash( x ) + F ( i ) ) % TableSize
    其中,hi(x)是第i次冲突的解决函数, Hash( x ) 是原哈希函数,F ( i )是不同的开放寻址法所定义的函数,TableSize是哈希表的大小。
    以下三种开放寻址法解决方式,所不同的仅是对F ( i )的不同定义而已。

    ①线性探查

    根据上面所叙述的通用公式,在线性探查中,F ( i ) 为探查的次数,即发生哈希冲突后,依次将哈希函数值加一后对表大小取模,重新计算新的哈希位置。
    在具体实现中表现为,某个数x被哈希到i号位置,发现i号位置已经被占用,则查找(i+1)号位置,直到找到一个空的位置进行存放。
    hi(x)= ( Hash( x ) + i ) % TableSize

    举例说明:
    线性探查举例
    将U中的数按顺序哈希到如图所示的TableSize=7的哈希表中,其中0、1、2、3由于不发生冲突,都按照 h0(x)= ( Hash( x ) + 0 ) % 7 进行哈希计算,被放入了0,1,2,3的位置。
    在进行7的哈希计算时发现 h0(7)= ( 7 + 0 ) % 7 = 0 ,而0号位置已经被占用,则进行冲突解决,尝试 h1(7)= ( 7 + 1 ) % 7 = 1 ,发现1号位置也被占用,继续探查,h2(7)= ( 7 + 2 ) % 7 = 2 ,h3(7)= ( 7 + 3 ) % 7 = 3 , h4(7)= ( 7 + 4 ) % 7 = 4 , 直到第三次探查,找到了4号位置是空的,则将7放入4号位置,解决了冲突。

    ②二次探查

    在二次探查(也称平方探查)中,F ( i ) 是探查次数的平方
    hi(x)= ( Hash( x ) + i^2 ) % TableSize
    同样举例说明:
    二次探查举例说明
    同样的,我们先将0、1哈希到表的0、1位置,且未发生冲突。
    接下来,我们对7进行哈希,发现 h0(7)= ( 7 + 0^2 ) % 7 = 0 ,且0号位置已被占用,则进行冲突解决,尝试 h1(7)= ( 7 + 1^2 ) % 7 = 1 ,发现1号位置同样被占用,继续探查, h2(7)= ( 7 + 2^2 ) % 7 = 4,此时4号位置未被占用,则将7放入4号位置,冲突解决。

    ③双重探查

    双重探查也称二次再散列法,是指第一次散列产生哈希地址冲突,为了解决冲突,采用另外的散列函数或者对冲突结果进行处理的方法。
    在双重探查中,F ( i ) 是一个新的哈希函数的值的整数倍
    通常情况下,我们有:
    hi(x)= ( Hash( x ) + i*Hash1( x ) ) % TableSize
    其中Hash1( x )是一个不同于Hash( x )的新的哈希函数。

    举例说明:
    双重探查举例说明
    此例中,我们定义Hash1( x ) = x mod 5 。
    则有 hi(x)= ( Hash( x ) + i*(x mod 5) ) % 7 。
    在这里,0、1、2被哈希到0、1、2的位置,且未发生哈希冲突。
    对7进行哈希计算,发现 h0(7)= ( 7 + 0^2 ) % 7 = 0 ,0号位置已经被占用,发生哈希冲突,则进行解决,尝试 h1(7)= ( 7 + 1*(7 mod 5) ) % 7 = 2,发现2号位置同样被占用,则继续探查, h2(7)= ( 7 + 2*(7 mod 5) ) % 7 = 4,发现4号位置为空,则将7放入4号位置,解决冲突。

    展开全文
  • 文章目录Java哈希表概念冲突避免冲突哈希函数的设计方法常见哈希函数负载因子调节解决哈希冲突两种常见的方法是:闭散列和开散列哈希表和 java 类集的关系 Java哈希表 概念 顺序结构以及平衡树中,元素关键码与其...

    Java哈希表

    概念

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log N),搜索的效率取决于搜索过程中元素的比较次数。

    理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。
    当向该结构中:
    插入元素
    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
    搜索元素
    对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功
    该方式即为
    哈希(散列)方法
    ,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(HashTable)(或者称散列表)

    冲突

    不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。

    避免冲突

    *由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一
    个问题,冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率。*而不能完全避免哈希冲突。

    哈希函数的设计方法

    引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:

    哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
    哈希函数计算出来的地址能均匀分布在整个空间中
    哈希函数应该比较简单

    常见哈希函数

    1. 直接定制法–(常用)
      取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况
    2. 除留余数法–(常用)
      例如:数据集合{1,7,6,4,5,9};
      哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
      设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
      在这里插入图片描述
      用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快
    3. 平方取中法–(了解)
      假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况
    4. 折叠法–(了解)
      折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
      折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况
    5. 随机数法–(了解)
      选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

    负载因子调节

    在这里插入图片描述
    负载因子 = 0.75;

    所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。
    已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。(2倍扩容)

    为什么负载因是0.75

    HashMap的扩容时取决于threshold, 而threshold取决于loadFactor, loadFactor(负载因子)HashMap的默认值是0.75(3/4), 那么为什么当HashMap的容量超过3/4时就需要扩容了呢? 为什么不是1/2扩容 或者 等于table.length时扩容呢?

    根据统计学的结果, hash冲突是符合泊松分布的, 而冲突概率最小的是在7-8之间, 都小于百万分之一了; 所以HashMap.loadFactor选取只要在7-8之间的任意值即可,
    但是为什么就选了3/4这个值?
    HashMap.loadFactor的选值是3/4就能理解了, table.length * 3/4可以被优化为(table.length >> 2) << 2) - (table.length >> 2) == table.length - (table.lenght >> 2),
    JAVA的位运算比乘除的效率更高, 所以取3/4在保证hash冲突小的情况下兼顾了效率;

    解决哈希冲突两种常见的方法是:闭散列和开散列

    解决哈希冲突两种常见的方法是:闭散列和开散列

    哈希表和 java 类集的关系

    1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
    2. java 中使用的是哈希桶方式解决冲突的
    3. java 会在冲突链表长度大于一定阈值后,将链表转变为搜索树(红黑树)
    4. java 中计算哈希值实际上是调用的类的 hashCode 方法,进行 key 的相等性比较是调用 key 的 equals 方
      法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须覆写 hashCode 和 equals 方
      法,而且要做到 equals 相等的对象,hashCode 一定是一致的。
    展开全文
  • 什么是哈希冲突: 不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词” 哈希冲突的避免: 首先,我们需要明确一点,...

    什么是哈希冲突

    • 不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词

    哈希冲突的避免

    • 首先,我们需要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题,冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率

    1. 哈希函数的设计

    • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
    • 哈希函数计算出来的地址能均匀分布在整个空间中
    • 哈希函数应该比较简单

    常用哈希函数:

    • 直接定制法–(常用)

    取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况

       public int hashFunc(int key) {
            return 2 * key - 1;
        }
    
    • 除留余数法–(常用)

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

       public int hashFunc1(int key) {
            return key % this.array.length;
        }
    
    • 常用的字符串的哈希算法

    • MD5算法

    1. 无论输入多长的字符串,最终得到的MD5值的长度都是固定的
    2. 如果输入俩个字符串很相似,就只有一个字符不同,得到的MD5值相差也会非常大
    3. 通过字符串计算MD5值很高效,反之不行(给定MD5 值求字符串要经过大量计算,理论上是不可行的除非字符串很简单如:abc)
    4. MD5也常用到一些需要加密的场景和一些传输数据的校验上
    • SHA1算法

    理论上比MD5更安全,也更简便,但是效率不如MD5

    1. 负载因子调节
    • 负载因子的定义为:填入表中的元素个数 / 散列表长度
    • 对于开方地址法,负载因子特别重要,要严格控制在0.7~0.8以下,一旦超过0.8哈希表的查找效率就非常低,所以在java的系统库限制了负载因子为0.75,超过或者达到就会resize(扩容)
    • 已知哈希表中的关键字个数是不可变的,那我们就只有调整哈希表中的数组的大小。(扩容)

    哈希冲突的解决:

    • 常见的俩种解决思想就是闭散列、开散列

    1. 闭散列(不推荐这种方式)
    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢?

    • 线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。(再进行删除操作的时候易出错)
    • 二次探索:从发生冲突的位置开始,依次向后探测,直到寻找到下(n^2)空位置为止。(再进行删除操作的时候易出错,而且空间利用低)

    2. 开散列(哈希桶)(推荐)

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

    这个我有具体实现:

    点击这里查看:如何利用开散列(哈希桶)的思想解决哈希冲突,实现哈希表的增加(扩容)、查找、删除

    展开全文
  • 哈希表及哈希冲突解决办法

    千次阅读 2019-07-17 22:04:11
    哈希表及哈希冲突解决办法 目录 什么是哈希表? 哈希表的数据结构 哈希冲突 哈希冲突解决办法 1. 什么是哈希表? 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而...
  • 哈希表:理想情况下可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函 数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以...
  • 定义哈希表是根据关键码值直接进行数据访问的数据结构,它通过把关键码映射到一个位置来访问记录,这个映射函数叫哈希函数,存放记录的数组叫哈希表 最简单的哈希查找 当知道数据的范围为0~99时,使用哈希的思想就...
  • 哈希表以及哈希冲突的解决 1.哈希表 1.1概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应关系,因此在查找一个元素的时候,必须要经过关键码的多次比较,这样查找的效率就比较低下,搜索的效率取决...
  • 哈希表,哈希冲突

    2020-05-23 23:29:12
    什么是哈希表? 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行...散列冲突:不同的关键字经过散列函数的计算得到了相同的散列地址。 好的散列函数=计算简单+分布均匀(计算得到的散列地址分
  • 哈希表---开链法解决哈希冲突

    千次阅读 2016-11-19 10:17:17
    上篇文章已经写过构造哈希表时用开放定址法解决哈希冲突,这次我就来写写这个开链法解决哈希冲突的问题! 一、结点定义 我们已经知道开链法大概是一种什么结构了,(如果不知道,这里有讲哦点我点我)显而易见...
  • 写在之前 什么是函数? 在中学中,函数被定义为,已知一个数集A,通过特定对应法则,由数集A得到了数集B。我们可以这样理解数集A中...哈希函数也叫散列函数,哈希函数的定义域是所有key值,值域是下标。 哈希函数可以
  • 通常,我们所谓的哈希冲突可以定义为对于两个不相等的数据元素 i和 j,将他们代入哈希函数hashFunc有:   hashFunc(i) == hashFunc(j)  即不同关键字通过相同哈希函数计算出相同的哈希地址,对于哈希冲突的...
  • 2 哈希冲突的处理—— 链地址法(Seperate Chaining) Java8 之前,每一个位置对用一个链表; Java8 开始,当哈希冲突达到一定程度,每一个位置从链表转成红黑树; 3 实现自定义的哈希表 HashTable package ...
  • 一、哈希表概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。搜索的效率取决于搜索过 程中元素的比较次数。 如果构造一种存储结构,通过...
  • 设计一个哈希表的关键有三个:怎么控制哈希表的长度,怎么设计哈希函数,怎么处理哈希冲突。 怎样控制哈希表的长度 哈希表的长度一般是定长的,在存储数据之前我们应该知道存储的数据规模是多大,应该尽可能地...
  • 哈希冲突的产生原因 哈希是通过对数据进行再压缩,提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的,而数据可能比较多,导致经过哈希函数处理后仍然有不同的数据对应相同的哈希值。这时候就产生了...
  • 本文章主要介绍哈希的概念、关于处理哈希表中哈希冲突的闭散列方式以及代码实现其哈希表闭散列方式的插入查找删除操作!
  • 等等等等,所以,在根据不同的场景可以制定不同的哈希函数,这样就可以减少哈希冲突出现的概率。 闭散列中的线性探测和二次探测 线性探测 线性探测就是:当发生哈希冲突的时候,key值逐个向后进行查找,直到找到...
  • 文章目录哈希表和哈希函数的概念哈希函数的构造直接定址法数字分析法平方取中法折叠法除留余数法(常用)随机数法哈希函数的选择处理冲突的方法开放定址法再哈希法链地址法建立一个公共溢出区代码实现 哈希表和哈希...
  • 本文章主要介绍处理哈希冲突的另一种方式:开散列方式。以及通过代码实现以开散列方式存储的哈希表的插入查找删除操作!
  • 哈希表 概念: 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2Nlog_2 Nlog2​N),...
  • 哈希 一般指哈希算法。英文Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,...
  • 如何解决哈希冲突

    2016-05-31 11:10:44
    就不自己写了,直接贴下吧看了ConcurrentHashMap的实现, 使用的是拉链法.虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的...因此,处理冲突和溢出是 哈希技术中的两个重要问题
  • 哈希冲突解决方法

    2015-07-29 14:38:15
    就不自己写了,直接贴下吧 看了ConcurrentHashMap的实现, ...另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是
  • 由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。 哈希构造函数 本文的哈希构造函数采用除留余数法,哈希构造函数可以参考我的另一篇...
  • 开散列法又叫链地址法(开链法)/哈希桶/拉链法,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储...
  • 哈希冲突是指hash出来的地址被其他元素所占用; 解决的方法 1.链地址法 解决的思路就是当出现冲突的时候将冲突的元素加入当前的链表之中 2.开放地址法 开放地址法也称之为再散列。 思路:如果映射的地址被占用了,在...
  • 这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突哈希地址pi ,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,932
精华内容 20,372
热门标签
关键字:

哈希冲突的定义