Hashmap是Java中最常用的集合类型，使用非常广泛。不过，有些细节问题很多人没有关注过，这也使很多人在面试时栽了跟头！比如，阿里很多团队为了考察候选人的基础，就出了这么一个面试题：为什么HashMap的初始长度和扩容长度是2的N次幂？

HashMap的数据结构

先了解一下HashMap的数据结构，在java中，数组和链表是最常用的两个基础数据结构，很多集合类都基于他们实现。HashMap也不例外，是一个链表数组，即数组和链表的结合体，当链表长度超过8时，链表转换为红黑树。

 

如上图，HashMap的数组元素存放了key-value键值对或者链表。当新建一个HashMap的时候，就会初始化一个数组。我们来看看java代码：

 

table 就是那个数组，Node是数组中的元素，Node中存放了key，value键值对。

 

当table中某个位置发生hash冲突时，就会自动拉链，该位置的元素也就变成了Node链表。从上图我们可以看到next成员变量，next会指向链表的下一个元素。

当我们往HashMap中put元素的时候，会先根据key的hashCode值计算出数组中对应的位置（下标），然后再把这个元素的key，value封装成Node放到对应的位置上。如果这个元素所在的位置已经存放了其他元素，那么在同一个位置上的元素将以Node链表的形式存放，新加入的Node放在链表头。从HashMap中get元素时，首先会根据key的hashCode值计算出数组中对应的位置，然后通过equals方法在对应位置的链表中找到相应的元素。所以，我们要尽量减少Hash冲突，如果每个位置上只有一个元素而不是形成链表，HashMap的效率将是最高的，时间复杂度将达到最理想的O(1)。不过现实场景中，基本都会拉链，HashMap查询过程也往往需要做链表遍历，这也导致了查询效率的下降。在Java1.8后HashMap数据结构中引入了红黑树，当链表过长时，链表会被转化为树形结构，以此来降低查询时遍历的层级和次数。

为什么长度是2的N次幂？

先了解一下哈希算法。Hash（哈希），一般翻译成散列，Hash是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值（Hash值）。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说Hash算法就是一种将无限的数据映射到有限地址空间的算法。

我们可以看到在HashMap中要找到某个元素，需要根据key的hashcode（hash值）来求得对应数组中的位置。这种将较大规模的输入数据映射到有限地址空间的算法就是hash算法（hashmap初始化时数组长度只有16，但基于链表数组的数据结构，hashmap可存储的元素数量却远大于16）。前面说过hashmap的数据结构是数组和链表的结合，所以我们希望hashmap里的元素尽量分布均匀些，尽量使每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以取到数组上对应位置的元素，而不用再去遍历链表。

可能很多人想到了用hashcode对数组长度取模得到数组下标位置，不错，取模的方式确实可以让数据分布比较均匀。但是，有没有更好的方式呢？

 

Hashmap是利用位运算实现的，位运算是基于二进制进行计算的，在计算机世界里所有数据最终都要转为二进制数据，所以位运算的效率非常高。位运算效率至少比取模运算高一个数量级。从上图可以看到，Hashmap在put（get）元素时通过 (n-1) & hash 做位运算，来获取数组下标位置，其中n是数组长度。

利用key的hashcode值，和数组的长度减一（n-1）做“与”运算。使用位运算，除了效率高，还有其他玄机吗？当HashMap的容量是2的n次幂时，(n-1)的2进制也就是11111***111这样形式的，此时与key的hashcode值进行位运算时，能够充分的散列，使添加的元素能够均匀分布在数组的每个位置上，使hash碰撞几率降到最低，下面举例说明。

 

HashMap的长度是16（2的4次幂）时，它的二进制是10000，(n-1)的二进制是01111，与hash值的计算结果如上图所示。我们可以看到当hashmap长度是2的n次幂时，n-1与不同的hashcode值的位运算结果都不一样，添加的元素能够均匀分布在数组的不同位置，降低了hash冲突。

 

再看看HashMap的长度不是2的N次幂的情况，假设长度是10，它的二进制是01010，(n-1)的二进制是01001，与hash值的计算结果如上图所示。我们可以看到当HashMap容量不是2的n次幂时，n-1与不同的hashcode值的位运算结果有好几个都一样，这样在添加元素时就产生了严重的hash冲突。

所以，当数组长度为2的n次幂时，不同的key通过位运算获取的数组下标冲突的几率会比较小。冲突少了，添加元素的效率自然会更高，数据在数组上的分布也会更均匀，相应的链表长度也比较短。查询时，由于数据分布均匀，链表长度也比较平均，减少了遍历次数，查询效率也就会更高。

位运算虽然不是什么高深的知识，但是和计算机底层操作非常紧密，是进阶程序高手的必备技能。如果你有读源码的习惯，会发现JDK中有很多对位运算的应用。我们在日常开发中，不妨多用用位运算，一来可以提高程序性能，二来也可以帮自己养成对技术精深探究的习惯，让自己在技术的道路上越走越远！