HashMap的大小为什么必须是2的倍数

了解HashMap的都知道，HashMap的大小必须是2的倍数，通过调用tableSizeFor方法来保证HashMap的大小为2的次方，如果你在构造函数中传入了大小，HashMap会调用tableSizeFor方法将大小变成大于你传入的数的最小2的倍数

HashMap的底层数据结构是数组+链表+红黑树，这个大家都知道，数据也是保存在table数组上面

将元素放在table数组上面，是用hash值%数组大小定位位置，而HashMap是用hash值&(数组大小-1)，却能和前面达到一样的效果，这就得益于HashMap的大小是2的倍数，2的倍数意味着该数的二进制位只有一位为1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和%一样的效果，并且位运算比%的效率高得多，这是一个方面

第二个方面是在扩容时，利用扩容后的大小也是2的倍数，将已经产生hash碰撞的元素完美的转移到新的table中去

我们先来看看HashMap的扩容机制，如果看过源码的朋友一定都知道，HashMap中的元素在超过负载因子*HashMap大小时就会产生扩容在源码中来表示是在putVal函数中

 扩容时，首先创建一个2倍大的旧table，然后将旧table中的数据转移到新table中来，这其中就分为三种情况

第一：该位置只有一个元素，没有后序节点，直接使用前面说的hash值&（新数组大小-1）放置到新table中去

第二：假如该节点是红黑树的根节点，就会走红黑树的转移方式

 第三：该节点是一个链表，则会遍历该链表，具体做法如下

HashMap使用这种方法完美的避免了再次去进行哈希碰撞，仅只用了O（n）的时间复杂度，就将数据完成了转移，这一点也得益于HashMap的大小为2的倍数，下面我们来分析一下，为什么元素会只存在于新table的旧下标位置和旧下标+旧数组大小的位置？为什么元素的hash值&旧数组大小为0就一定在新table的旧下标位置，非0一定在新table的旧下标位置+旧数组大小位置？

假设有如下二进制数字

从图片中也可以看出，元素在新table中的位置，关键是在红框圈起来的hash二进制位是0还是1

如果是0的话，hash值&旧数组大小，就一定是0

如果是1的话，hash值&旧数组大小，就一定是非0

以上就是HashMap为什么一定规定大小是2的倍数

HashMap的运算效率跟数据的散列程度有很大的关系，为此HashMap为了散列数据做了很大的努力。

首先通过JVM支持的hashCode方法，得到一个hash值，然后通过HashMap中的hash值，然后将HashCode右移16位和本身做异或运算，保证数据的高16位也参与运算，使hash值更加随机化，综合时间复杂度和空间复杂度选择0.75作为负载因子，在HashMap中的元素个数超过负载因子*HashMap数组大小的时候，就会进行扩容，保证数据的散列，在扩容时依靠数组大小为2的倍数，将一个链表或者红黑树进行更加随机的拆分，这里主要是，旧数组的大小为2的倍数，这样我们也不知道二进制位为1的位是奇数位还是偶数位，更加随机的转移。

前面扩容第二点的时候会走红黑树的转移方式，我们这边看一下源码

可以发现，这边有一个非常熟悉的东西，没错就是两个链表的头结点和尾结点，红黑树的扩容数据转移跟链表是一样的，只不过它会在最后判断两个链表的长度，如果长度少于等于6，则会退化成链表，否则就会构造成红黑树