到底什么是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)


相关推荐

  • 360奇安信天擎卸载不干净_奇安信Ateam

    360奇安信天擎卸载不干净_奇安信Ateam360天擎是什么具体可以参考:百度:360天擎总之,一些单位里为了安全防护,会在单位的电脑上安装360天擎,如果你想用自己的笔记本电脑连上单位的网络的话,也会要求你安装。不安装就连不上网络,但安装之后,卸载又是一个很大的难题。用什么卸载其实网上会有很多强力卸载软件,甚至有些会强力到可以卸载系统文件,这类软件不建议使用(如果用的明白,请自便)。无效方式如,腾讯管家自带的软件管理有效方式如,联想电脑管家,和微软自带的卸载,如下图:点击右键->卸载->完成?不不不,这

  • allowMultiQueries=true_python的list用法

    allowMultiQueries=true_python的list用法消息列表:消息 描述 WM_NOTIFICATION_CLICKED 控件被点击 WM_NOTIFICATION_RELEASED 控件被释放 WM_NOTIFICATION_MOVED_OUT 控件被点击,指针移出控件但没被释放 WM_NOTIFICATION_SEL_CHANGED 控件选中的内容被改变 常用函数LISTWHEEL_A…

  • 查看数据库隔离级别,mysql

    查看数据库隔离级别,mysql1.查看当前会话隔离级别select@@tx_isolation;2.查看系统当前隔离级别select@@global.tx_isolation;3.设置当前会话隔离级别setsessiontransactionisolatinlevelrepeatableread;4.设置系统当前隔离级别setglobaltransac…

  • winhttp 发送 get 请求「建议收藏」

    winhttp 发送 get 请求「建议收藏」由于微端要和服务器交互,而服务器又只有http协议的处理,所以需要用C++来模拟get或post请求。这是使用windowsapi来模拟get请求的,使用到的库有“winhttp”,头文件有“winhttp.h”,下面的代码来源于http://msdn.microsoft.com:12345678

  • 怎样安装pip_pip 安装本地python包

    怎样安装pip_pip 安装本地python包网上有各种方法安装pip,针对不同的系统方法还不一样,最后发现还是下面这种方法最简单,直接了当干脆方便,适用于Windows和Linux。(1)下载pip进入https://pypi.python.org/pypi/pip,下载第二项。(2)解压安装解压下载的文件(windows下只用解压工具解压如RAR,Linux下终端输入tar-xfpip-9.0.1.tar.gz,即tar-xf文件名

    2022年10月27日
  • navicat15激活码最新【在线注册码/序列号/破解码】

    navicat15激活码最新【在线注册码/序列号/破解码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

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

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