精华内容
下载资源
问答
  • 什么是哈希冲突: 不同关键字通过相同哈希哈数计算...1. 哈希函数设计 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间 哈希函数计算出来的地址能均匀分布在

    什么是哈希冲突

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

    哈希冲突的避免

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

    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. 开散列(哈希桶)(推荐)

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

    这个我有具体实现:

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

    展开全文
  • 取模法的素数选择 当数据量在32~64之间时,选择53 …

    取模法的素数选择
    当数据量在32~64之间时,选择53

    在这里插入图片描述

    展开全文
  • 哈希函数设计 “键”通过哈希函数得到的“索引”分布越均匀越好; 对于一些特殊领域,有特殊领域的哈希函数设计方式,甚至有专门的论文; 一般的哈希函数设计原则 整型 小范围正整数直接使用; 小范围负整数...

    哈希函数设计

    • “键”通过哈希函数得到的“索引”分布越均匀越好;
    • 对于一些特殊领域,有特殊领域的哈希函数设计方式,甚至有专门的论文;

    一般的哈希函数设计原则

    • 整型
      • 小范围正整数直接使用;
      • 小范围负整数进行偏移,比如 -100 ~ 0 -> 0 ~ 100;
    • 大整数
      • 通常做法:取模,比如取后4位,等同于mod 10000,但取模不能利用大整数中所有有用的信息,一个简单的解决办法是:模一个素数,具体素数怎么选择有人研究的,比如从这里可以参考
    • 浮点型
      • 将浮点型占用的二进制空间看成整型,用整型的办法处理;
    • 字符串
      • 转成整型处理,用26进制表示字符串,比如:code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0;
      • hash("code") = ( c * B^3 + o * B^2 + d * B^1 + e * B^0 ) % M
        hash("code") = ( ( ( ( c * B ) + o ) * B + d ) * B + e ) % M
        hash("code") = ( ( ( ( c % M ) * B + o ) % M * B + d ) % M * B + e) % M
    int hash = 0
    for(int i = 0; i < s.length(); i++) 
       hash = (hash * B + s.charAt(i)) % M
    
    • 复合类型
      • 可以转换成字符串来处理,而字符串又可以转成整数来处理;

    总而言之,就是转成整型处理,但这并不是唯一的方法!

    哈希函数设计原则

    • 一致性:如果 a == b,则hash(a) == hash(b)
    • 高效性:计算搞笑简便;
    • 均匀性:哈希值分布均匀;
    展开全文
  • 3. 解决哈希冲突的方法:数组扩容,设计优秀的哈希函数,开放寻址法和链表法为哈希值找到合适的映射。 4. 开放寻址法,插入、查找、删除都需要相同的寻址逻辑,所以时间复杂度一样。数组中元素越多,空闲位置越少,...

    一、什么是哈希表

    哈希表就是数组+哈希函数,其核心思想是利用数组可以按照下标索引随机访问数据的特性。

    举个栗子:一个班级有50个人,每个人都有学号,按自然数顺序编号,学号1是小明,学号2是小红,学号3是小强,以此类推。在这个栗子中一个班级就是一个数组容器,学号就是数组的下标,学生就是数组中的元素,通过学号找人就是利用数组下标随机访问元素的特性。而如何给学生编号就是哈希函数的事情了。

    在这里插入图片描述

    二、哈希函数

    哈希函数,顾名思义,是一个函数,表达式:hash(key),key就是与数组下标不相干的关键词,而哈希函数计算的值就是与数组下标建立联系,可以直接作为数组下标,也可以将哈希值做取模等运算得到数组下标。

    刚才学号的栗子就是hash(自然数)=自然数,计算得到的哈希值可以直接用作数组下标,而深入到哈希表的实际应用,往往计算出的哈希值会很大,将其直接作为数组下标的话会使数组的长度很长,浪费内存。所以在有限的数组中通过哈希函数映射下标,势必会造成哈希冲突。

    三、哈希冲突的原因与解决方法

    产生哈希冲突的原因不仅仅是因为数组的有界,还包括哈希函数的计算以及对哈希值的映射都会产生哈希冲突。

    解决哈希冲突的方式也是根据这三个原因对症下药:

    1. 数组有界就适当扩容。
    2. 设计优秀的哈希算法。
    3. 开放寻址法和链表法为哈希值找到合适的映射。

    1、数组扩容

    数组中空闲的位置越多,一定程度上哈希冲突也会越小。但是不能因为这个原因就把数组的长度设置的很长,而是设置一个合理的初始长度,后面再慢慢扩容。

    什么时候扩容?扩容多少?都是有考究的。扩容太少导致频繁扩容影响性能,扩容太多浪费内存。一般经验所得,当元素个数占数组长度的3/4时扩容,扩容后的长度是原来的两倍。这也是java中HashMap的扩容思想,但是还是需要根据实际情况做调整。

    什么时候扩容有一个名词,装载因子,代表元素个数占数组长度的比例:装载因子=元素个数/数组长度。装载因子的设置要权衡时间和空间复杂度,装载因子太大,哈希冲突越严重,装载因子太小,内存浪费严重。

    如果内存空间不紧张,对执行效率要求很高,可以降低装载因子的阈值;相反,如果内存空间紧张,对执行效率要求又不高,可以增加装载因子的大小,甚至可以大于 1(对于链表法冲突解决)。

    对于单纯的数组扩容,数据的迁移很简单,对应位置复制过去即可,但是哈希表的扩容迁移就比较复杂,哈希表的长度变了,元素的位置也变了,需要一个个重新计算哈希映射新位置。扩容的时间复杂度是O(n),简单的插入一个数据的时间复杂度是O(1),如果刚好碰上扩容,时间复杂度就是O(n)。
    在这里插入图片描述

    扩容在一定程度上影响插入数据的性能,所以要避免无效的扩容,除了设计合理的装载因子和扩容比例,还可以从扩容的过程中优化:

    (1)扩容动作摊分到每个插入操作中,新数据插入新数组中,插入数据的同时复制一个旧数组中的一个元素到新数组,这样每次插入操作的时间复杂度都是O(1),但是需要兼容维护新旧数组,查找和删除操作先到旧数组查找,没有再到新数组查找。(jdk1.8 ConcurrentHashMap多线程扩容思想)

    (2)对于链表法解决冲突构成的哈希表,迁移时可以链表为单位复制,无需所有元素重新计算哈希值。(ConcurrentHashMap扩容以链表为单位整体迁移复制)

    2、一个优秀的哈希函数

    一个不合理的哈希函数,会使得数组扩容功亏一篑。若计算的哈希值本身很容易冲突,或者映射到数组下标不均匀分布,再多的空闲位置也没用。这就要求一个优秀的哈希函数必须具有以下2个要素:

    • 哈希值尽量随机且均匀分布,这样不仅可以最小化哈希冲突,而且即使出现了冲突,也会平均在各个位置,有利于冲突的解决改善(开放寻址法和链表法)。
    • 哈希算法的计算性能要高,不能影响哈希表的正常操作。

    数组扩容和优秀的哈希函数仍然无法避免哈希冲突,还可以从哈希值映射上下手,常用的方法有开放寻址法和链表法。

    3、开放寻址法

    开放寻址法,就是当发生哈希冲突时,重新找到空闲的位置,然后插入元素。寻址方式有多种,常用的有线性寻址、二次方寻址、双重哈希寻址:

    • 线性寻址,当需要插入元素的位置被占用时,顺序向后寻址,如果到数组最后也没找到一个空闲位置,则从数组开头寻址,直到找到一个空闲位置插入数据。线性寻址的每次寻址步长是1,寻址公式hash(key)+n(n是寻址的次数)。
    • 二次方寻址,就是线性寻址的总步长的二次方,即hash(key)+n^2
    • 双重哈希寻址,顾名思义就是多次哈希直到找到一个不冲突的哈希值。
      在这里插入图片描述

    采用开放寻址法解决哈希冲突,又该如何查找元素和删除元素呢?

    查找元素的过程和插入元素类似,用相同的寻址方式,寻址的同时比对key或者value是否相等,相等则认为元素存在,不相等则继续寻址,如果探测到空闲位置依然没有找到则认为该元素不存在

    删除有些特别,不能单纯的把要删除的元素设置为空,因为在查找元素的过程中探测到的空闲位置是删除元素的位置,就会使得查找元素的寻址算法失效,本来存在的元素误判定为不存在。该如何解决这个问题呢?

    只需要删除元素不是物理删除而是逻辑删除。给删除的元素做上delete标记,当查询元素寻址时遇到delete标记的位置时不会停下来而是继续向后探测,但是在插入元素寻址遇到delete标记的位置就会把应该删除的元素替换掉。

    三种寻址方式都有着明显的不足:

    • 线性寻址,寻址的性能虽然元素个数的增多逐步下降,最坏时间复杂度是O(n)。
    • 二次方寻址,寻址的次数比线性寻址较低了,但是会因为步长是二次方,所以需要较长的数组长度,内存利用率可能较低。
    • 双重哈希寻址,多次哈希可能会浪费时间,需要优质的哈希函数做支撑。

    而整个开放寻址法的不足也很明显:

    • 插入、查找、删除都需要寻址。
    • 数组中元素越多,空闲位置越少,哈希冲突越剧烈。所以装载因子不能太大,要及时扩容减小冲突,但是数组内存利用率较低。

    看似开放寻址法有挺多问题,但是也有一些优点:

    • 数据都存储在数组中,可以有效地利用 CPU 缓存加快查询速度。
    • 而且,这种方法实现的哈希表,序列化也简单,不像链表还要考虑指针。

    总结而得,当数据量比较小、装载因子小的时候,适合采用开放寻址法。这也是 Java 中ThreadLocal内部类ThreadLocalMap使用开放寻址法解决散列冲突的原因。

    4、链表法

    链表法相对于开放寻址法实现起来简单一些,在数组内存利用率上比开放寻址法高,同时对装载因子的忍耐度也相对较高。开放寻址法的装载因子只能小于1,越趋近于1,冲突越剧烈,寻址过程越耗时,而链表法的装载因子可以大于1(但是内存不紧张,在意性能的一般不会装载因子不会大于1)。

    链表法就是将产生哈希冲突的元素链接成一个链表,每个链表可以设想成一个桶(bucket)或者槽(slot):

    • 插入元素就是通过哈希找到对应的桶,然后插入到链表中,时间复杂度为O(1);
    • 查找元素也是通过哈希找到对应的桶,然后遍历链表;
    • 删除元素同样通过哈希找到对应的桶,遍历链表找到需要删除的元素删除。

    当哈希比较均匀时,理论上查询和删除的时间复杂度为O(n/m),n是数组中元素的个数,m是数组中桶的个数。但是当哈希冲突非常严重时,数据都集中在一个桶里,数组退化成链表,查找和删除的时间复杂度为趋近与O(n)。
    在这里插入图片描述

    针对数组退化成链表或者链表过长导致的性能下降,可以在合适的时机将链表转换为红黑树,极端情况下数组退化成一个红黑树,时间复杂度也是O(logn),比O(n)强多了。(jdk8中ConcurrentHashMap对于jdk7有所优化,当链表节点的个数大于8个且数组的长度大于64时,链表转换为红黑树;当红黑树的节点小于8个时又退化为链表。)

    可以容忍的缺点:

    • 因为链表节点需要存放指针,所以内存占用上比开放寻址法高。
    • 链表中的节点在内存中是不连续分布的,所以对CPU缓存的利用率也不高,序列化也比开放寻址法复杂。

    优点:

    • 内存利用率较高。
    • 优化策略灵活,红黑树和链表可以互相转换。

    四、总结

    哈希表的两个核心哈希函数的设计与哈希冲突的解决。

    1. 哈希表就是数组+哈希函数,其核心思想是利用数组可以按照下标索引随机访问数据的特性。
    2. 哈希冲突的原因:数组的有界,哈希函数的计算,哈希值的映射。
    3. 解决哈希冲突的方法:数组扩容,设计优秀的哈希函数,开放寻址法和链表法为哈希值找到合适的映射。
    4. 开放寻址法,插入、查找、删除都需要相同的寻址逻辑,所以时间复杂度一样。数组中元素越多,空闲位置越少,哈希冲突越剧烈。
    5. 链表法需要注意,当哈希冲突非常严重时,数组会退化成链表,查找和删除的时间复杂度趋近于O(n),可以采用红黑树进行优化。

    参考:极客时间专栏《数据结构与算法之美》。

    PS: 如若文章中有错误理解,欢迎批评指正,同时非常期待你的评论、点赞和收藏。我是徐同学,愿与你共同进步!

    展开全文
  • 哈希函数设计

    2012-12-04 14:19:09
    今天闲来没事在poj上刷提,找找当年读本科的感觉。 随便选了个有关哈希的poj3349,题目比较简单,就是要找左循环或者右循环...从这个小例子可以看出,哈希函数设计对于提高效率还是有很大作用的。 PS:用cin进行
  • 设计一个哈希表的关键有三个:怎么控制哈希表的长度,怎么设计哈希函数,怎么处理哈希冲突。 怎样控制哈希表的长度 哈希表的长度一般是定长的,在存储数据之前我们应该知道存储的数据规模是多大,应该尽可能地...
  • 哈希表与哈希函数

    2018-08-19 17:59:15
    设计哈希函数的过程要针对状态数来进行分析。 哈希函数的本质在做哈希,处理哈希碰撞。 设计哈希表应当注重以下两点: 设计哈希函数 处理冲突 设计哈希有以下几种方法: 开放地址法 多重哈希...
  • 哈希函数设计以及冲突的处理

    千次阅读 2015-08-05 14:34:51
    哈希函数设计以及冲突的处理
  • 不使用任何内建的哈希表库设计一个哈希映射 设计包含以下内容: put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更新这个值。 get(key):返回给定的键所对应的值,如果映射中不包含这...
  • 哈希函数+布隆过滤器+一致性哈希+哈希表 认识哈希函数和哈希表 设计RandomPool结构 认识布隆过滤器 认识一致性哈希 (from左神算法初级班第6节) 1.认识哈希函数和哈希表 1)什么是哈希函数?(非常重要) 定义:...
  • 今天主要讨论:哈希函数、哈希表、布隆过滤器、一致性哈希、并查集的介绍和应用。 题目一 认识哈希函数和哈希表 1、输入无限大 2、输出有限的S集合 3、输入什么就输出什么 4、会发生哈希碰撞 5...
  • 构造哈希函数

    2018-12-27 14:26:25
    设计哈希函数;分别采用线性探测再散列法和链地址法解决冲突 1.线性探测再散列:建立一个一维数组,需要计算数组的容量。如果是对12个数建立哈希表,则表长通过填满因子,计算为15。线性解决冲突的方法是通过哈希...
  • 哈希函数

    2021-01-21 11:59:32
    小明设计了一个哈希函数,将一个长度为 kk 的字符串转成个长度为 3232 的字符串。这个哈希函数 \mathcal{f}f 的设计如下: 声明一个长度为 3232 的数组 arr,并将其中元素全部初始化为 0。 取出每一位的 ASCII 值,...
  • 哈希表查找的基本思想是:根据当前带查找数据的特征,以记录关键字为自变量,设计一个哈希函数,以该函数按关键码计算该元素的存储位置,并按此存放;查找时,有同一个函数对给定值key计算地址,将key与地址单元中...
  • Hash函数特点: 1.输入域无穷,输出域有限。例如:有无穷多个(在工程中可以具体到多少个,例如1000)输入参数经过hash函数映射后得到有限的输出域{1,2,3,4}。 2.输入参数确定,经过hash函数映射出的返回值一样。...
  • 哈希函数+布隆过滤器+一致性哈希+哈希表认识哈希函数和哈希表设计RandomPool结构认识布隆过滤器认识一致性哈希1.1什么是哈希函数?定义:能通过哈希函数直接找到需要的记录,在记录的存储位置和它的关键字之间建立一...
  • 这一篇文章来具体说一说,怎么设计哈希函数能够让哈希表更加效率。 哈希函数,是用来计算存储数据的哈希值的,根据存储数据的类型,可以设计不同的哈希函数。一个好的哈希函数(让哈希表效率高的函数),一般都具备...
  • 实现哈希表有两个主要的问题, 一个是解决哈希函数设计, 一个是哈希冲突的处理 哈希函数 键通过哈希函数可以得到一个索引, 通过索引可以在内存中找到这个键所包含的信息, 索引的分布越均匀冲突才越少 所有类型的...
  • 哈希表及哈希函数研究综述摘要 随着信息化水平的不断提高,数据已经取代计算成为了信息计算的中心,对存储的需求不断提高信息量呈现爆炸式增长趋势,存储已经成为急需提高的瓶颈。哈希表作为海量信息存储的有效方式...
  • (1)哈希函数采用除留余数法,解决哈希冲突方法采用开放定址法的线性探查法。 (2)设计函数表构造头文件。头文件包括节点结构体定义,以及哈希表初始化、哈希表元素插入、哈希表元素删除、哈希表查找和哈希表撤销...
  • C语言新哈希函数

    2021-01-06 23:21:26
    小明设计了一个哈希函数,将一个长度为 k 的字符串转成个长度为 32 的字符串。这个哈希函数设计如下: 声明一个长度为 32 的数组 arr,并将其中元素全部初始化为 0。 取出每一位的 ASCII 值,将长度为 k的字符串中...
  • 哈希函数的构造方法

    千次阅读 2016-11-17 23:41:55
    哈希函数的构造方法本文阐述了哈希函数的构造方法有很多,但应注意两个原则:第一,函数值应在1至...设要存放的数据元素有n个,存放数据元素的内存单元有m个,设计哈希函数的目标就是要使通过哈希函数得到的n个数据元素
  • 哈希函数

    千次阅读 2013-01-02 21:39:00
    Hash查找因为其O(1)的查找性能而著称,被对查找性能要求高...其中hash函数设计是最为关键的,均匀分布、冲突概率小全在它; (3) 通常采用拉链方法来解决hash冲突问题,即散射到同一个hash表项的关键字,以链表形式来表
  • 哈希函数的生成方法

    千次阅读 2017-07-30 21:22:49
    设要存放的数据元素有n个,存放数据元素的内存单元有m个,设计哈希函数的目标就是要使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上,同时使计算过程尽可能简单以达到尽可能高的时间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,251
精华内容 500
关键字:

哈希函数设计