精华内容
下载资源
问答
  • Hash碰撞概率

    2018-06-23 23:53:00
    计算Hash冲突的概率 虽然已经很多可以选择的Hash函数,但创建一个好的Hash函数仍然是一个活跃的研究领域。一些Hash函数是快的,一些是慢的,一些Hash值均匀地分布在值域上,一些不是。对于我们的目的,让我们假设这...

    计算Hash冲突的概率

    虽然已经很多可以选择的Hash函数,但创建一个好的Hash函数仍然是一个活跃的研究领域。一些Hash函数是快的,一些是慢的,一些Hash值均匀地分布在值域上,一些不是。对于我们的目的,让我们假设这个Hash函数是非常好的。它的Hash值均匀地分布在值域上。

    在这种情况下,对于一个输入集合生成的Hash值是非常像生成一个随机数集合。我们的问题转化为如下: 
            给K个随机值,非负而且小于N,他们中至少有个相等的概率是多少? 
    实际上我们求这个问题的对立问题更加简单:他们都不相同的概率是多少?无论这个对立问题的结果是多少,我们用1减去对立问题的结果就得到原问题的结果。

    对于一个值域为N的Hash值,假设你已经挑选出一个值。之后,剩下N-1个值是不同于第一个值的,因此,对于第二次随机生成不同第一个数的概率为N/N-1. 
    简而言之,有N个不同的数,你第一次挑选出某个,然后继续从N个数中挑选,那只要不是选到和第一次一样的那个数一样就不一样喽,所以概率为N-1/N。 
    之后就是第三次挑选,第三次挑选出的第三个数要求不同于前两个数,所以概率就为N-1/N*N-2/N. 
    一般的,随机生成K个数,他们都不相同的概率为: 
    这里写图片描述 
    计算机中,对于K很大的时候计算很麻烦,幸运的是,上面的表达式近似于 
    这里写图片描述 
    这个会更快得计算,我们如何知道这是一个好的近似。我们看一下分析过程,使用泰勒公式和epsilon-delta proof,这个误差趋于0当N增大的时候。或者,更简单,你可以计算2者的值然后比较他们,运行下面的python代码,你会感觉到这个近似是多么准确:

    import math
    N = 1000000
    probUnique = 1.0
    for k in xrange(1, 2000):
        probUnique = probUnique * (N - (k - 1)) / N
        print k, 1 - probUnique, 1 - math.exp(-0.5 * k * (k - 1) / N)

    好的,这个奇妙的表达式作为我们每个值都不一样的结果,然后我们用1减去得到Hash冲突的概率 
    这里写图片描述 
    这是一个 N=2^32的图,它说明了使用32bit的Hash值的冲突概率,当Hash数是77163时,发生碰撞的可能为50%,这是有价值的。而且注意无论N区任意值都会得到一个类似S曲线的图。 
    这里写图片描述

    简化表达式

    这是非常有趣的,我们的表达式是1-e^-x这种形式,下面近似这仅仅在X较小的时候误差非常小,1/10或更小: 
    这里写图片描述 
    换句话说,这个表达式非常好的近似于它自己的指数,实际上x越小,越准确,所以小的冲突概率,我们能使用这个简化表达式 
    这里写图片描述 
    这实际上是一个非常方便的表示。因为它避免了一些在原表达式中的精度问题。浮点型数字在非常接近1的时候表示不是很好。

    此外,如果N远大于K,K和K-1并没有什么大区别。所以我们可以更加化简为:K^2/2N

     

     

     

    参考:   

    Hash碰撞概率

    Hash算法的碰撞概率

    转载于:https://www.cnblogs.com/AndrewYin/p/9219314.html

    展开全文
  • hash碰撞

    2019-10-24 23:01:02
    一 ,到底什么是hash呢? hash(散列、杂凑)函数,是将任意长度的数据映射到有限长度的域上。直观解释起来,就是对一串数据m进行杂糅,输出另一段固定长度的数据h,作为这段数据的特征(指纹)。 也就是说,无论...

    一 ,到底什么是hash呢?

    hash(散列、杂凑)函数,是将任意长度的数据映射到有限长度的域上。直观解释起来,就是对一串数据m进行杂糅,输出另一段固定长度的数据h,作为这段数据的特征(指纹)。
    也就是说,无论数据块m有多大,其输出值h为固定长度。到底是什么原理?将m分成固定长度(如128位),依次进行hash运算,然后用不同的方法迭代即可(如前一块的hash值与后一块的hash值进行异或)。如果不够128位怎么办?用0补全或者用1补全随意,算法中约定好就可以了。由于用途的不同,hash在数据结构中的含义和密码学中的含义并不相同,所以在这两种不同的领域里,算法的设计侧重点也不同。


    抗碰撞能力:对于任意两个不同的数据块,其hash值相同的可能性极小;对于一个给定的数据块,找到和它hash值相同的数据块极为困难。
    抗篡改能力:对于一个数据块,哪怕只改动其一个比特位,其hash值的改动也会非常大。
    在用到hash进行管理的数据结构中,比如hashmap,hash值(key)存在的目的是加速键值对的查找,key的作用是为了将元素适当地放在各个桶里,对于抗碰撞的要求没有那么高。换句话说,hash出来的key,只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能,直接与hash值产生的速度有关,所以这时候的hash值的产生速度就尤为重要,以JDK中的String.hashCode()方法为例,很简洁的一个乘加迭代运算,在不少的hash算法中,使用的是异或+加法进行迭代,速度和前者差不多。

    在密码学中,hash算法的作用主要是用于消息摘要和签名,换句话说,它主要用于对整个消息的完整性进行校验。举个例子,我们登陆知乎的时候都需要输入密码,那么知乎如果明文保存这个密码,那么黑客就很容易窃取大家的密码来登陆,特别不安全。那么知乎就想到了一个方法,使用hash算法生成一个密码的签名,知乎后台只保存这个签名值。由于hash算法是不可逆的,那么黑客即便得到这个签名,也丝毫没有用处;而如果你在网站登陆界面上输入你的密码,那么知乎后台就会重新计算一下这个hash值,与网站中储存的原hash值进行比对,如果相同,证明你拥有这个账户的密码,那么就会允许你登陆。银行也是如此,银行是万万不敢保存用户密码的原文的,只会保存密码的hash值而而已。
    在这些应用场景里,对于抗碰撞和抗篡改能力要求极高,对速度的要求在其次。一个设计良好的hash算法,其抗碰撞能力是很高的。以MD5为例,其输出长度为128位,设计预期碰撞概率为,这是一个极小极小的数字——而即便是在MD5被王小云教授破解之后,其碰撞概率上限也高达,也就是说,至少需要找次才能有1/2的概率来找到一个与目标文件相同的hash值。而对于两个相似的字符串,MD5加密结果如下:
    MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
    MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8";
    可以看到仅仅一个比特位的改变,二者的MD5值就天差地别了。

    二,什么是hash碰撞呢?怎么处理?

    如果两个输入串的hash函数的值一样,则称这两个串是一个碰撞(Collision)。既然是把任意长度的字符串变成固定长度的字符串,所以必有一个输出串对应无穷多个输入串,碰撞是必然存在的。

    一个优良的hash函数 f 应当满足以下三个条件:

    (1)对于任意y,寻找x,使得f(x)=y,在计算上是不可行的。

    (2)给定x1∈A,找x2∈B,,使得f(x1)=f(x2),在计算上是不可能的,这也就是弱无碰撞性。

    (3)寻找x1,x2,使得f(x1)=f(x2),在计算上也是不可行的,这也就是强无碰撞性。

    这样就称为安全保密的Hash函数,除了枚举外不可能有别的更快的方法。如第3条,根据生日定理,要想找到这样的x1,x2,理论上需要大约2^(n/2)的枚举次数。

    因为前两条都能被破坏的hash函数太弱而被抛弃,几乎所有的hash函数的破解,都是指的破坏上面的第3条性质,即找到一个碰撞。在密码学上还有一个概念是理论破解,指的是提出一个算法,使得可以用低于理论值得枚举次数找到碰撞。

    4、碰撞处理

       通常有两类方法处理碰撞:开放寻址(Open Addressing)法和链接(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中;后者通常是把散列到同一槽中的所有元素放在一个链表中,而将此链表的头指针放在散列表T[0..m-1]中。

    (1)开放寻址法

      所有的元素都在散列表中,每一个表项或包含动态集合的一个元素,或包含NIL。这种方法中散列表可能被填满,以致于不能插入任何新的元素。在开放寻址法中,当要插入一个元素时,可以连续地检查或探测散列表的各项,直到有一个空槽来放置待插入的关键字为止。有三种技术用于开放寻址法:线性探测、二次探测以及双重探测。

    <1>线性探测

      给定一个普通的散列函数h':U —>{0,1,.....,m-1},线性探测方法采用的散列函数为:h(k,i) = (h'(k)+i)mod m,i=0,1,....,m-1  

         探测时从i=0开始,首先探查T[h'(k)],然后依次探测T[h'(k)+1],…,直到T[h'(k)+m-1],此后又循环到T[0],T[1],…,直到探测到T[h'(k)-1]为止。探测过程终止于三种情况: 
      (1)若当前探测的单元为空,则表示查找失败(若是插入则将key写入其中); 
      (2)若当前探测的单元中含有key,则查找成功,但对于插入意味着失败; 
      (3)若探测到T[h'(k)-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。

      线性探测方法较容易实现,但是存在一次群集问题,即连续被占用的槽的序列变的越来越长。采用例子进行说明线性探测过程,已知一组关键字为(26,36,41,38,44,15,68,12,6,51),用除余法构造散列函数,初始情况如下图所示:

    散列过程如下图所示:

    <2>二次探测

       二次探测法的探查序列是:h(k,i) =(h'(k)+i*i)%m ,0≤i≤m-1 。初次的探测位置为T[h'(k)],后序的探测位置在次基础上加一个偏移量,该偏移量以二次的方式依赖于i。该方法的缺陷是不易探查到整个散列空间。

    <3>双重散列

      该方法是开放寻址的最好方法之一,因为其产生的排列具有随机选择的排列的许多特性。采用的散列函数为:h(k,i)=(h1(k)+ih2(k)) mod m。其中h1和h2为辅助散列函数。初始探测位置为T[h1(k)],后续的探测位置在此基础上加上偏移量h2(k)模m。

     (2)链接法

      将所有关键字为同义词的结点链接在同一个链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1。

      举例说明链接法的执行过程,设有一组关键字为(26,36,41,38,44,15,68,12,6,51),用除余法构造散列函数,初始情况如下图所示:

    最终结果如下图所示:

    三 ,为什么HashMap初始容量是2<<4 ?
    如果两个元素不相同,但是hash函数的值相同,这两个元素就是一个碰撞

    因为把任意长度的字符串变成固定长度的字符串,所以存在一个hash对应多个字符串的情况,所以碰撞必然存在

    为了减少hash值的碰撞,需要实现一个尽量均匀分布的hash函数,在HashMap中通过利用key的hashcode值,来进行位运算
    公式:index = e.hash & (newCap - 1)

    举个例子:
    1.计算"book"的hashcode
        十进制 : 3029737
        二进制 : 101110001110101110 1001

    2.HashMap长度是默认的16,length - 1的结果
        十进制 : 15
        二进制 : 1111

    3.把以上两个结果做与运算
        101110001110101110 1001 & 1111 = 1001
        1001的十进制 : 9,所以 index=9

    hash算法最终得到的index结果,取决于hashcode值的最后几位

    为了推断HashMap的默认长度为什么是16
    现在,我们假设HashMap的长度是10,重复刚才的运算步骤:
    hashcode : 101110001110101110 1001
    length - 1 :                                     1001
    index :                                            1001

    再换一个hashcode 101110001110101110 1111 试试:
    hashcode : 101110001110101110 1111
    length - 1 :                                     1001
    index :                                            1001

    从结果可以看出,虽然hashcode变化了,但是运算的结果都是1001,也就是说,当HashMap长度为10的时候,有些index结果的出现几率
    会更大而有些index结果永远不会出现(比如0111),这样就不符合hash均匀分布的原则

    反观长度16或者其他2的幂,length - 1的值是所有二进制位全为1,这种情况下,index的结果等同于hashcode后几位的值
    只要输入的hashcode本身分布均匀,hash算法的结果就是均匀的

    所以,HashMap的默认长度为16,是为了降低hash碰撞的几率

    展开全文
  • 我发现哪怕10年后,这文章也没过时,很多人还是没拎清 冲突概率和样本空间的关系。 前段时间跟某大牛叽歪的时候,被提到我写的一篇文章(用CRC32实现短网址的一篇)里提到的CRC32算法有误。今天写代码,恰好需要用到这...

    注:这篇文章源自我10年前写的博客,今天看到有人谈密码安全的,再发一遍和大家讨论下。我发现哪怕10年后,这文章也没过时,很多人还是没拎清 冲突概率和样本空间的关系。

    前段时间跟某大牛叽歪的时候,被提到我写的一篇文章(用CRC32实现短网址的一篇)里提到的CRC32算法有误。今天写代码,恰好需要用到这个函数,想起来了,就又回去看了下。确认了下,原先的文章并没有错误,但是有一处描述是很有问题的。

    原文是这样的,『综合以上的思路,决定采用CRC32来实现。CRC32也是一个哈希算法,和MD5类似,不过它是32位的,故更短一些,速度也更快。它所能表示的范围为40亿,也会产生冲突,但是对于一般应用足够了,这也是个成本很低廉的做法。』

    这只是提到的一种简单做法而已。但是确实是在这里可能误导数学不好的读者。我们知道,CRC32是32位的,MD5是128位(谁说16位、32位, 我敲死他。这里的位是bit,不是字符长度),也可以说是CRC128的演化版。通常我们习惯用MD5来做hash。但是我在之前文章为了简单和压缩长度,使用了CRC32。容易知道,CRC32的值域是2^32,即大约40亿。

    很多人想当然地理解为,CRC32的冲突概率是1/2^32,这是错的。

    对样本空间的误解

    这是不是说在实际应用中,我们就可以大胆使用CRC32了呢?因为一般来说,我们所用的数据很少过亿,更别说40亿了。在原文,我是作为短网址算法的引子展开的。就算腾讯那样的规模,也没那么容易超过40亿(腾讯的短网址算法是用在微博里的)。

    如果你回答,应该是的,那你的高数是周公教的。在这里,我们说的40亿分之一的指的是CRC32所拥有的样本空间。在概率论中,尤其要注意至少这样的字眼。CRC32的样本空间是2^32次方,这并不表 明在40亿(2的32次方)的数据中就才可能产生一对碰撞,而是比这大得多。

    假设有1000万组数据,

    则第一个数据不碰撞的概率为,1/4000000000

    第二个数据不和第一个碰撞的概率是(4000000000-1)/4000000000

    以此类推,1000万个数据完全不碰撞的概率是个小的不能再小的数字,反过来,就是有可能碰撞了,即“完全不碰撞”的逆事件。1减去一个小的不能再小的数据,那么就是一个大的不能再大的数据了(和小于1的数比较)。想到了什么?生日悖论!不是吗?

    生日悖论

    也叫做"生日问题"(birthday problem):一个班级需要有多少人,才能保证每个同学的生日都不一样?

    答案很出人意料。如果至少两个同学生日相同的概率不超过5%,那么这个班只能有7个人。事实上,一个23人的班级有50%的概率,至少两个同学生日相同;50人班级有97%的概率,70人的班级则是99.9%的概率。

    这意味着,如果哈希值的取值空间是365,只要计算23个哈希值,就有50%的可能产生碰撞。也就是说,哈希碰撞的可能性,远比想象的高。

    来推算一下:

    至少两个人生日相同的概率,可以先算出所有人生日互不相同的概率,再用 1 减去这个概率。

    我们把这个问题设想成,每个人排队依次进入一个房间。第一个进入房间的人,与房间里已有的人(0人),生日都不相同的概率是365/365;第二个进入房间的人,生日独一无二的概率是364/365;第三个人是363/365,以此类推。

    因此,所有人的生日都不相同的概率,就是下面的公式。

    912d7a40664eb0080c9ba27f0c3f0df5.png

    生日悖论

    上面公式的 n 表示进入房间的人数。可以看出,进入房间的人越多,生日互不相同的概率就越小。

    这个公式可以推导成下面的形式。

    7f840a63d07e9074cb151ca866c513b6.png

    生日悖论公式

    那么,至少有两个人生日相同的概率,就是 1 减去上面的公式。

    6c379dd48164a9b743ad0e13da3129ff.png

    两个人生日相同概率

    Hash冲突的概率

    同理。

    任意两个数经过CRC32后不碰撞,是一个随机事件。根据期望的线性限制,对模型简化,可以得到,碰撞对的数目,即E(X)=k(k-1)/2n,代入1000万,结果可知。实际上,只需要92682组数据,CRC32就已经有碰撞的可能性了。

    那么为了让1000万组数据碰撞的可能性不大于1/2,也该有多少位呢?如果利用从一个全散列中随机选出的散列函数h,将n个关键字存储到一个大小为 m=n^2的那么出现碰撞的概率小于1/2.E(X)=(n,2)*1/n^2<1/2。即N的桶最好承载square(N)的数据,这样保证冲突概率小于50%。

    到这里已经很清楚了,CRC32不是足够用,而是用不成的。

    很轻松就能举出CRC32碰撞的例子,因为它的碰撞概率不到10W分之一,随便写个循环就可以跑出来。

    我举个例子

    package baicai.other;import java.util.zip.CRC32;public class Crc32 {    public static void main(String[] args) {        CRC32 crc32 = new CRC32();        crc32.update("86821".getBytes());        System.out.println(crc32.getValue());        CRC32 crcTwo = new CRC32();        crcTwo.update("14740600".getBytes());        System.out.println(crcTwo.getValue());    }}

    这个例子,两个数字就冲突了,它们的CRC32结果都是 350569284

    917ed7c2eee46ef6c2a0cc5f183ec404.png

    CRC32冲突实例

    那MD5呢,MD5冲突概率虽然小得多,但也是很容易发生的,也很容易构造。这里也给个例子

    下面这张图片,它显示的内容也是它本身的MD5值,这明显是精心构造的碰撞

    57c650685897afbd3bb9e1536e517fa1.gif

    构造MD5冲突的图片

    [ren@ren-pc 下载]$ md5sum md5.gif f5ca4f935d44b85c431a8bf788c0eaca  md5.gif

    注:由于上传的关系,这种图片可能被压缩,会导致你验证失败。各位读者可以自行下载验证下。

    展开全文
  • Hash 和 hash碰撞

    2019-12-21 18:33:55
    ,这是一个极小极小的数字——而即便是在MD5被王小云教授破解之后,其碰撞概率上限也高达 ,也就是说,至少需要找 次才能有1/2的概率来找到一个与目标文件相同的hash值。而对于两个相似的字符串,MD5加密结果如下: ...

    hash(散列、杂凑)函数,是将任意长度的数据映射到有限长度的域上。直观解释起来,就是对一串数据m进行杂糅,输出另一段固定长度的数据h,作为这段数据的特征(指纹)。
    也就是说,无论数据块m有多大,其输出值h为固定长度。到底是什么原理?将m分成固定长度(如128位),依次进行hash运算,然后用不同的方法迭代即可(如前一块的hash值与后一块的hash值进行异或)。如果不够128位怎么办?用0补全或者用1补全随意,算法中约定好就可以了。
    原问题回答完毕。但是既然要说hash算法,不妨说的更透彻些。
    =================分割线==========
    由于用途的不同,hash在数据结构中的含义和密码学中的含义并不相同,所以在这两种不同的领域里,算法的设计侧重点也不同。

    预备小知识:
    抗碰撞能力:对于任意两个不同的数据块,其hash值相同的可能性极小;对于一个给定的数据块,找到和它hash值相同的数据块极为困难。
    抗篡改能力:对于一个数据块,哪怕只改动其一个比特位,其hash值的改动也会非常大。
    在用到hash进行管理的数据结构中,比如hashmap,hash值(key)存在的目的是加速键值对的查找,key的作用是为了将元素适当地放在各个桶里,对于抗碰撞的要求没有那么高。换句话说,hash出来的key,只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能,直接与hash值产生的速度有关,所以这时候的hash值的产生速度就尤为重要,以JDK中的String.hashCode()方法为例:

    
     
    1. public int hashCode() {
    2. int h = hash;
    3. //hash default value : 0
    4. if (h == 0 && value.length > 0) {
    5. //value : char storage
    6. char val[] = value;
    7. for ( int i = 0; i < value.length; i++) {
    8. h = 31 * h + val[i];
    9. }
    10. hash = h;
    11. }
    12. return h;
    13. }

    很简洁的一个乘加迭代运算,在不少的hash算法中,使用的是异或+加法进行迭代,速度和前者差不多。

    在密码学中,hash算法的作用主要是用于消息摘要和签名,换句话说,它主要用于对整个消息的完整性进行校验。举个例子,我们登陆知乎的时候都需要输入密码,那么知乎如果明文保存这个密码,那么黑客就很容易窃取大家的密码来登陆,特别不安全。那么知乎就想到了一个方法,使用hash算法生成一个密码的签名,知乎后台只保存这个签名值。由于hash算法是不可逆的,那么黑客即便得到这个签名,也丝毫没有用处;而如果你在网站登陆界面上输入你的密码,那么知乎后台就会重新计算一下这个hash值,与网站中储存的原hash值进行比对,如果相同,证明你拥有这个账户的密码,那么就会允许你登陆。银行也是如此,银行是万万不敢保存用户密码的原文的,只会保存密码的hash值而而已。
    在这些应用场景里,对于抗碰撞和抗篡改能力要求极高,对速度的要求在其次。一个设计良好的hash算法,其抗碰撞能力是很高的。以MD5为例,其输出长度为128位,设计预期碰撞概率为1/2^{64},这是一个极小极小的数字——而即便是在MD5被王小云教授破解之后,其碰撞概率上限也高达1/2^{41},也就是说,至少需要找2^{40}次才能有1/2的概率来找到一个与目标文件相同的hash值。而对于两个相似的字符串,MD5加密结果如下:

    
     
    1. MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
    2. MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8";

    可以看到仅仅一个比特位的改变,二者的MD5值就天差地别了。

    二,什么是hash碰撞呢?怎么处理?

     

    如果两个输入串的hash函数的值一样,则称这两个串是一个碰撞(Collision)。既然是把任意长度的字符串变成固定长度的字符串,所以必有一个输出串对应无穷多个输入串,碰撞是必然存在的。

    一个优良的hash函数 f 应当满足以下三个条件:

    (1)对于任意y,寻找x,使得f(x)=y,在计算上是不可行的。

    (2)给定x1∈A,找x2∈B,,使得f(x1)=f(x2),在计算上是不可能的,这也就是弱无碰撞性。

    (3)寻找x1,x2,使得f(x1)=f(x2),在计算上也是不可行的,这也就是强无碰撞性。

    这样就称为安全保密的Hash函数,除了枚举外不可能有别的更快的方法。如第3条,根据生日定理,要想找到这样的x1,x2,理论上需要大约2^(n/2)的枚举次数。

    因为前两条都能被破坏的hash函数太弱而被抛弃,几乎所有的hash函数的破解,都是指的破坏上面的第3条性质,即找到一个碰撞。在密码学上还有一个概念是理论破解,指的是提出一个算法,使得可以用低于理论值得枚举次数找到碰撞。

     

     

     

    4、碰撞处理

       通常有两类方法处理碰撞:开放寻址(Open Addressing)法和链接(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中;后者通常是把散列到同一槽中的所有元素放在一个链表中,而将此链表的头指针放在散列表T[0..m-1]中。

    (1)开放寻址法

      所有的元素都在散列表中,每一个表项或包含动态集合的一个元素,或包含NIL。这种方法中散列表可能被填满,以致于不能插入任何新的元素。在开放寻址法中,当要插入一个元素时,可以连续地检查或探测散列表的各项,直到有一个空槽来放置待插入的关键字为止。有三种技术用于开放寻址法:线性探测、二次探测以及双重探测。

    <1>线性探测

      给定一个普通的散列函数h':U —>{0,1,.....,m-1},线性探测方法采用的散列函数为:h(k,i) = (h'(k)+i)mod m,i=0,1,....,m-1  

         探测时从i=0开始,首先探查T[h'(k)],然后依次探测T[h'(k)+1],…,直到T[h'(k)+m-1],此后又循环到T[0],T[1],…,直到探测到T[h'(k)-1]为止。探测过程终止于三种情况: 
      (1)若当前探测的单元为空,则表示查找失败(若是插入则将key写入其中); 
      (2)若当前探测的单元中含有key,则查找成功,但对于插入意味着失败; 
      (3)若探测到T[h'(k)-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。

      线性探测方法较容易实现,但是存在一次群集问题,即连续被占用的槽的序列变的越来越长。采用例子进行说明线性探测过程,已知一组关键字为(26,36,41,38,44,15,68,12,6,51),用除余法构造散列函数,初始情况如下图所示:

    散列过程如下图所示:

    <2>二次探测

       二次探测法的探查序列是:h(k,i) =(h'(k)+i*i)%m ,0≤i≤m-1 。初次的探测位置为T[h'(k)],后序的探测位置在次基础上加一个偏移量,该偏移量以二次的方式依赖于i。该方法的缺陷是不易探查到整个散列空间。

    <3>双重散列

      该方法是开放寻址的最好方法之一,因为其产生的排列具有随机选择的排列的许多特性。采用的散列函数为:h(k,i)=(h1(k)+ih2(k)) mod m。其中h1和h2为辅助散列函数。初始探测位置为T[h1(k)],后续的探测位置在此基础上加上偏移量h2(k)模m。

     (2)链接法

      将所有关键字为同义词的结点链接在同一个链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1。

      举例说明链接法的执行过程,设有一组关键字为(26,36,41,38,44,15,68,12,6,51),用除余法构造散列函数,初始情况如下图所示:

    最终结果如下图所示:

     

     

    三 ,为什么HashMap初始容量是2<<3?

     

     

    如果两个元素不相同,但是hash函数的值相同,这两个元素就是一个碰撞

    因为把任意长度的字符串变成固定长度的字符串,所以存在一个hash对应多个字符串的情况,所以碰撞必然存在

    为了减少hash值的碰撞,需要实现一个尽量均匀分布的hash函数,在HashMap中通过利用key的hashcode值,来进行位运算
    公式:index = e.hash & (newCap - 1)

    举个例子:
    1.计算"book"的hashcode
        十进制 : 3029737
        二进制 : 101110001110101110 1001

    2.HashMap长度是默认的16,length - 1的结果
        十进制 : 15
        二进制 : 1111

    3.把以上两个结果做与运算
        101110001110101110 1001 & 1111 = 1001
        1001的十进制 : 9,所以 index=9

    hash算法最终得到的index结果,取决于hashcode值的最后几位

    为了推断HashMap的默认长度为什么是16
    现在,我们假设HashMap的长度是10,重复刚才的运算步骤:
    hashcode : 101110001110101110 1001
    length - 1 :                                     1001
    index :                                            1001

    再换一个hashcode 101110001110101110 1111 试试:
    hashcode : 101110001110101110 1111
    length - 1 :                                     1001
    index :                                            1001

    从结果可以看出,虽然hashcode变化了,但是运算的结果都是1001,也就是说,当HashMap长度为10的时候,有些index结果的出现几率
    会更大而有些index结果永远不会出现(比如0111),这样就不符合hash均匀分布的原则

    反观长度16或者其他2的幂,length - 1的值是所有二进制位全为1,这种情况下,index的结果等同于hashcode后几位的值
    只要输入的hashcode本身分布均匀,hash算法的结果就是均匀的

    所以,HashMap的默认长度为16,是为了降低hash碰撞的几率

     

     

     

    展开全文
  • Hash函数碰撞概率公式 生日问题 这个问题在数学上早有原型,叫做"生日问题"(birthday problem):一个班级需要有多少人,才能保证每个同学的生日都不一样? 答案很出人意料。如果至少两个同学生日相同的概率不超过5...
  • hash碰撞处理

    2017-08-16 15:07:34
    hash碰撞处理 对于Hash,我们是怎样来处理冲突的。现在就来介绍一些经典的Hash冲突处理的方法。主要包括    (1)开放地址法  (2)拉链法  (3)再哈希法  (4)建立公共溢出区   (1)开放地址...
  • 来自:http://www.cnblogs.com/xuanhun/archive/2012/01/01/2309571.html1.Hash与Hash碰撞 Hash,简单来讲,是一种将任意长度的输入变换成固定长度的输出,固定长度的输出在“实际应用场景”下可以代表该输入。...
  • HashMap是大家都在用,面试的时候也经常会被考的考点,在这篇文章中介绍下HashMap的hash碰撞和减轻碰撞的优化。 1、什么是hash碰撞 在解释Hash碰撞之前先说一下hashmap的存储结构、添加和检索是怎么实现的 1.1...
  • 内部已经实现equals和hashcode方法,遵循hashmap内部规范计算准确性,有效减少hash碰撞的几率, 2.如果使用object作为key,需要重写equals和hashcode方法,equals保证key在hash表中唯一,hashcode计算存储位置; 3.不直接...
  • java hash碰撞分析模拟

    千次阅读 2017-09-14 18:10:02
    此漏洞利用碰撞相同的hash值得到一个长链表, 重新get时,map的计算过程会将时间复杂度巨增,原来一个简单的过程将变成一个很费cpu的过程。 常见的服务器会将用户post的数据保存在hashmap中. 而向hash
  • 解决hash碰撞问题

    千次阅读 2016-09-09 16:32:18
    若采用线性探测的开放定址法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为 ____ ; 若利用拉链法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为 ____ 线性探测法: 3
  • 一 ,到底什么是hash呢? 作者:知乎用户 链接:https://www.zhihu.com/question/26762707/answer/40119521 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 hash(散列、杂凑)...
  • HashMap hash碰撞分析

    千次阅读 2014-05-06 14:53:41
    HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时,系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法,都可...
  • 一 ,到底什么是hash呢? 作者:知乎用户 链接:https://www.zhihu.com/question/26762707/answer/40119521 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 hash(散列、杂凑)...
  • 实现,即使用拉链法处理数据碰撞,即对key进行hash后的索引如果相同,就放在一个链表中,如图 虽然这能很好的解决数据碰撞的问题,但是随着链表中的元素越来越多,数据查找的时间复杂度为O(1+N),查询效率将会变...
  • 计算随机情况下HASH发生碰撞概率

    千次阅读 2011-09-14 16:31:54
    // 计算随机情况下HASH碰撞率 // 不碰撞率 // f(N,1) = 1.0; // f(N,2) = 1.0-1/N; // f(N,k+1) = f(N,k)*(N-k)/N // f(N,k) = (N-1)*(N-2)...(N-(k-1))/(N^(k-
  • 为什么使用开放地址法解决Hash冲突 由于哈希值的空间远小于输入的空间,所以经过散列处理后,仍然出现不同数据对应相同的数组下标,这时候就产生了哈希冲突。 解决哈希冲突有以下四种方法: 1、链式地址法(java....
  • 所谓哈希(hash),就是将不同的输入映射成独一无二的、固定长度的值(又称"哈希值")。它是最常见的软件运算之一。 如果不同的输入得到了同一个哈希值,就发生了"哈希碰撞"(collision)。 ...
  • 不管是环形数组还是弱引用的ThreadLocal,产生hash碰撞的本质原因是有多个实例,而这多个实例在环形数组且弱引用的ThreadLocal中会增加产生hash碰撞概率。 解决hash碰撞 这里假设已经产生了碰撞 假如已经有一个...
  • 我是架构精进之路,点击上方“关注”,坚持每天为你分享技术干货,私信我回复“01”,送你一份程序员成长进阶大礼包。HASH算法介绍散列函数(英语:Hash function)又称散列算法、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,516
精华内容 4,606
热门标签
关键字:

hash碰撞的概率