概述
ConcurrentMap(并发映射)，在jdk1.5以后提供的保证并发性已经数据安全的映射。
ConcurrentHashMap–并发哈希映射
底层使用数组加链表的数据结构，默认容量为16，加载因子为0.75，当容量超过最大容量*加载因子后会进行扩容，每次扩容为原来的一倍。是异步线程安全的映射。
ConcurrentHashMap是怎么保证线程安全的？
- 在jdk1.7的时候ConcurrentHashMap使用了分段（桶）锁和读写锁，每个锁只锁一个桶，这样在并发环境下，如果访问的元素不属于一个桶，就不会产生锁的竞争，提高了效率，读写锁保证了只要不出现写操作，大量的读操作可以同时进行，大大的提高了ConcurrentHashMap在并发环境下的效率。
- 在JDK1.8之后，ConcurrentHashMap使用了数组加链表/红黑二叉树的数据结构，线程安全问题也摒弃了分段锁的概念，而直接使用无锁算法CAS(Compare And Swap),什么是CAS算法，CAS的语义是“我认为V的值应该为A，如果是，那么将V的值更新为B，否则不修改并告诉V的值实际为多少”，举个例子，变量a的值为1，现在有X和Y两个线程要对a进行a的操作(线程X和Y都都记录这变量a的内存地址)假设X线程拿到了cpu的执行权X线程保存A的预期值为1与变量a的值相等，执行a,变量a的值变为2，B线程被cpu调度之后，发现a的值发生了改变与预期内存值不相等，获取a的真实值2，执行a 操作，a的值变为3。
- 在JDK1.8之后，桶的数量超过64以后，链表的数量超过阈值8会自动转化为红黑二叉树的结构，大大提高了查找的效率，红黑二叉树的时间复杂度为O(logn),
红黑树
代码语言：javascript复制 /**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
* conflicts between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = ;
当桶的容量大于是，链表的长度超过阈值将会自动转化为红黑树
红黑二叉树
红黑二叉树本质上是一个自平衡二叉查找树
二叉查找树特点：左小于根，右大于根
红黑树的特点:父子节点都为红
i.所有的节点非红即黑
ii.根节点必须为黑节点
iii.红节点的子节点必须为黑节点，反之不成立
iv.从根节点出发相同高度的黑节点总是一致
v.所有的根节点都为黑色的空节点
vi.新添加的节点必须为红色
红黑树修正方案：
i.叔父节点为红，将父节点以及叔父节点涂黑，祖父节点涂红.
ii.叔父节点为黑，当前节点为父节点的右子叶，以当前节点为轴进行左旋（与当前节点有关的节点以当前节点为轴逆时针旋转°，并保持左右子树不变）
iii.叔父节点为黑，当前节点为父节点的左子叶，以当前节点为轴进行右旋旋（与当前节点有关的节点以当前节点为轴顺时针旋转°，并保持左右子树不变）
iv。红黑树修正过程是链式反应过程
红黑树的时间复杂度:O(logn)
ConcurrentSkipListMap的相关api
代码语言：javascript复制package com.jmy.ConcurrentMap;
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashMapDemo {
public static void main(String[] args) {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap();
// 添加元素
map.put("a",);
map.put("b",);
map.put("c",);
// 获取所有的key
System.out.println(map.keySet());
// 使用key查找value
System.out.println(map.get("a"));
// 转化为键值对的集合
System.out.println(map.entrySet());
}
}
ConcurrentSkipListMap(并发跳跃表映射)
当查找元素18时不在需要使用原始链表从头结点遍历，而是先查找最上层的索引的依次向下寻找，大大提高的查找的效率。
代码语言：javascript复制 */
public ConcurrentSkipListMap() {
this.comparator = null;
initialize();
}
/**
* Initializes or resets state. Needed by constructors, clone,
* clear, readObject. and ConcurrentSkipListSet.clone.
* (Note that comparator must be separately initialized.)
*/
private void initialize() {
keySet = null;
entrySet = null;
values = null;
descendingMap = null;
head = new HeadIndex<K,V>(new Node<K,V>(key:null, BASE_HEADER,next:null),
down:null, right:null, level:);
}
/** Lazily initialized key set */
private transient KeySet<K> keySet;
/** Lazily initialized entry set */
private transient EntrySet<K,V> entrySet;
/** Lazily initialized values collection */
private transient Values<V> values;
/** Lazily initialized descending key set */
private transient ConcurrentNavigableMap<K,V> descendingMap;
图中的索引即为level
代码语言：javascript复制a.底层是基于跳跃表实现的
b.跳跃表:
i.元素是有序的
ii.实际过程中，跳跃表是多层的，最上层的元素至少是两个
iii.跳跃表是典型的以空间换取时间的产物
iv.查询的时间复杂度为O(logn)
v.适用于查询多，而增删少的场景
vi.在跳跃表中添加元素，新添的元素是否提取到上层的跳跃表中遵循"抛硬币"的原则(自定义算法)
ConcurrentSkipListMap的相关方法
代码语言：javascript复制package com.jmy.ConcurrentMap;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;
public class ConcurrentSkipListMapDemo {
public static void main(String[] args) {
// ConcurrentNavigableMap是一个接口，所以使用的更多的是它的实现类
ConcurrentNavigableMap<String, Integer> map = new ConcurrentSkipListMap<>();
// 添加元素
map.put("d", );
map.put("e", );
map.put("w", );
map.put("a", );
map.put("h", );
map.put("y", );
map.put("u", );
// 提供了用于截取子映射的方法
// 从头开始截取到指定元素
System.out.println(map.headMap("h"));
// 从指定元素开始截取到尾
System.out.println(map.tailMap("h"));
// 从指定元素截取到指定元素
System.out.println(map.subMap("a", "h"));
}
}
