本文基于JDK-8u261源码分析
1 简介
HashMap是一个使用非常频繁的键值对形式的工具类，其使用起来十分方便。但是需要注意的是，HashMap不是线程安全的，线程安全的是ConcurrentHashMap（Hashtable这种过时的工具类就不要再提了），在Spring框架中也会用到HashMap和ConcurrentHashMap来做各种缓存。从Java 8开始，HashMap的源码做了一定的修改，以此来提升其性能。首先来看一下HashMap的数据结构：
整体上可以看作是数组+链表的形式。数组是为了进行快速检索，而如果hash函数冲突了的话，就会在同一个位置处后面进行挂链表的操作。也就是说，同一个链表上的节点，它们的hash值计算出来都是一样的。但是如果hash冲突比较多的时候，生成的链表也会拉得比较长，这个时候检索起来就会退化成遍历操作，性能就比较低了。在Java 8中为了改善这种情况，引入了红黑树。
红黑树是一种高级的平衡二叉树结构，其能保证查找、插入、删除的时间复杂度最坏为O(logn)。在大数据量的场景下，相比于AVL树，红黑树的插入删除性能要更高。当链表中的节点数量大于等于8的时候，同时当前数组中的长度大于等于MIN_TREEIFY_CAPACITY时（注意这里是考点！所以以后不要再说什么当链表长度大于8的时候就会转成红黑树，这么说只会让别人觉得你没有认真看源码），链表中的所有节点会被转化成红黑树，而如果当前链表节点的数量小于等于6的时候，红黑树又会被退化成链表。
其中MIN_TREEIFY_CAPACITY的值为64，也就是说当前数组中的长度（也就是桶bin的个数）必须大于等于64的时候，同时当前这个链表的长度大于等于8的时候，才能转化。如果当前数组中的长度小于64，即使当前链表的长度已经大于8了，也不会转化。这点需要特别注意。以下的treeifyBin方法是用来将链表转化成红黑树操作的：
从上面的第7行和第8行代码处可以看出，如果当前数组的长度也就是桶的数量小于MIN_TREEIFY_CAPACITY的时候，会选择resize扩容操作，此时就不会走转成红黑树的逻辑了。这里的意思就是说如果当前的hash冲突达到8的时候，根本的原因就是因为桶分配的太少才产生那么多冲突的。那么此时我选择扩容操作，以此来降低hash冲突的产生。等到数组的长度大于等于MIN_TREEIFY_CAPACITY的时候，如果当前链表的长度还是8的话，才会去转化成红黑树。
由此可以看出加入MIN_TREEIFY_CAPACITY这个参数的意义就是在于要保证hash冲突多的原因不是因为数组容量少才导致的；还有一个意义在于，假如说当前数组的所有数据都放在了一个桶里面（或者类似于这种情况，绝大部分的节点都挂在了一个桶里（hash函数散列效果不好，一般不太可能出现）），此时如果没有MIN_TREEIFY_CAPACITY这个参数进行限制的话，那我就会去开开心心去生成红黑树去了（红黑树的生成过程以及后续的维护还是比较复杂的，所以原则上是能不生成就不生成，后面会有说明）。
而有了MIN_TREEIFY_CAPACITY这个参数进行限制的话，在上面的第8行代码处就会触发扩容操作。这里的扩容更多的意义在于把这个hash冲突尽量削减。比如把链表长度为8的八个节点再平分到扩容后新的两倍数组的两处新的桶里面，每个桶由原来的八个节点到现在的四个节点（也可能是一个桶5个另一个桶3个，极端情况下也可能一个桶8个另一个桶0个。但不管怎样，从统计学上考量的话，原来桶中的节点数大概率会被削减），这样就相当于减少了链表的个数，也就是说减少了在同一个位置上的hash冲突的发生。还有一点需要提一下，源码注释中说明MIN_TREEIFY_CAPACITY的大小要至少为4倍的转成红黑树阈值的数量，这么做的原因也是更多的希望能减少hash冲突的发生。
**那么为什么不直接用红黑树来代替链表，而是采用链表和红黑树来搭配在一起使用呢？**原因就在于红黑树虽然性能更好，但是这也仅是在大数据量下才能看到差异。如果当前数据量很小，就几个节点的话，那么此时显然用链表的方式会更划算。因为要知道红黑树的插入和删除操作会涉及到大量的自旋，以此来保证树结构的平衡。如果数据量小的话，插入删除的性能高效根本抵消不了自旋操作所带来的成本。
**还有一点需要留意的是链表转为红黑树的阈值是8，而红黑树退化成链表的阈值是6。**为什么这两个值会不一样呢？可以试想一下，如果这两个值都为8的话，而当前链表的节点数量为7，此时一个新的节点进来了，计算出hash值和这七个节点的hash值相同，即发生了hash冲突。于是就会把这个节点挂在第七个节点的后面，但是此时已经达到了变成红黑树的阈值了（MIN_TREEIFY_CAPACITY条件假定也满足），于是就转成红黑树。
但是此时调用了一次remove操作需要删掉这个新加的节点，删掉之后当前红黑树的节点数量就又变成了7，于是就退化成了链表。然后此时又新加了一个节点，正好又要挂在第七个节点的后面，于是就又变成红黑树，然后又要remove，又退化成链表…可以看到在这种场景下，会不断地出现链表和红黑树之间的相互转换，这个性能是很低的，因为大部分的执行时间都花费在了转换数据结构上面，而我仅仅是做了几次连续的增删操作而已。所以为了避免这种情况的发生，将两个阈值错开一些，以此来尽量避免在阈值点附近可能存在的、频繁地做转换数据结构操作而导致性能变低的情况出现。
这里之所以阈值会选择为8是通过数学统计上的结论得出的，在源码中也有相关注释：
其中中间的数字表示当前这个位置预计发生指定次数哈希冲突的概率是多少。可以看到当冲突概率为8的时候，概率已经降低到了0.000006%，几乎是不可能发生的概率。从这里也可以看出，HashMap作者选择这个数作为阈值是不希望生成红黑树的（红黑树的维护成本高昂）。而同样负载因子默认选择为0.75也是基于统计分析出来的，以下是源码中对负载因子的解释：
负载因子衡量的是数组在扩容前的填充程度，也就是说一个数组真正能存进去的实际容量 = 数组的长度 * 负载因子（比如当前数组的长度为16（桶的个数），负载因子为0.75，那么当数组存进了16 * 0.75 = 12个桶的时候，就会进行扩容操作，而不是等到数组空间满了的时候）。如果为0.5表示的就是数组填充一半后就进行扩容；为1就表示的是数组全部填满后再进行扩容。之所以默认值选择为0.75是在时间和空间成本上做的一个折中方案，一般不建议自己更改。这个值越高，就意味着数组中能存更多的值，减少空间开销，但是会增加hash冲突的概率，增加查找的成本；这个值越低，就会减少hash冲突的概率，但是会比较费空间。
而数组的默认容量为16也是统计上的结果。值得一说的是，如果事先知道了HashMap所要存储的数量的时候，就可以将数组容量传进构造器中，以此来避免频繁地扩容操作。比如我现在要往HashMap中大约放进200个数据，如果不设置初始值的话，默认容量就是16，当存进16 * 0.75 = 12个数据的时候就会扩容一次，扩容到两倍容量32，然后等再存进32 * 0.75 = 24个数据的时候再继续扩容…直到扩容到能存进200个数据为止。所以说，如果能提前先设置好初始容量的话，就不需要再扩容这么多次了。
2 构造器
3 put方法
4 resize方法
在上面putVal方法中的第39行和118行代码处，都是调用了resize方法来进行初始化或扩容的。而resize方法也是HashMap源码中比较精髓、比较有亮点的一个方法。其具体实现大致可以分为两部分：设置扩容标志位和具体的数据迁移过程。下面就首先来看一下resize方法的前半部分源码：
上面在把newCap、newThr和threshold标记位都设置好了后，下面就是具体的数据迁移的过程，也就是resize方法后半部分的实现：
在Java 7的HashMap源码中，transfer方法是用来做扩容时的迁移数据操作的。其实现就是通过遍历链表中的每一个节点，重新rehash实现的。在这其中会涉及到指针的修改，在高并发的场景下，可能会使链表上的一个节点的下一个指针指向了其前一个节点，也就是形成了死循环，死链（具体形成过程不再展开）：
这样再去遍历链表的时候就永远不会停下来，出现了bug。而Java8中通过形成两个链表，节点hash值在数组容量二进制数为1的那个位置处去按位与判断是0还是1，以此来选择插入的方式很好地解决了这个问题，而且不用每一个节点rehash，提高了执行速度。
既然说到了不用rehash，那么这里想要探究一下在数组扩容时，选择新插入数组的位置是原位置和原位置+旧数组容量，为什么这里加上的是旧数组容量呢？加别的值不可以吗？其实这里加旧数组容量是有原因的。我们都知道，数组容量必须是2的幂，即100…000，而新数组的容量是原数组的2倍，也就是把原来值中的“1”往左移了一位，而我们在判断插入桶位置时用的方式是（数组容量 - 1）& hash值。把这些信息都整合一下，我们就知道在新数组中计算桶位置和在旧数组中计算桶位置的差异，其实就在于旧数组二进制为1上的这位上。如果该位是0，那就是和原来旧数组是同一个位置，如果是1，就是旧数组位置处+旧数组的容量。下面举个例子：
两个节点此时计算出来桶的位置都是1010，即第10个桶。它们都会被放在第10个桶中的链表中。
而现在数组扩容了，数组容量变为了32，我们再来看看结果会怎样：
这时候发现(n - 1) & hash的结果不一样了，节点1是01010，节点2是11010。也就是说，我们在get方法执行的时候（get方法也是通过(n - 1) & hash的方式来找到桶的位置），找到节点1是在第10个桶，节点2是在第26个桶，这两个节点之间相差16个桶，这不就是旧数组的容量吗？现在是不是恍然大悟了，我们当初在扩容时，将节点的hash值和旧数组容量进行按位与，其实也就是在找上图红框框中的那个位置。如果为0，就将节点1放在新数组中第10个桶中（1010），也就是原位置处；如果为1，就将节点2放在新数组中第26个桶中（1010+10000），也就是原位置+旧数组容量处。这样做的话，我在get方法执行的时候也能保证正确执行，能正确找到节点在新数组中桶的位置。同时也说明了，这个放入的策略是不能换的。也就是说，不能是如果为1的话最后就会插入到新数组的原位置，为0就插入到原位置+旧数组容量的位置。如果这么做的话，最后get方法在查找该节点的时候，就找不到了（而实际上还存在）。所以通过Java 8中的这种扩容方式，既能计算出正确的新桶位置，又能避免每一个节点的rehash，节省计算时间，实在是妙哉。
5 get方法
6 remove方法
7 clear方法
在这行干的越久真是越觉得：万丈高楼平地起，这绝B是句真理！在应用业务里待太久很多底层的东西往往容易忽略掉，今年的年初计划是把常用的JDK源码工具做一次总结，眼看年底将近，乘着最近有空，赶紧的给补上。
