ConcurrentHashMap的底层数据为数组加链表,哈希冲突的值会放在链表中,如果哈希冲突严重,对ConcurrentHashMap的操作会变为对长链表的操作,为了解决效率问题,1.8会进行红黑树的转换
红黑树
什么是红黑树
红黑树是一种特殊的平衡二叉树,存放有序的数据,检索的时间复杂度为O(lgn)
红黑树的特性
- 红黑树的节点非红即黑
- 根节点为黑色
- 叶子节点为黑色叶子节点为NIL节点即空节点
- 如果一个节点为红色,那么他的子节点一定是黑色
- 从一个节点到该节点的子孙节点的所有路径包含相同个数个黑色节点
红黑树的结构修改
- 左旋
- 将节点A的子右节点调整为自己的父节点,将该子右节点下的子左节点调整为自己的子右节点
- 右旋
- 将节点A的子左节点调整为自己的父节点,将该子左节点下的子右节点调整为自己的子左节点
- 着色
在什么情况下进行转换
java针对链表进行监控,给链表的最大长度设定默认阈值为8,超过阈值就会进行结构改变
1 | /** |
具体时间是在put方法调用的真实方法putVal中,处理完数据的放置后进行检查1
2
3
4
5
6
7if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
首先对节点进行处理,先判断是否需要进行链表的扩容,以64长度为界限,64以下扩容2倍,64以上将Node转换为TreeNode
1 | /** |