我们知道HashMap是线程不安全的，在JDK1.7及之前，高并发环境下很容易出现环形链表（或者称为闭环链），导致get操作一直处于死循环，CPU飙升100%。

其实，java给我们提供了其他的线程安全的容器，像HashTable,
Collections.sychorinizedMap等。但是，翻过他们源码的人都知道，他们的所谓安全是对整个数据集加锁，导致一旦锁被占用，其他操作都会被阻塞，性能在高并发场景下惨不忍睹。

ConcurrentHashMap就在这样的背景下诞生了，既兼顾了线程安全，又提升了效率。

JDK1.7版本的ConcurrentHashMap

内部使用了Segment的概念，每个Segment可以看成一个HashMap实例，Segment继承了重入锁，所以我们可以看做每个Segment都是一把锁，一个ConcurrentHashMap包含2的N次方个Segment,不同Segment相互独立，互不影响，那么ConcurrentHashMap依靠分段锁机制实现了高并发场景下的线程安全和高效率。由此可知，同一Segment下的读写不阻塞，不同Segment的写操作不阻塞，同一Segment下的并发写会阻塞。

JDK1.8下的CocurrentHashMap

JDK1.8在HashMap的基本上做了多处优化，实现比1.7要复杂的多，优化如下：

1.数据结构：数据+链表+红黑树，取消了Segment的2层hash表设计。

2.锁机制：使用sychorinized+CAS替换了1.7中重入锁（Segment继承了ReentrantLock）

3.锁粒度：1.8中只加锁hash表中的头结点而并非1.7中的整个Segment对象，锁粒度变小

4.数据结构优化：定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。

5.时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

put方法实现逻辑：

源码：

1.根据key的hash值定位到桶位置

2.判断if(table==null)，先初始化table。

3.判断if(table[i]==null),cas添加元素。成功则跳出循环，失败则进入下一轮for循环。

4.判断是否有其他线程在扩容table，有则帮忙扩容，扩容完成再添加元素。进入真正的put步骤

5.真正的put步骤。桶的位置不为空，遍历该桶的链表或者红黑树，若key已存在，则覆盖；不存在则将key插入到链表或红黑树的尾部。

并发问题：假如put操作时正好有别的线程正在对table数组(map)扩容怎么办？

暂停put操作，先帮助其他线程对map扩容。

get方法:

1.根据key的hash值定位到桶位置。

2.map是否初始化，没有初始化则返回null。否则进入3

3.定位到的桶位置是否有头结点，没有返回nul,否则进入4

4.是否有其他线程在扩容，有的话调用find方法查找。所以这里可以看出，扩容操作和get操作不冲突，扩容map的同时可以get操作。

5.若没有其他线程在扩容，则遍历桶对应的链表或者红黑树，使用equals方法进行比较。key相同则返回value,不存在则返回null.

并发问题：假如此时正好有别的线程正在对数组扩容怎么办？

没关系，扩容的时候不会破坏原来的table，遍历任然可以继续，不需要加锁。

扩容方法:

什么情况会导致扩容？

1.链表转换为红黑树时(链表节点个数达到8个可能会转换为红黑树)。如果转换时map长度小于64则直接扩容一倍，不转化为红黑树。如果此时map长度大于64，则不会扩容，直接进行链表转红黑树的操作。

2.map中总节点数大于阈值(即大于map长度的0.75倍)时会进行扩容。

如何扩容？

1.创建一个新的map，是原先map的两倍。注意此过程是单线程创建的

2.复制旧的map到新的map中。注意此过程是多线程并发完成。（将map按照线程数量平均划分成多个相等区域，每个线程负责一块区域的复制任务）

扩容的具体过程：

注：扩容操作是hashmap最复杂难懂的地方，博主也是看了很久才看懂个大概。一两句话真的很难说清楚，建议有时间还是看源码比较好。网上很少有人使用通俗易懂语言来描述扩容的机制。所以这里我尝试用自己的语言做一个简要的概括，描述一下大体的流程，供大家参考，如果觉得不错，可以点个赞，表示对博主的支持，谢谢。

整体思路：扩容是并发扩容，也就是多个线程共同协作，把旧table中的链表一个个复制到新table中。

1.给多个线程划分各自负责的区域。分配时是从后向前分配。假设table原先长度是64，有四个线程，则第一个到达的线程负责48-63这块内容的复制，第二个线程负责32-47，第三个负责16-31，第四个负责0-15。

2.每个线程负责各自区域，复制时是一个个从后向前复制的。如第一个线程先复制下标为63的桶的复制。63复制完了接下来复制62，一直向前，直到完成自己负责区域的所有复制。

3.完成自己区域的任务之后，还没有结束，这时还会判断一下其他线程负责区域有没有完成所有复制任务，如果没有完成，则可能还会去帮助其它线程复制。比如线程1先完成了，这时它看到线程2才做了一半，这时它会帮助线程2去做剩下一半任务。

4.那么复制到底是怎么完成的呢？线程之间相互帮忙会导致混乱吗？

5.首先回答上面第一个问题，我们知道，每个数组的每个桶存放的是一个链表（红黑树也可能，这里只讨论是链表情况）。复制的时候，先将链表拆分成两个链表。拆分的依据是链表中的每个节点的hash值和未扩容前数组长度n进行与运算。运算结果可能为0和1，所以结果为0的组成一个新链表，结果为1的组成一个新链表。为0的链表放在新table的 i 位置，为1的链表放在 新table的 i+n处。扩容后新table是原先table的两倍，即长度是2n。

6.接着回答上面第二个问题，线程之间相互帮忙不会造成混乱。因为线程已完成复制的位置会标记该位置已完成，其他线程看到标记则会直接跳过。而对于正在执行的复制任务的位置，则会直接锁住该桶，表示这个桶我来负责，其他线程不要插手。这样，就不会有并发问题了。

7.什么时候结束呢？每个线程参加复制前会将标记位sizeCtl加1，同样退出时会将sizeCtl减1，这样每个线程退出时，只要检查一下sizeCtl是否等于进入前的状态就知道是否全都退出了。最后一个退出的线程，则将就table的地址更新指向新table的地址，这样后面的操作就是新table的操作了。

remove方法

1.根据入参key,计算其hash值

2.遍历整个table，如果table为空或者其长度为0，则break.

3.如果hash==MOVED,则执行扩容，否则执行4

4.如果当前索引的数据结构是链表，遍历链表，并删除key所在的节点，如果是红黑树，则同样删除其所在节点，并返回节点的值。

5.如果没有在table中定位到key的节点，则返回null.