HashMap 源码分析（二）

一、概述

在上一篇文章中，我们分析了HashMap中增删改查的流程，但这是远远不够的，所以在本文中，我们将根据一些常见问题并结合源码来进行更具体的分析。

二、常见问题

1. HashMap的数组长度为什么必须是2的幂？
2. HashMap的默认负载因子是多少，作用是什么？
3. HashMap的默认负载因子为什么是0.75？
4. HashMax数组最大长度是多少？
5. 什么叫做Hash碰撞？
6. HashMap何时扩容？
7. Jdk 1.8为什么加入了红黑树？
8. 什么时候由链表转为红黑树？

三、问题解析

1. HashMap的数组长度为什么必须是2的幂？

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

通过上面的源码注释中，就已经写明了：必须是 2 的幂，这是为什么？源码也不是我们写的，我们也不知道，不过我们根据数组的长度的使用来进行分析，在HashMap的putVal方法中，有这样一段代码：

n = (tab = resize()).length;
p = tab[i = (n - 1) & hash]

这里的n为数组的长度，p为计算出来的下标，下标通过(16-1) & hash 进行计算的。就是15&hash，我们反向来思考问题，如果数组长度为15呢？我们来看下图：

01.png

可以看到，当数组长度为15时，通过&运算，最终计算出来的下标为：0，2，4，6，8，10，12，14，且均发生了哈希碰撞。那这时候数组的1 3 5 7 9 11 位置上不就存不上数据了嘛。

接下来我们再看当数组长度为2的幂次方时的结果：我们用2的3次方，长度为8举例

02.png

可以看到，当长度为2的幂时，最终算出的下标是均匀分布的，并没有发生哈希碰撞。
细心的人可以发现，当数组长度不为2的幂时，二进制的最后一位总是为0，这就导致不管hash为多少，最终算出来总是双数，进而导致了数组分布不均，有些位置永远用不到。

所以：数组长度为2的幂，是为了减少哈希碰撞，是数组分布更均匀。

---

---

2. HashMap的默认负载因子是多少，作用是什么？

static final float DEFAULT_LOAD_FACTOR = 0.75f;

newCap = DEFAULT_INITIAL_CAPACITY;
float ft = (float)newCap * loadFactor;

默认的加载因子为0.75，它与HashMap的扩容机制相关，当数组长度大于16*0.75=12时，数组就会扩容，并不是到达16时才会扩容。它决定了HashMap扩容的时机。

3. HashMap的默认负载因子为什么是0.75？

上面提到了数组扩容是由 长度加载因子，得到一个阈值，当长度达到这个阈值时就会扩容，如果加载因子为1，那就是161,即数组长度达到16时才会扩容，但是这样会牺牲时间效率，如果加载因子0.5时，那么长度为8时就扩容了，此时就会导致数组中空间利用率降低，所以0.75是一个比较合适的值。

4. HashMax数组最大长度是多少？

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap数组最大长度为：2的30次幂，1073741824

5. 什么叫做Hash碰撞？

在HashMap中，Hash碰撞就是指计算出的hash值相同。

6. HashMap何时扩容？

n = (tab = resize()).length; //629行

if (++size > threshold)
            resize();  //663行

在HashMap中，扩容由resize()方法完成，
在首次调用put时，会执行resize()方法初始化，put之后判断数量是否大于阈值，如果大于阈值则扩容，
后续调用会直接存入数据，然后再判断数量是否大于阈值，如果大于阈值则扩容，
当数组长度大于加载因子*数组长度时，则会扩容。

7. Jdk 1.8为什么加入了红黑树？

再Jdk1.7中，HashMap是通过数组+链表实现的，Jdk1.8中加入了红黑树，只有当数组中链表的长度大于8时，才会转为红黑树，红黑树相比于链表在插入和删除的操作上，要比链表更快，如果说链表长度为100时，那么HashMap要循环99次才能找到最后一个节点，再执行插入操作，删除同理。

8. 什么时候由链表转为红黑树？

 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);


if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  64
            resize();

当链表的长度大于8时执行树化的方法，随后如果数组长度小于64时，则会扩容，反之转换为红黑树。
所以 当链表长度大于8时 且 数组长度小于64时才会将链表转为红黑树。