ConcurrentHashMap的实现原理
ConcurrentHashMap的出现主要为了解决hashmap在并发环境下不安全，JDK1.8ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，CAS等乐观锁技术来减少锁竞争对于性能的影响，ConcurrentHashMap保证线程安全的方案是：
- JDK1.8：synchronized+CAS+HashEntry+红黑树
- JDK1.7：ReentrantLock+Segment+HashEntry
JDK7 ConcurrentHashMap
在JDK1.7中ConcurrentHashMap由Segment(分段锁)数组结构和HashEntry数组组成，且主要通过Segment(分段锁)段技术实现线程安全。
Segment是一种可重入锁，是一种数组和链表的结构，一个Segment中包含一个HashEntry数组，每个HashEntry又是一个链表结构，因此在ConcurrentHashMap查询一个元素的过程需要进行两次Hash操作，如下所示：
- 第一次Hash定位到Segment
- 第二次Hash定位到元素所在的链表的头部
正是通过Segment分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。
这样结构会使Hash的过程要比普通的HashMap要长，影响性能， 但写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，ConcurrentHashMap提升了并发能力。
JDK8 ConcurrentHashMap
在JDK8ConcurrentHashMap内部机构：数组+链表+红黑树，Java 8在链表长度超过一定阈值(8)时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(long(N)))，结构基本上与功能和JDK8的HashMap一样，只不过ConcurrentHashMap保证线程安全性。
但在JDK1.8中摒弃了Segment分段锁的数据结构，基于CAS操作保证数据的获取以及使用synchronized关键字对相应数据段加锁来实现线程安全，这进一步提高了并发性。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val; //使用了volatile属性
volatile Node<K,V> next; //使用了volatile属性
...
}
ConcurrentHashMap采用Node类作为基本的存储单元，每个键值对(key-value)都存储在一个Node中，使用了volatile关键字修饰value和next，保证并发的可见性。其中Node子类有：
- ForwardingNode：扩容节点，只是在扩容阶段使用的节点，主要作为一个标记，在处理并发时起着关键作用，有了ForwardingNodes，也是ConcurrentHashMap有了分段的特性，提高了并发效率
- TreeBin：TreeNode的代理节点，用于维护TreeNodes，ConcurrentHashMap的红黑树存放的是TreeBin
- TreeNode：用于树结构中，红黑树的节点（当链表长度大于8时转化为红黑树），此节点不能直接放入桶内，只能是作为红黑树的节点
- ReservationNode：保留结点
ConcurrentHashMap中替换元素和赋值元素在没有发生哈希冲突时都是基于sun.misc.Unsafe中原子操作实现多并发的无锁化操作。
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
}
ConcurrentHashmap 不支持 key 或者 value 为 null 的原因
ConcurrentHashmap和hashMap不同的是，concurrentHashMap的key和value都不允许为null，
因为concurrenthashmap它们是用于多线程的，并发的 ，如果map.get(key)得到了null，不能判断到底是映射的value是null，还是因为没有找到对应的key而为空，而用于单线程状态的hashmap却可以用containKey（key） 去判断到底是否包含了这个null。
put()方法如何实现线程安全呢
-
在第一次put数据时，调用
initTable()方法/** * Hash表的初始化和调整大小的控制标志。为负数，Hash表正在初始化或者扩容; * (-1表示正在初始化,-N表示有N-1个线程在进行扩容) * 否则，当表为null时，保存创建时使用的初始化大小或者默认0; * 初始化以后保存下一个调整大小的尺寸。 */ private transient volatile int sizeCtl; //第一次put，初始化数组 private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { //如果已经有别的线程在初始化了，这里等待一下 if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin //-1 表示正在初始化 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { ... } finally { sizeCtl = sc; } break; } } return tab; }使用
sizeCtl参数作为控制标志的作用，当在从插入元素时，才会初始化Hash表。在开始初始化的时候，- 首先判断
sizeCtl的值，如果sizeCtl < 0，说明有线程在初始化，当前线程便放弃初始化操作。否则，将**SIZECTL设置为-1**，Hash表进行初始化。 - 初始化成功以后，将
sizeCtl的值设置为当前的容量值
在不存在hash冲突的时
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //利用CAS操作将元素插入到Hash表中 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; // no lock when adding to empty bin(插入null的节点，无需加锁) }(f = tabAt(tab, i = (n - 1) & hash)) == null中使用tabAt原子操作获取数组，并利用casTabAt(tab, i, null, new Node<K,V>(hash, key, value))CAS操作将元素插入到Hash表中在存在hash冲突时，先把当前节点使用关键字
synchronized加锁，然后再使用tabAt()原子操作判断下有没有线程对数组进行了修改，最后再进行其他操作。 - 首先判断
为什么要锁住更新操作的代码块?
因为发生了哈希冲突，当前线程正在f所在的链表上进行更新操作，假如此时另外一个线程也需要到这个链表上进行更新操作，则需要等待当前线程更新完后再执行
//当前节点加锁
synchronized (f) {
//这里判断下有没有线程对数组进行了修改
if (tabAt(tab, i) == f) {
......//do something
}
}