1.首先我们来看一下HashMap的结构，HashMap的底层是基于数组＋链表+红黑树的原理。 2.数组特点：查询快，增删慢。 链表特点：查询慢，增删快。 红黑树特点：查询快，增删快，是一棵二叉排序树，有自平衡的特点，时间复杂度能控制到O(log(n))。

HashMap的默认容量为16，默认的负载因子为0.75，当HashMap中元素个数超过容量乘以负载因子的个数时，就创建一个大小为前一次两倍的新数组，再将原来数组中的数据复制到新数组中。当数组长度到达64且链表长度大于8时，链表转为红黑树。 底层源码：

每次遍历一个链表，平均查找的时间复杂度是 O(n)，n 是链表的长度。红黑树有和链表不一样的查找性能，由于红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在 O(log(n))。 最初链表还不是很长，所以可能 O(n) 和 O(log(n)）的区别不大，但是如果链表越来越长，那么这种区别便会有所体现。所以为了提升查找性能，需要把链表转化为红黑树的形式。 那么问题来了，既然红黑树这么好用，为什么不直接使用红黑树呢？

这个问题其实在源码中已经给出了答案

通过源码我们可以发现，系统默认的是链表长度达到8就转成红黑树，而当链表长度降到6就转换回链表，这体现了时间和空间平衡的思想。 我们也可以理解成最开始使用链表的时候，空间占用是比较少的，而且由于链表短，所以查询时间也没有太大的问题。可是当链表越来越长，需要用红黑树的形式来保证查询的效率。此时对于何时应该从链表转化为红黑树，就应该需要确定一个阈值，于是系统把这个阈值默认设置为8。 那么问题又来了，为什么这个阈值刚好是8呢？

这个问题在源码中也有解释

上述代码的意思是如果 hashCode 分布的比较良好，也就是 hash 冲突比较少，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为8的时候，概率仅为0.00000006。这是一个小于千万分之一的概率，在实际情况中我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。 那么问题又来了，当数组长度小于64，但链表长度大于8时，链表还会转成红黑树吗？

如果链表长度大于8，但是数组长度小于64时，还是会进行扩容操作，不会转换为红黑树。因为数组的长度较小，应该尽量避开红黑树。因为红黑树需要进行左旋，右旋，变色操作来保持平衡。 所以当数组长度小于64，使用数组加链表比使用红黑树查询速度要更快、效率要更高。

一般情况下，HashMap底层使用数组+链表，当数据量非常大时，长度大的链表（大于8）自动转成红黑树，此时，HashMap底层使用数组+链表+红黑树。至于这个阈值是系统设置的。当链表长度降到6时就自动转换回链表。 通常情况下不会使用红黑树，当数据量较小时，如何强制使用红黑树，不但不能提高效率，反而耗费内存空间。只有当数据量非常大时，使用红黑树才能更好地提高效率。