??HashMap是一个使用非常频繁的键值对形式的工具类，其使用起来十分方便。但是需要注意的是，HashMap不是线程安全的，线程安全的是ConcurrentHashMap（Hashtable这种过时的工具类就不要再提了），在Spring框架中也会用到HashMap和ConcurrentHashMap来做各种缓存。从Java8开始，HashMap的源码做了一定的修改，以此来提升其性能。首先来看一下HashMap的数据结构：
??整体上可以看作是数组+链表的形式。数组是为了进行快速检索，而如果hash函数冲突了的话，就会在同一个位置处后面进行挂链表的操作。也就是说，同一个链表上的节点，它们的hash值计算出来都是一样的。但是如果hash冲突比较多的时候，生成的链表也会拉的比较长，这个时候检索起来就会退化成遍历操作，性能就比较低了。在Java8中为了改善这种情况，引入了红黑树。
??红黑树是一种高级的平衡二叉树结构，其能保证查找、插入、删除的时间复杂度最坏为O(logn)。在大数据量的场景下，相比于AVL树，红黑树的插入删除性能要更高。当链表中的节点数量大于等于8的时候，同时当前数组中的长度大于等于MIN_TREEIFY_CAPACITY时（注意这里是考点！所以以后不要再说什么当链表长度大于8的时候就会转成红黑树，这么说只会让别人觉得你没有认真看源码），链表中的所有节点会被转化成红黑树，而如果当前链表节点的数量小于等于6的时候，红黑树又会被退化成链表。其中MIN_TREEIFY_CAPACITY的值为64，也就是说当前数组中的长度（也就是桶bin的个数）必须大于等于64的时候，同时当前这个链表的长度大于等于8的时候，才能转化。如果当前数组中的长度小于64，即使当前链表的长度已经大于8了，也不会转化。这点需要特别注意。以下的treeifyBin方法是用来将链表转化成红黑树操作的：
1/**2*Replacesalllinkednodesinbinatindexforgivenhashunless3*tableistoosmall,inwhichcaseresizesinstead.4*/5finalvoidtreeifyBin(NodeK,V[]tab,inthash){6intn,index;NodeK,Ve;7if(tab==null
(n=tab.length)MIN_TREEIFY_CAPACITY)8resize();9elseif((e=tab[index=(n-1)hash])!=null){10TreeNodeK,Vhd=null,tl=null;11do{12TreeNodeK,Vp=replacementTreeNode(e,null);13if(tl==null)14hd=p;15else{16p.prev=tl;17tl.next=p;18}19tl=p;20}while((e=e.next)!=null);21if((tab[index]=hd)!=null)22hd.treeify(tab);23}24}
??从上面的第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是通过数学统计上的结论得出的，在源码中也有相