到底什么是hash呢?hash碰撞?为什么HashMap的初始容量是16?

到底什么是hash呢?hash碰撞?为什么HashMap的初始容量是16?一,到底什么是hash呢?作者:知乎用户链接:https://www.zhihu.com/question/26762707/answer/40119521来源:知乎著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。hash(散列、杂凑)函数,是将任意长度的数据映射到有限长度的域上。直观解释起来,就是对一串数据m进行杂糅,输出另一段固定长度的数据h,作为这段数据的…

大家好,又见面了,我是你们的朋友全栈君。

一 ,到底什么是hash呢?

作者:知乎用户
链接:https://www.zhihu.com/question/26762707/answer/40119521
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

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()方法为例:

    public int hashCode() {
        int h = hash;
 //hash default value : 0 
        if (h == 0 && value.length > 0) {
 //value : char storage
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

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

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

到底什么是hash呢?hash碰撞?为什么HashMap的初始容量是16?

散列过程如下图所示:

到底什么是hash呢?hash碰撞?为什么HashMap的初始容量是16?

<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),用除余法构造散列函数,初始情况如下图所示:到底什么是hash呢?hash碰撞?为什么HashMap的初始容量是16?

最终结果如下图所示:

到底什么是hash呢?hash碰撞?为什么HashMap的初始容量是16?

 

 

三 ,为什么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碰撞的几率

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/148592.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • MySQL数据类型选择「建议收藏」

    MySQL数据类型选择「建议收藏」前言在MySQL中,选择正确的数据类型,对于性能至关重要。一般应从以下两个方面考量:确定合适的大类型:数值、字符串、时间、二进制;确定具体的类型:有无符号、取值范围、变长定长等。在MySQL数据类型设置方面,尽量采用更小的数据类型,因为它们占用的存储空间更小,通常有更好的性能,花费更少的硬件资源。并且,尽量把字段定义为NOTNULL,避免使用NULL。1.字符串类型类型大小用途CHAR0-255字节定长字符串,char(n)当插入的字符串实际长度不足n时,插

  • Java单例模式实现的两种方式和应用场景

    Java单例模式实现的两种方式和应用场景单例模式的定义个人理解,单例是指单个实例,在整个应用程序当中有且仅有一个实例存在,该实例是通过代码指定好的(自行创建的)。为什么要使用解决在高并发过程中,多个实例出现逻辑错误的情况。在特定的业务场景下避免对象重复创建,节约内存。实现的两种方式饿汉式顾名思义,不管有没有使用到该对象,只要程序启动成功,该单实例对象就存在。代码如下:/***饿汉式*/publicclassSingletonHungry{privatestaticSingletonHung

  • 超详细Linux配置DHCP服务器

    超详细Linux配置DHCP服务器概述DHCP(DynamicHostConfigurationProtocol,动态主机配置协议)通常被应用在大型的局域网络环境中,主要作用是集中的管理、分配IP地址,使网络环境中的主机动态的获得IP地址、Gateway地址、DNS服务器地址等信息,并能够提升地址的使用率。工作原理1、客户端开机没有IP,局域网内需要发送一个广播形式的DISCOVER(局域网内不知道谁是DHCP服务器),只要能收…

  • RESETful API 设计规范

    RESETful API 设计规范

  • drupal安装教程mysql_Drupal8 安装教程

    drupal安装教程mysql_Drupal8 安装教程安装Drupal8需要环境环境:UNIX/Linux,OSX,或者windowsweb服务器:Apache2,nginx,MicrosoftIIS等数据库:推荐数据库Mysql(5.5.3),MariaDB(5.5.20),PerconaServer(5.5.8),支持:PostgreSql(9.1.2),SQLite(3.6.8)开始安装我的环境,OSX,Apache2,Mysql(…

  • ubuntu20.04 LTS_Ubuntu 20

    ubuntu20.04 LTS_Ubuntu 20Ubuntu22.04LTS正式发布,采用Linux5.17内核,包括桌面改进、视觉变化及系统功能。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号