jdk源码分析之HashMap--为什么初始容量是2的n次幂

熟悉HashMap的人都知道，其底层是数组+链表结构实现，也就是说我们常用的get和put操作中，key要和底层的结构关联对应起来，先看一下HashMap的机构模型：

垂直方式是Entry<K,V>数组，水平方向是链表。

也就是说每一次get或者put，首先要在垂直方向找到数组索引位置，然后再查询或操作链表。首先看一下get方法的源码：

public V get(Object key) {

if (key == null)

return getForNullKey();

Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();

}

意思是如果key==null，直接从数组0号位置对应链表开始查询，否则执行getEntry方法并返回结果，接着看一下getEntry方法代码：

final Entry<K,V> getEntry(Object key) {

if (size == 0) {

return null;

}

int hash = (key == null) ? 0 : hash(key);

for (Entry<K,V> e = table[indexFor(hash, table.length)];

e != null;

e = e.next) {

Object k;

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

}

return null;

}

意思是如果size==0(没有元素)，直接返回null；否则先通过hash方法算出key的hash值(hash方法其实是对key的hashcode二次hash计算，得出比较分散的hash值，减少碰撞)，对hash方法本篇暂不做过多分析，然后for循环头中调用了indexFor方法，返回的是key在Entry<K,V>数组中的位置索引，然后for循环做的事情就是遍历该位置的链表，如果有和key相等的节点，直接返回节点(由调用方返回节点中的value)。那么我们关注的是indexFor方法中如何找到key在数组中的位置呢？看一下indexFor的代码:

/**

* Returns index for hash code h.

*/

static int indexFor(int h, int length) {

// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

return h & (length-1);

}

方法很简单，直接返回入参h和length-1的按位与结果，其实可以理解为key的hashcode与Entry<K,V>数组长度-1按位与结果。

分析之前先明确一个概念，java中的按位与到底是什么？其实就是两个数字的二进制数据对应的位对比，1&1=1，1&0=0，0&0=0，比如：

1011=11

1000=8

按位与之后

1000=8

回到我们的主题中，为什么初始容量（也就是Entry<K,V>数组的长度）建议为2的n次幂呢？

我们举几个例子，length1=3(奇数)，length2 = 6(偶数)，length3 = 16(2的n次幂)，那么对应的length-1二进制数组如下：

我们对三种情况做一下分析，对于第一个数字length1=3，任何数和length1-1按位与操作，第一、二和四位置上永远不可能为1；第二个数字length2=6虽然是偶数，看起来会好一点，但是任何数和length2-1按位与操作，第一、三位置上永远不可能为1；而第三个数字length3=16，length3-1自身满足任何一个位置上都是1，也就是说只要入参key的hashcode足够分散，和length3-1按位与操作能够满足使任何一个位置上都是1，也就是说hashcode&lenght-1能够返回Entry<K,V>数组任何一个下标位置。

从以上例子中可知，奇数和偶数(非2的n次幂)，和任何key的hashcode按位与操作，总会有一些位置覆盖不到。回到上述的indexFor方法中，也就是说对于数组长度非2的n次幂的情况，永远会有一些数组位置辐射不到，再换一个角度来说，这些场景中，我们永远无法将Entry<K,V>数组利用率提高到100%。

在一些极端的情况下，我们的HashMap可能会出现纯链表结构：

这样的话链表变得很大，这样会产生很多问题：

1. 数组中有大量空位置，浪费空间，数组利用率很低
2. get和put性能都很差
3. 由于HashMap非线程安全，有链表的put操作触发resize导致死链的概率变大

最后我们可以得出结论，使用HashMap的时候建议指定的容量是2的n次幂(很多人习惯使用空构造器，默认容量16已经满足需求)，具体还需要考虑业务场景而定。

感谢各位的支持，如有疑问可以留言或私聊我，希望大家多多交流，一起进步。最后附上公众号