为什么HashMap的初始容量是16

向右看齐 2022-03-18 01:17 379阅读 0赞

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

[https://blog.csdn.net/qq\_35583089/article/details/80048285][https_blog.csdn.net_qq_35583089_article_details_80048285]

一 ，到底什么是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值相同的数据块极为困难。  
抗篡改能力：对于一个数据块，哪怕只改动其一个[比特位][Link 1]，其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.   
8.  `for (int i = 0; i < value.length; i++) {`
9.  `h = 31 * h + val[i];`
10. `}`
11. `hash = h;`
12. `}`
13. `return h;`
14. `}`
15.

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

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

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

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

二，什么是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)，用除余法构造散列函数，初始情况如下图所示：

![27221539-e3de5525fd6648b6b1420d41f32884d2.png][]

散列过程如下图所示：

![27222340-9f285bd1c87d438e9a8ffb75db9ea37d.png][]

<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)，用除余法构造散列函数，初始情况如下图所示：![27224437-8b63e902839b467080d6c758955cb492.png][]

最终结果如下图所示：

![27225206-e969b13cdc2c4fa4867888838ed26d15.png][]

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

[https_blog.csdn.net_qq_35583089_article_details_80048285]: https://blog.csdn.net/qq_35583089/article/details/80048285
[Link 1]: https://www.baidu.com/s?wd=%E6%AF%94%E7%89%B9%E4%BD%8D&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[1_2_64]: https://www.zhihu.com/equation?tex=1%2F2%5E%7B64%7D+
[1_2_41]: https://www.zhihu.com/equation?tex=1%2F2%5E%7B41%7D+
[2_40]: /images/20220318/91e0fd5f2afb46d5a561af30d20f40c3.png+
[Link 2]: https://www.baidu.com/s?wd=%E5%A4%A9%E5%B7%AE%E5%9C%B0%E5%88%AB&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[27221539-e3de5525fd6648b6b1420d41f32884d2.png]: /images/20220318/f599313429bf4ee69ba1f7897738cefc.png
[27222340-9f285bd1c87d438e9a8ffb75db9ea37d.png]: /images/20220318/71886d51084647c18d49f4930e3b01bf.png
[h1]: https://www.baidu.com/s?wd=h1&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[27224437-8b63e902839b467080d6c758955cb492.png]: /images/20220318/ff4a753938a64930ae1be1c1d76122d3.png
[27225206-e969b13cdc2c4fa4867888838ed26d15.png]: /images/20220318/ceeace60147e46b4891ec5c2b9c18df4.png