共计 3306 个字符，预计需要花费 9 分钟才能阅读完成。
文章目录：
①、抛出问题
②、给出论断
③、论证问题
④、& 和 % 运算效率比照
置信对 JDK 源码感兴趣的小伙伴，HashMap 的源码你肯定不要错过，外面有很多精妙的设计，也是面试的罕用考点，本文我会点出一些。
然而我不具体介绍 HashMap 源码，想理解的能够看我之前的文章，本篇文章次要是给大家解惑几个问题。
1、抛出问题
1.1 为什么 HashMap 的默认初始容量长度要是 1<<4 ?
为啥源码这里不间接写 16？要写成 1<<4？晓得的能够在评论区留言。
1.2 为什么 HashMap 初始化即便给定长度，仍然要从新计算一个 2^n^ 的数?
PS: 这个办法是 HashMap 用于计算初始化容量，后果是返回大于给定值的第一个偶数，比方 :
new HashMap(10)，其实理论长度是 16；
new HashMap(18)，理论长度是 32；
new HashMap(40)，理论长度 64。
波及到两个运算符：
①、| : 或运算符。
②、>>> : 无符号右移运算符，挪动时疏忽符号位，空位以 0 补齐。
这个算法也比拟有意思，原理就是每一次运算都是将现有的 0 的位转换成 1，直到所有的位都为 1 为止；最初返回后果的时候，如果比最大值小，则返回后果 +1，正好将所有的 1 转换成 0，且进了一位，刚好是 2^n^。
1.3 为什么 HashMap 每次扩容是扩充一倍，也就是 2^1^ ?
当存入 HashMap 的元素占比超过整个容量的 75%（默认加载因子 DEFAULT_LOAD_FACTOR = 0.75）时，进行扩容，而且在不超过 int 类型的范畴时，左移 1 位(长度扩为原来 2 倍)
1.4 为什么 HashMap 的计算索引算法是 &，而不是 %？
新增加一个元素时，会计算这个元素在 HashMap 中的地位，算法分为两步：
①、失去 hash 值
PS：其实这里的算法能够钻研下，hashcode() 是一个 native 润饰的办法，返回一个 int 类型的值（依据内存地址换算进去的一个值），而后将这个值无符号右移 16 位，高位补 0，并与后面第一步取得的 hash 码进行按位异或 ^ 运算。
这样做有什么用呢？这其实是一个扰动函数，为了升高哈希码的抵触。右位移 16 位，正好是 32bit 的一半，高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。
这样混合后的低位掺杂了高位的局部特色，高位的信息也被变相保留下来。
也就是保障思考到高下 Bit 位都参加到 Hash 的计算中。
②、索引值 i = (n-1) & hash
这里的 n 是 HashMap 的长度，hash 是上一步失去的值。
留神：这里是用的按位与 &，而不是用的取模 %。
1.5 问题总结
大家发现没，通过我下面提出的四个问题，前三个问题 HashMap 的长度始终保持在 2^n^。
①、默认初始长度是 2^4^;
②、即便给定初始长度，其值仍旧是大于给定值的第一个偶数；
③、每次扩容都是扩充一倍，2^1^；
而后第四个问题，计算 HashMap 的元素索引时，咱们失去了一个 hash 值，竟然是对 HashMap 的长度做 & 运算，而不是做 % 运算，这到底是是为什么呢？
2、给出论断
咱们先间接给出论断：
当 lenth = 2^n^ 且 X >0 时，X % length = X & (length – 1)
也就是说，长度为 2 的 n 次幂时，模运算 % 能够变换为按位与 & 运算。
比方：9 % 4 = 1，9 的二进制是 1001 ,4-1 = 3,3 的二进制是 0011。9 & 3 = 1001 & 0011 = 0001 = 1
再比方：12 % 8 = 4,12 的二进制是 1100,8-1 = 7,7 的二进制是 0111。12 & 7 = 1100 & 0111 = 0100 = 4
下面两个例子 4 和 8 都是 2 的 n 次幂，论断是成立的，那么当长度不为 2 的 n 次幂呢？
比方：9 % 5 = 4，9 的二进制是 1001，5-1 = 4,4 的二进制是 0100。9 & 4 = 1001 & 0100 = 0000 = 0。显然是不成立的。
为什么是这样？上面咱们来详细分析。
3、论证论断
首先咱们要晓得如下规定：
①、”<<” 左移：按二进制模式把所有的数字向左挪动对应的位数，高位移出（舍弃），低位的空位补零。左移一位其值相当于乘 2。
②、”>>” 右移：按二进制模式把所有的数字向右挪动对应的位数。对于右边移出的空位，如果是负数则空位补 0，若为正数，可能补 0 或补 1，这取决于所用的计算机系统。右移一位其值相当于除以 2 。
③、”>>>” 无符号右移：左边的位被挤掉，对于右边移出的空位一律补上 0。
依据二进制数的特点，置信大家很好了解。
当初对于给定一个任意的十进制数 X~n~X~n-1~X~n-2~….X~1~X~0~，咱们将其用二进制的示意办法合成：
公式 1：
X~n~X~n-1~X~n-2~….X~1~X~0~ = X~n~2^n^+X~n-1~2^n-1^+……+X~1~2^1^+X~0~2^0^
回到下面的论断：当 lenth = 2^n^ 且 X >0 时，X % length = X & (length – 1)
以及对于除法，除以一个数能用除法分配律，除以几个数的和或差不能用除法分配律：
公式 2：
成立：（a+b）÷c=a÷c+b÷c
不成立：a÷（b+c）≠a÷c+a÷c
通过 公式 1 以及 公式 2 ，咱们能够得出当任意一个十进制除以一个 2^k^ 的数时，咱们能够将这个十进制转换成 公式 1 的示意模式：
如果咱们想求下面公式的余数，置信大家一眼就能看进去：
①、当 0<= k <= n 时，余数为 X~k~2^k^+X~k-1~2^k-1^+……+X~1~2^1^+X~0~2^0^ , 也就是说 比 k 大的 n 次幂，咱们都舍掉了（大的都能整除 2^k^），比 k 小的咱们都留下来了(小的不能整除 2^k^)。那么留来下来即为余数。
②、当 k > n 时，余数即为整个十进制数。
看到这里，咱们离证实论断曾经很近了。
再回到下面说的二进制的移位操作，向右移 n 位，示意除以 2^n^ 次方，由此咱们失去一个很重要的论断：
一个十进制数对一个 2^n^ 的数取余，咱们能够将这个十进制转换为二进制数，将这个二进制数右移 n 位，移掉的这 n 位数即是余数。
晓得怎么算余数了，那么咱们怎么去获取这移掉的 n 为数呢？
咱们再看 2^0^,2^1^,2^2^….2^n^ 用二进制示意如下：
0001，0010，0100，1000，10000……
咱们把下面的数字减一：
0000，0001，0011，0111，01111……
依据与运算符 & 的法则，当位上都是 1 时，后果才是 1，否则为 0。所以任意一个二进制数对 2^k^ 取余时，咱们能够将这个二进制数与（2^k^-1）进行按位与运算，保留的即是余数。
这就完满的证实了后面给出的论断：
当 lenth = 2^n^ 且 X >0 时，X % length = X & (length – 1)
4、& 和 % 运算效率
为什么要将 % 运算改为 & 运算，很显然是因为 & 运算在计算机底层只须要一个简略的 与逻辑门就能够实现，然而实现除法的确一个很简单的电路，大家感兴趣的能够上来钻研下。
我这里在代码层面，给大家做个测试，直观的比拟下速度：
public class HashMapTest {public static void main(String[] args) {
long num = 100000*100000;
long startTimeMillis1 = System.currentTimeMillis();
long result = 1;
for (long i = 1; i < num; i++) {result %= i;}
long endTimeMillis1 = System.currentTimeMillis();
System.out.println("%:"+ (endTimeMillis1 - startTimeMillis1));
long startTimeMillis2 = System.currentTimeMillis();
result = 1;
for (long i = 1; i < num; i++) {result &= i;}
long endTimeMillis2 = System.currentTimeMillis();
System.out.println("&:"+ (endTimeMillis2 - startTimeMillis2));
}
}打印后果如下：
差距还是很显著的，而且这个后果还会随着测试次数的增多而越拉越开。
