java面试必问——hashMap 深入分析put方法
2020-04-21 18:44:48   来源：东方头条   

1：hashMap底层结构

数组+链表+红黑树

2：简要看下put方法的执行步骤

1：如果hashMap为初始话，则初始化map,初始容量为16

2：对key求hash值，然后计算下标（数组位置，或者说是桶的位置，或者是bin）

3:如果出现了碰撞（在数组的相同下标），以链表的方式连接到后面

4：如果没有出现碰撞就直接放入桶中

5：如果链表中的节点数大于阈值8个时，就直接转换为红黑树

6：如果树中节点个数小于6个时，那么就会从红黑树转换为链表

7：如果节点已经存在，就直接覆盖

8：如果桶容量达到16*0.75=12这个阈值的时候，数组需要扩容

上边是put方法执行的大概流程，那么下面我们来具体分析

1：为什么需要从链表转换为红黑树？

因为map中的桶的元素初始化是链表保存的，其查找性能是o(n),而树结构能将查找性能提升到o(log(n)),当链表长度很小的时候，及时遍历，速度也非常快，但是当链表长度不断变成时，肯定会对查询性能有一定的影响，所以才需要转换成树，源码如下图

上边的截图的大概意思是：当bin长度大于8的时候转换成树的结构

上边这个截图的意思是：Tree结构的总量必须大于8,当少于6的时候就开始转换为链表

下面继续看这样一段源码

上图的大概含义是：当hashcode离散性很好的时候，树型bin用到的概率很小因为数据均匀分布在每一个bin上，几乎不会有bin中链表长度会达到阈值，但是随机hashcode小，离散性可能会变差，然而jdk又不能阻止用户实现这种，不好的算法，因此就可能导致不均匀的数据分布，不过理想情况下随机hashcode算法下所有bin中节点分布频率会遵循泊松公式，从泊松公式我们可以看到一个bin中链表长度达到8个元素的概率几乎为0,0.00000006这就是为什么要选择8当转换的阈值

以上总结：

1：链表的复杂度是o(n) .树的复杂度是o(log(n)) ,当链表过长计算效率低，需要转换成红黑树

2：链表大于8时开始转换为红黑树，小于6时由红黑树转换为链表

3：选择8个转换阈值，是因为通过泊松公式，在同一个bin上节点等于8的概率几乎等于0

-----------------------------------------

以上内容，纯属个人观点，有不同的看法，欢迎留言交流，喜欢的朋友们希望给个支持的赞！

谢谢大家！