54.CurrentHashMap

/**
* 每天一个知识点day54 TODO ConcurrentHashMap
* 在并发变成中HashMap可能会导致程序死循环，Hashtable效率又比较低下，
* 基于这两个原因所以有了ConcurrentHashMap
*
* Hashtable效率低下的原因是所有访问Hashtable的线程必须竞争同一把
* 锁，假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，
* 那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争。
* 从而可以有效提高并发访问效率，这就是ConcurrentHashMap使用的锁分段
* 技术，首先将数据分成一段一段地存储，然后给每一段数据配一把锁，
* 当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
*
* ConcurrentHashMap结构：
* JDK1.7中是由Segment数组结构和HashEntry数组结构组成，Segment是一种可
* 重入锁(ReentrantLock)，HashEntry则是用于存储键值对数据，
* 一个ConcurrentHashMap包含一个Segment数组，Segment结构和HashMap类似，
* 是一种数组和链表结构，一个Segment里包含一个HashEntry数组，每一个HashEntry
* 是一个链表结构的元素，每个Segment里包含一个HashEntry数组里的元素，
* 当对HashEntry里的数据进行修改时，首先要获取到与它对应的Segment锁，
*
* JDK1.8版本的CurrentHashMap采用了数组+链表+红黑树的实现方式来设计，
* 内部大量采用CAS操作
* CAS是compare and swap的缩写，即我们所说的比较交换。
* cas是一种基于锁的操作，而且是乐观锁。在java中锁分为乐观锁和悲观锁。
* 悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。
* 而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源。
* CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。
* 如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。
* CAS是通过无限循环来获取数据的，如果在第一轮循环中，a线程获取地址里面的值被b线程修改了，
* 那么a线程需要自旋，到下次循环才有可能机会执行。
*
* JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。
*
* 1.数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
* 2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，
* 其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
* 3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
* 4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,
* 因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
* 5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。
*
*
* get操作
* 先经过一次散列，然后使用这个散列值通过散列运算定位到Segment，
* 再通过散列算法定位到元素，get整个过程不需要加锁，除非读到的值是空才会
* 加锁重读，
*/