之前看HashMap源码时，总说HashMap数组大小要用2的n次幂，取模时用到的位运算，这样HashMap取模才会很快，也就知道了这个特性，没有去专门了解过，为什么用2的n次幂，可以用位运算来取模；由于最近看一些框架底层代码，位运算遇到的多了，有点好奇，就研究了下；发现这个取模确实很有趣；

一、(n -1) & hash 取模算法

HashMap取模算法

(n -1) & hash  就是计算，该key是在数组中的哪个位置，下面我们研究下这个(n -1) & hash；

首先是hash这个值，转成二进制，就是0和1，我们先用个例子来说明下，n=4，hash=11

11的二进制是1011

4的二进制是100

能整除的位

从上图可以看出，因为如果用2的n次幂，当转换成二进制后，高位肯定能整除低位（举个例子：上面的是8，肯定能整除4，8的下一位是16，肯定也能整除4，以此类推），所以高位可以直接舍弃掉，只用看同样位置后面的数；后面的数就为3，但是这个3要怎么得到呢；这就是 (n - 1) 和 &的精髓了；

大家都知道，&1得到的是原来的值，高位没有则不取；2进制数字， n-1则刚好得到的是2的n次幂小一位全是1的二进制数字，所以上面的列子中，最后是计算

两位数的&

就刚好可以直接把余数取出来；

看到这里了之后，突然想起来，我们创建HashMap时，可以指定HashMap的初始大小，那我们传进去一个不是2的n次幂的数字，那上面的就计算不了了，然后就接着研究了下，这个初始化的算法，也是相当精髓；

二、初始化数组大小

数组大小初始化 取最高位

我们来看看JDK1.7的数组初始化，这个逻辑清晰一些；首先我们得明白这一部分逻辑肯定是为了把我们传进来的数字，给变成2的n次幂才能进行上面的取模算法；我们先看看 Integer.highestOneBit((number -1) <<1)  这一部分；找到了highestOneBit这个方法的解释，意思就是取传进来的最高位，大概就是当传进来为7的话，2进制为111，最高位就是100，也就是4；得到的就是2的n次幂；

我们先看看括号里面的是什么意思，(number -1) <<1 ，就是我们传进来的数字减一，然后向左移一位；开始我的理解是向左移一位就是乘以2，之后才发现，我们得放弃我们得数学思维，不然就会想复杂了；这个向左移一位是为了取到一个大于我们传进来的数字且刚好能满足2的n次幂的数字，比如，我们传进来是7，二进制就是111，那刚好大于111的2的n次幂，肯定是1000，也就是8，所以，这个向左移一位，然后取最高位，就刚好满足条件，那我们就看出这段逻辑的大概意思了；HashMap数组的长度，就是给到一个最适合的数字，并且尽量能满足大部分的key能刚好落到数组上，不用进行链表的遍历，这样取值是最快的；

看到这里，开始我一直没明白这个 number -1 是什么意思，本来 number  << 1就可以满足条件了，为啥还得减一，最开始的时候也怀疑过是，我们传入的数组刚好是2的n次幂时，会有问题；其实只要一想到这个，就能明白这个意思，因为我们传入8的时候，如果向左移一位的话，就是16了，然后取最高位也是16，那就数组会比原来大一倍；但是我开始觉得，如果我们能在移位之前判断这个数字是不是2的n次幂后再进行移位，这样是不是就不用减一了；然后比较下这两种处理方式的性能，才明白，直接减一肯定比判断这个数字是不是2的n次幂要简单的多，并且也快得多；并且当数字为2的n次幂时，减一肯定不会使二进制数字的最高位移位，因为只有当数字为2的n次幂时，二进制数字才是最高位是1，后面全是0；其他任何情况，减一，都是修改非最高位数字，所以根本没影响；然后到这里，就完全明白了这段代码的逻辑，为啥HashMap性能高，因为全部是位运算；

三、highestOneBit运算

那到这里就完了吗；不，都研究到这里了，不把highestOneBit搞明白，我估计是睡不着觉了；开始看见这段逻辑我是拒绝的，这矩阵都是啥啥啥啊。。。算了，用最原始的方式来吧；看到这个方法，就发现，都是向右移，开始移一位进行或运算，然后移两位进行或运算，再移四位进行或运算......手动操作了下，就看明白了，我举个极端例子吧，当进入到这个方法刚好是2的n次幂，比如16，运算流程如下：

highestOneBit执行逻辑

因为最高位肯定是1，我们不用管后面的位数是什么数字，这个算法就是刚好能把所有位上全变成1，因为第一次移一位，进行一次或运算，这样，前两位肯定都是1了，然后再把前两位往右移两位，然后进行或运算，这样前四位就都是1了，再移4位，8位，16位。。。这样就得到了所有位上全是1的二进制数字了，然后把这个二进制数字向右移一位，然后减掉，就得到了只有最高位是1，后面全是0的，2的n次幂数字了；

四、JDK8中HashMap链表扩容

JDK8 HashMap链表扩容 JDK7 HashMap链表扩容

分析了上面一块位运算，然后看到了JDK8，如果遇到链表结构，迁移时，居然没有用到取模算法去获取该节点的位置，直接分成两类，一类直接迁入新数组的同样索引位置，一类直接迁入同样索引加上原来数组长度的索引位置；网上有人说，这个是2的n次幂特性，其实，这个是扩容选择双倍的特性；应为，举个例子：14%3=2  当3扩大两倍后 14%6=2，这是第一种情况；第二种情况，就是  17%3=2  扩大两倍后  17%6=5=2+3；其实这个想的话，很容易就能想的明白；这个是数学原理，然后我们再看看代码，这个是用位运算来代替这个原理；我们回到上面(n -1) & hash这个算法的原理上，看一下就能明白为什么这个直接&就能知道，要不要加原来数组长度了；比如当前有两个hash值，一个为17，一个为21，扩容前数组长度为4，扩容后为8；扩容前，都落在索引为1的位置；扩容后，一个在1，一个在5；下面我们看下二进制计算过程；

取模的值

首先1.8的算法直接用hash和原来数组的大小直接进行&运算，运算后，要么是0要么是原来数组的长度（可以用上面的例子来进行验证下，因为是2的n次幂，所以只有一位上是1，其他位上全是0）；然后这一&运算，运算后，就能知道扩容时，原来差的那一位到底是1，还是0；如果是1的话，得到的值肯定是大于0的，是0的话，得到的值肯定是0；然后我们再看下，如果用原来的(n -1) & hash算法时，如果原来位置上是0，扩容后进行这个运算，得到的值是原值；如果原来位置上是1，扩容后进行这个运算，得到的值就是，数组原值最高位上，少了个1，这样转成10进制，就是刚好加上原值就行；所以这个就是为什么不用重新进行(n -1) & hash，只需要 (hash&oldcap) 的原理;