HashMap和ConcurrentHashMap的put方法详解

发表于 分类于

结构简述

HashMap和ConcurrentHashMap的结构都是一样的，jdk1.8之后都是 数组+链表+红黑树，链表长度超过8之后转红黑树。

计算

节点为6个的时候，链表的平均查询时间：(1+2+3+4+5+6)/ 6 = 3.5，红黑树的平均查询时间 (1+22+33)/6=2.3

节点为7个的时候，链表的平均查询时间：(1+2+3+4+5+6+7)/ 7 = 4，红黑树的平均查询时间 (1+22+34)/7=2.4

节点为8个的时候，链表的平均查询时间：(1+2+3+4+5+6+7+8)/ 8 = 4.5，红黑树的平均查询时间 (1+22+34+1*4)/8=2.6

链表的时间复杂度为O(n)，而树的时间复杂度为O(ln n)，上面计算有明显的效率变化，至于为啥选8这个阈值，应该是基于大量数据收集之后比较而定的。

结构图

HashMap

流程图

img

代码详解

ConcurrentHashMap

流程图

代码详解