一、概述
1.是JDK1.5提供的用于应对高并发以及保证安全性的一类映射
二、ConcurrentHashMap - 并发哈希映射
1.底层结构依然是依靠数组+链表
2.默认初始容量是16，默认加载因子是0.75，默认扩容是增加1倍
3. 底层采用了分桶锁(分段锁)机制保证并发性，在后续的版本中，在分段锁的基础上引入了读写锁的机制：
a.读锁：允许多个线程同时读，不允许线程写
b.写锁：允许一个线程写，不允许线程读
4.在JDK1.8中，采用了无锁算法CAS(Compare and Swap - 比较和交换)
CAS的语义：我认为V的值是A，如果是，那么将V的值更新为B，否则修改并告诉V的值实际为多少
V 内存值
A 旧的预期值
B 新的预期值
5.在JDK1.8中，引入红黑树机制。当桶中的元素个数超过8个的时候，会扭转成一棵树；
如果节点数不足7个，则会扭转回链表
解决问题：桶数越多，扩容的几率就越低，桶数越多，每一个桶中的元素个数越多，使用红黑树
6.红黑树：解决瘸腿二叉树的问题
a.本质上是一颗自平衡二叉查找树 - Binary Search Tree - BST
二叉树 - Binary Tree - B-树
b.二叉查找树：i.基于二叉树，ii.左子树小于根，右子树都大于根
c.特点：
i.所有的节点颜色非红即黑(比如：true为黑色，false和红色)
ii.根节点一定是黑的
iii.红节点的子节点一定是黑节点，黑节点的子节点可以是红节点也可以是黑节点
iv.最底层的叶子节点一定是黑色的空节点(在红黑树中空节点使用 NIL 表示)
v.从根节点到任意一个叶子节点经过的黑色节点的个数一定相同，即黑色节点高度一致
vi.新添加的节点的颜色一定是红节点
红黑树图例：
示例：现有一串数字；11，2，14，1，7，13，5，8，需要构建一颗红黑树，如果构建如下第一个图，存在什么问题？
问题如下:左边的高度为3，右边的高度为2
针对上述问题进行调整，最终如下：将右边黑色14变为红色14，黑色13变为红色13
如果这时需要添加 4 这个元素，按照正常的规则，放在红5下，
并且按照规则，新增为红，但是红色节点下又必须为黑色的那么需要进行红色树的修正
三、ConcurrentNavigableMap
原文：https://www.cnblogs.com/alen-apple/p/13054442.html