Java7版本的ConcurrentHashMap
Java8版本的ConcurrentHashMap
红黑树的特点是，每个节点都是带有颜色属性的二叉查找树，红黑树的本质是对二叉查找树BST的一种平和策略。
红黑树的一些其他特点:
每个节点要么是红色的，要么是黑色的，但根节点永远是黑色的
红色节点不能连续，也就是说，红色节点的子和父都不能是红色的
从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点。
红黑树有自平衡的特点，即便是在极端的情况下，查询也比较快。
分析Java8版本的ConcurrentHashMap的重要源码
Node 节点
我们先来看看最基础的内部存储结构 Node，这就是一个一个的节点，如这段代码所示：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
// ...
}可以看出，每个 Node 里面是 key-value 的形式，并且把 value 用 volatile 修饰，以便保证可见性，同时内部还有一个指向下一个节点的 next 指针，方便产生链表结构。
下面我们看两个最重要、最核心的方法。
put 方法源码分析
put 方法的核心是 putVal 方法，为了方便阅读，我把重要步骤的解读用注释的形式补充在下面的源码中。我们逐步分析这个最重要的方法，这个方法相对有些长，我们一步一步把它看清楚。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) {
throw new NullPointerException();
}
//计算 hash 值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
//如果数组是空的，就进行初始化
if (tab == null || (n = tab.length) == 0) {
tab = initTable();
}
// 找该 hash 值对应的数组下标
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果该位置是空的，就用 CAS 的方式放入新值
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null))) {
break;
}
}
//hash值等于 MOVED 代表在扩容
else if ((fh = f.hash) == MOVED) {
tab = helpTransfer(tab, f);
}
//槽点上是有值的情况
else {
V oldVal = null;
//用 synchronized 锁住当前槽点，保证并发安全
synchronized (f) {
if (tabAt(tab, i) == f) {
//如果是链表的形式
if (fh >= 0) {
binCount = 1;
//遍历链表
for (Node<K, V> e = f; ; ++binCount) {
K ek;
//如果发现该 key 已存在，就判断是否需要进行覆盖，然后返回
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent) {
e.val = value;
}
break;
}
Node<K, V> pred = e;
//到了链表的尾部也没有发现该 key，说明之前不存在，就把新值添加到链表的最后
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
break;
}
}
}
//如果是红黑树的形式
else if (f instanceof TreeBin) {
Node<K, V> p;
binCount = 2;
//调用 putTreeVal 方法往红黑树里增加数据
if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent) {
p.val = value;
}
}
}
}
}
if (binCount != 0) {
//检查是否满足条件并把链表转换为红黑树的形式，默认的 TREEIFY_THRESHOLD 阈值是 8
if (binCount >= TREEIFY_THRESHOLD) {
treeifyBin(tab, i);
}
//putVal 的返回是添加前的旧值，所以返回 oldVal
if (oldVal != null) {
return oldVal;
}
break;
}
}
}
addCount(1L, binCount);
return null;
}通过以上的源码分析，我们对于 putVal 方法有了详细的认识，可以看出，方法中会逐步根据当前槽点是未初始化、空、扩容、链表、红黑树等不同情况做出不同的处理。
get 方法源码分析
get 方法比较简单，我们同样用源码注释的方式来分析一下：
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//计算 hash 值
int h = spread(key.hashCode());
//如果整个数组是空的，或者当前槽点的数据是空的，说明 key 对应的 value 不存在，直接返回 null
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//判断头结点是否就是我们需要的节点，如果是则直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//如果头结点 hash 值小于 0，说明是红黑树或者正在扩容，就用对应的 find 方法来查找
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//遍历链表来查找
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}总结一下 get 的过程：
计算 Hash 值，并由此值找到对应的槽点；
如果数组是空的或者该位置为 null，那么直接返回 null 就可以了；
如果该位置处的节点刚好就是我们需要的，直接返回该节点的值；
如果该位置节点是红黑树或者正在扩容，就用 find 方法继续查找；
否则那就是链表，就进行遍历链表查找。
对比JDK1.7和1.8的异同点和优缺点
数据结构jdk1.7采用的是Segment分段锁来实现
jdk1.8中的ConcurrentHashMap使用数组+链表+红黑树。
并发度：
Java7：每个Segment独立加锁，最大并发个数就是Segment的个数（默认是16）
Java8：每个node是独立的，锁力度更细，数组的长度就是最大并发数，并发度比之前有提高。
保证并发安全的原理
Java7，采用Segment分段锁来保证安全，Segment是继承了ReenLock
Java8，采用Node+CAS+synchronized保证安全
遇到Hash碰撞
Java7：使用拉链法
Java8：先使用拉链法，在链表长度超过一定阀值时，将链表转换为红黑树
查询时间复杂度
Java7：遍历链表的时间复杂度为O（n），n为链表长度
Java8：如果变成遍历红黑树，时间复杂度降低为O（log（n）），n为树的节点个数。
二、为什么 Map 桶中超过 8 个才转为红黑树？
拉链法，当链表长度大于或等于阀值（默认8）的时候，如果同时还满足容量大于等于MIN_TREEIFY_CAPACITY（默认为64）的要求就会把链表转换为红黑树
当红黑树的节点小于或等于6个以后又会恢复为链表形态。
为什么需要转换：
每次遍历一个链表，平均查找的时间复杂度是O(n)，n是链表的长度
链表还不是很长，O（n）和O（log（n））的区别不大
如果链表越来越长，那么这种区别便会有所体现
为了提升查找性能，需要把链表转化为红黑树的形式。
默认链表长度达到8就转化为红黑树，而当长度降到6就转换回去
体现了时间和空间平衡个思想
当链表长度越来越长，需要红黑树的形式就可以保证查询的效率
对于为什么是8，是时间和空间的一种平衡，通常情况下没必要转化为红黑树，所以就选择了概率非常小，也就是长度为8的概率，如果平时开发中发现HashMap或是ConcurrentHashMap内部出现了红黑树的结构，往往就说明我们的哈希算法出现了问题，是不是HashCode分布不均匀。
三、ConcurrentHashMap和 Hashtable的区别
它们都是线程安全的，但是他们的区别是
1、出现的版本不同
Hashtable：JDK1.0中出现，JDK1.2版本中实现了Map接口
ConcurrentHashMap：
JDK1.5中出现的，后出现的在性能上存在较大的不同
2、实现线程安全方式的不同
Hashtable实现并发安全是通过synchronized关键字
而ConcurrentHashMap实现的原理，却有大大的不同，实现原理是CAS+synchronized+Node节点的方式。
3、性能不同
Hashtable，线程数量增加的时候性能会极具下降
每一次修改都会需要锁住整个对象，其他线程在此期间不能操作
会有额外的上下文切换等开销。多线程情况下，效率不一定高于单线程
ConcurrentHashMap，
仅会对一部分上锁而不是全部上锁
并发效率上，ConcurrentHashMap比Hashtable提高了很多。
4、迭代时修改的不同
Hashtable（包括HashMap），不允许在迭代期间修改内容，否则会抛出ConcurrentModificationException 异常，其原理是检测 modCount 变量，迭代器的 next() 方法的代码如下：
ConcurrentHashMap 即便在迭代期间修改内容，也不会抛出ConcurrentModificationException。
