currenthashmap实现原理_ConcurrentHashMap的实现原理
（JDK。。。
哈希表
1.介绍
哈希表就是⼀种以 键-值(key-indexed) 存储数据的结构，我们只要输⼊待查找的值即key，即可查找到其对应的值。
哈希的思路很简单，如果所有的键都是整数，那么就可以使⽤⼀个简单的⽆序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
2.链式哈希表
链式哈希表从根本上说是由⼀组链表构成。每个链表都可以看做是⼀个“桶”，我们将所有的元素通过散列的⽅式放到具体的不同的桶中。插⼊元素时，⾸先将其键传⼊⼀个哈希函数（该过程称为哈希键），函数通过散列的⽅式告知元素属于哪个“桶”，然后在相应的链表头插⼊元素。查找或删除元素时，⽤同们的⽅式先找到元素的“桶”，然后遍历相应的链表，直到发现我们想要的元素。因为每个“桶”都是⼀个链表，所以链式哈希表并不限制包含元素的个数。然⽽，如果表变得太⼤，它的性能将会降低。
3.应⽤场景
我们熟知的缓存技术（⽐如redis、memcached）的核⼼其实就是在内存中维护⼀张巨⼤的哈希表，还有⼤家熟知的HashMap、CurrentHashMap等的应⽤。
ConcurrentHashMap与HashMap等的区别
1.HashMap
所以在我们知道HashMap是线程不安全的，在多线程环境下，使⽤Hashmap进⾏put操作会引起死循环，导致CPU利⽤率接近100%，所以在并发情况下不能使⽤HashMap。
2.HashTable
HashTable和HashMap的实现原理⼏乎⼀样，差别⽆⾮是
HashTable不允许key和value为null
HashTable是线程安全的
给整个哈希表加了但是HashTable线程安全的策略实现代价却太⼤了，简单粗暴，get/put所有相关操
作都是synchronized的，这相当于给整个哈希表加了⼀把⼤锁。
多线程访问时候，只要有⼀个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串⾏化，在竞争激烈的并发场景中性能就会⾮常差。
3.ConcurrentHashMap
主要就是为了应对hashmap在并发环境下不安全⽽诞⽣的，ConcurrentHashMap的设计与实现⾮常精巧，⼤量的利⽤了
volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响。
数组+链表结构（JDK1.8该为数组+红⿊树）。
我们都知道Map⼀般都是数组+链表结构
ConcurrentHashMap避免了对全局加锁改成了局部加锁操作，这样就极⼤地提⾼了并发环境下的操作速度，由于ConcurrentHashMap避免了对全局加锁改成了局部加锁操作
ConcurrentHashMap在JDK1.7和1.8中的实现⾮常不同，接下来我们谈谈JDK在1.7和1.8中的区别。
JDK1.7版本的CurrentHashMap的实现原理
数组+Segment+分段锁的⽅式实现。
在JDK1.7中ConcurrentHashMap采⽤了数组+Segment+分段锁
1.Segment(分段锁)
ConcurrentHashMap中的分段锁称为Segment
分段锁称为Segment，它即类似于HashMap的结构，即内部拥有⼀个Entry数组，数组中的每个元素⼜是⼀个链表，同时⼜是⼀个ReentrantLock（Segment继承了ReentrantLock）。
2.内部结构
ConcurrentHashMap使⽤分段锁技术，将数据分成⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当
⼀个线程占⽤锁访问其中⼀个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：
从上⾯的结构我们可以了解到，ConcurrentHashMap定位⼀个元素的过程需要进⾏两次Hash操作。
第⼀次Hash定位到Segment，第⼆次Hash定位到元素所在的链表的头部。
3.该结构的优劣势
坏处
这⼀种结构的带来的副作⽤是Hash的过程要⽐普通的HashMap要长
好处
写操作的时候可以只对元素所在的Segment进⾏加锁即可，不会影响到其他的Segment，这样，在最理想的情况
下，ConcurrentHashMap可以最⾼同时⽀持Segment数量⼤⼩的写操作（刚好这些写操作都⾮常平均地分布在所有的Segment上）。
所以，通过这⼀种结构，ConcurrentHashMap的并发能⼒可以⼤⼤的提⾼。
JDK1.8版本的CurrentHashMap的实现原理
内部⼤量采⽤CAS操作，JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采⽤了数组+链表+红⿊树的实现⽅式来设计，内部⼤量采⽤CAS操作，这⾥我简要介绍下CAS。
CAS是compare and swap的缩写，即我们所说的⽐较交换。cas是⼀种基于锁的操作，⽽且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等⼀个之前获得锁的线程释放锁之后，下⼀个线程才可以访问。⽽乐观锁采取了⼀种宽泛的态度，通过某种⽅式不加锁来处理资源，⽐如通过给记录加version来获取数据，性能较悲观锁有很⼤的提⾼。
CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址⾥⾯的值和A的值是⼀样的，那么就将内存⾥⾯的值更新成B。CAS是通过⽆限循环来获取数据的，若果在第⼀轮循环中，a线程获取地址⾥⾯的值被b线程修改了，那么a线程需要⾃旋，到下次循环才有可能机会执⾏。
JDK8中彻底放弃了Segment转⽽采⽤的是Node，其设计思想也不再是JDK1.7中的分段锁思想。
Node：保存key，value及key的hash值的数据结构。其中value和next都⽤volatile修饰，保证并发的可见性。
class Node implements Map.Entry
implements Map.Entry { {
class Node
Java8 ConcurrentHashMap结构基本上和Java8的HashMap⼀样，不过保证线程安全性。
在JDK8中ConcurrentHashMap的结构，由于引⼊了红⿊树，使得ConcurrentHashMap的实现⾮常复杂，我们都知道，红⿊树是⼀种性能⾮常好的⼆叉查找树，其查找性能为O（logN），但是其实现过程也⾮常复杂，⽽且可读性也⾮常差，DougLea的思维能⼒确实不是⼀般⼈能⽐的，早期完全采⽤链表结构时Map的查找时间复杂度为O（N），JDK8中ConcurrentHashMap在链表的长度⼤于某个阈值的时候会将链表转换成红⿊树进⼀步提⾼其查找性能。
总结
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对⽽⾔，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红⿊树。
1.数据结构：
1.数据结构：取消了Segment分段锁的数据结构，取⽽代之的是数组+链表+红⿊树的结构。
2.保证线程安全机制：JDK1.7采⽤gment的分段锁机制实现线程安全，其中gment继承⾃ReentrantLock。JDK1.8采⽤
2.保证线程安全机制：
CAS+Synchronized保证线程安全。
3.锁的粒度：
3.锁的粒度：原来是对需要进⾏数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
4.链表转化为红⿊树：定位结点的hash算法简化会带来弊端,Hash冲突加剧，因此在链表节点数量⼤于8时，会将链表转化为红⿊树进⾏存4.链表转化为红⿊树：
储。
5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红⿊树O(logN)。
5.查询时间复杂度：
如何⼀起学习，有没有免费资料？
本⽂由博客⼀⽂多发平台 OpenWrite 发布！
