结构

• 在JDK 1.8中，ConcurrentHashMap已经抛弃了Segment分段锁机制，存储结构采用数组+链表或者红黑树的组合方式，利用CAS+Synchronized来保证并发更新的安全。
• 并发粒度进一步细化到每一个Bucket。
• 引入红黑树结构，节点数超过指定值时，自动将链表转换成红黑树。原因是：链表查询的时间复杂度为O(n)，红黑树查询的时间复杂度为O(log(n))，节点较多时，可大大提升性能。反之，节点变少时（默认小于6时），还会由红黑树，转换为链表。
• 链式Bucket转换成红黑树Bucket还有一个要求，table的容量达到最小树形化容量的阈值，只有当哈希表中的table容量大于该值时，才允许树将链表转换成红黑树的操作。否则，尽管单个Bucket内的元素太多，仍然选择直接扩容，而不是将Bucket树形化。
• 通过一个Node<K,V>数组table来保存Bucket，而在同一个Bucket位置是通过链表和红黑树的形式来保存的。
• 数据结构图如下：
  
• 往table中添加元素时，通过Hash值跟数组长度取余，来决定放在数组的哪个Bucket位置，如果同一位置放多个元素，就优先以链表的形式存放，在同一个位置的元素个数达到了8个以上，如果数组的长度还小于64，就会扩容数组。如果数组的长度大于等于64，就会将该节点的链表转换成树。
• 通过扩容数组的方式来把这些节点分散开。然后将这些元素复制到扩容后的新数组中，同一个Bucket中的元素通过Hash值和数组长度来重新确定位置，可能还是放在原来的位置，也可能放到新的位置。而且，在扩容完成之后，如果之前某个节点是树，但是现在该节点的“Key-Value对”数又小于等于6个，就会将该树转为链表。

put方法

通过cas自旋的方式，并发情况下，也可以保障安全添加成功。

使用CAS自旋完成Bucket的设置时，使用synchronized内置锁保证Bucket内并发操作的线程安全。尽管对同一个Map操作的线程争用会非常激烈，但是在同一个Bucket内的线程争用通常不会很激烈，所以使用CAS自旋（简单轻量级锁）、synchronized偏向锁或轻量级锁不会降低ConcurrentHashMap的性能。为什么不用ReentrantLock显式锁呢？如果为每一个Bucket都创建一个ReentrantLock实例，就会带来大量的内存消耗，反过来，使用CAS自旋（简单轻量级锁）、
synchronized偏向锁或轻量级锁，内存消耗的增加会微乎其微。

步骤如下：

• 循环开始。
• 计算hash值。
• 取当前table，即Node数组。如果table为空，则初始化数组。
• 如果table不为空，从table中，根据hash取节点，如果取到的节点为空，使用cas向此位置添加节点。cas判断条件为：此位置为null，则成功添加，否则失败，交给下一次循环。
• 如果取到的不为空，判断是否为MOVED迁移状态，如果是，返回新的table，然后进入下一次循环。
• 如果不是迁移状态，遍历找key，找不到则向链表或红黑树中添加节点，找到key相同的节点，根据onlyIfAbsent决定是否覆盖值。此过程使用synchronized进行加锁。
• 判断，如果节点数大于临界值，转换成红黑树。
• 节点总数加1。

get方法

没有加锁操作。
● 计算hash值。
● 如果table为空，返回null。
● 如果table不为空，根据hash取节点。遍历节点，找到key相同的，返回值。
● 为保障多线程的可见性，从table中取节点时，使用的是unsafe.getObjectVolatile()方法。
--结束--