ConcurrentHashMap原理

我们都知道Hashmap是线程不安全的,在多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap

HashTable和HashMap的实现原理几乎一样，差别无非是 HashTable不允许key和value为null HashTable是线程安全的但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差

这下就引出了ConcurrentHashMap,ConcurrentHashMap主要就是为了应对hashmap在并发环境下不安全而诞生的，ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响,ConcurrentHashMap避免了对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度.

JDK1.7版本下的ConcurrentHashMap

1.底层数据结构还是数组+链表,HashEntry作为链表的节点
2.采用了segment分段锁计数,在多线程并发更新操作时,对同一个segment进行同步加锁,保证数据安全,这样就可以基于不同segment进行并发操作.
3.同步的实现方式是基于ReentrantLock锁机制(segment继承自ReentrantLock)
4.和HashMap一样,同样存在hash冲突链表查询效率低下的问题.

从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

JDK1.8版本下的ConcurrentHashMap

1.底层数据结构还是基于数组+链表+红黑树.
2.支持多线程的并发操作,实现原理是CAS+synchronized保证并发更新.
3.put方法存放元素时,通过Key对象的hashcode值计算出数组的索引如果没有Node节点,则使用CAS尝试插入元素,失败则无条件自旋到插入成功;如果存在Node,则使用synchronized锁住该Node元素(链表或红黑树的头结点),在执行插入操作.

总结

1.键,值迭代器都为弱一致性迭代器,创建迭代器后,可以对元素进行更新.
2.读操作没有加锁,value是volatile修饰的,保证了可见性,是线程安全的.
3.读写操作分离可以提高效率:多线程对不同的Node/segment的插入和删除是可以并发,并行执行,对同一个Node/segment的写操作是互斥的.读操作都是无锁操作,可以并发,并行执行.

1.数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。
JDK1.8采用CAS+Synchronized保证线程安全。
3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。