1.HashMap几个问题的提出

看过jdk8源码的小火把肯定在第一次看完后就会有疑问，主要疑问在一下几个问题：

2.为什么要用有hashCode()?

不管是在存数据，还是在取数据的时候，均会下调用hash(Object key)这个方法，hash(Object key)源码如下：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

2.1 存的时候

获得hash之后，简单的位运算后就可以直接在数组中定位所在下标的位置。直接定位数组的index存入效率O(1)，（当然如果有hash冲突的情况，如果有hash冲突，同样是最快的，只需要另外调用equals()方法做后续比较即可）：

if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

2.2 取的时候

在取的时候，同样直接定位到数组index的位置获取元素，效率O(1)，（当然如果有hash冲突的情况，如果有hash冲突，同样是最快的，只需要另外调用equals()方法做后续比较即可）：

(first = tab[(n - 1) & hash]) != null) {

2.3 hashCode()总结

从存取两侧层面可以看使用hashCode()的方式是最快的。没有之一，如果使用遍历数组的方式去查找，黄花菜都凉了，O(n)了大哥。

3.为什么初始容量为16？或者说为什么在构造器中给了一个初始容量大小，它还是会把他修改为大于等于次数的最小2的n次幂的形式？

关于容量在哪里用到了？取的时候都会用到，即存取均用到了这行代码： tab[i = (n - 1) & hash]

上面提到在获取hash之后会做一个简单的位运算。我们分析一下这个为运算：

i = (n - 1) & hash

先给出结论：

为了不让下标越界为了hash分布的更均匀

3.1 为了不让下标越界

当capacity = n 为2的幂次的时候，n-1的二进制应该是这种情况,下面看一下二进制的情况： n= 1000… //以1开头，后面为n个0的情况。 那么n-1= 0111…//以0开头，后面均为1的情况 如：

十进制n二进制n-1二进制2100141000118100001111610000011113210000001111164100000001111111281000000001111111256100000000011111111………

(n - 1) & hash :&意为且。均为1则为1，这样就保证这个&运算的结果，永远不可能大于(n - 1)的值，即永远不会大于等于capacity 。最大索引为capacity -1。

3.2 为了hash分布的更均匀

&：对应为之均为1结果才为1. i = (n - 1) & hash的值，即i的值，怎么保证Node在table中是均匀存放的呢？ 反例证明：如果n的值不是2的n次幂的形式，n-1就会出现二进制末尾为0的情况，即：n-1 = ***0（前面n为可以为0或者1），这回造成一个生命现象呢？ 索引永远不会落在二进制下边为1结尾的索引上。会有一半的索引为空闲状态，进而会使结尾为0（二进制）的索引上发生hash冲突的概率为原来的2倍。会造成插入和查询的效率损失。

4.tableSizeFor()方法解析

源码：

/** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

先说结论：就是大于等于cap的最小2的n次幂：

cap返回值1258101622325064 先说下为什么要cap - 1： int n = cap - 1;

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。 再分析重头戏，下面的这几行代码：

n |= n >>> 1; 表示：n = (n | n >>> 1) |或：对应为只要有1几位1 分析开始： 假设 n的二进制为：01xxxxxxxxxxxxxx…右移一位： 001xxxxxxxxxxxxxx…与n求或n的值:011xxxxxxxxxxxxxx…同理， n |= n >>> 2;行执行完后n = 01111xxxxxxxxxxxxxxxxxxxxxxxxxxxx同理， n |= n >>> 4;行执行完后n = 011111111xxxxxxxxxxxxxxxxxxxxxxxx同理， n |= n >>> 8;行执行完后n = 01111111111111111xxxxxxxxxxxxxxxx同理， n |= n >>> 16;行执行完后n = 011111111111111111111111111111111到这里是不是熟悉了，return的时候最后在加1，正好又回到了100000…，前面一个1后面全是0的状态，即此方法返回的就是2的n次幂。

4 乘子31的问题解释

一句话为了让hash的分布更为均匀，他是素数 源码：

public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }

具体为什么要选择31呢？请参考：【jvm】科普：为什么 String hashCode 方法选择数字31作为乘子https://blog.csdn.net/happydecai/article/details/80493237

到此分享完毕，有不正确的请多多指正。

前路无畏 认证博客专家 专家认证 自律的艰辛总甜过懊悔的苦果！专注于java后端技术及解决方案，善于总结，分享！自律的艰辛总甜过懊悔的苦果！专注于java后端技术及解决方案，善于总结，分享！自律的艰辛总甜过懊悔的苦果！专注于java后端技术及解决方案，善于总结，分享！