文章目录

前言相关数据结构对比ConcurrentHashMap原理总结

前言

面试中常常问到Hashmap原理,这属于第一阶段的过招，之后面试官可能会顺势问一下，Hashmap是否是线程安全的。连环问于是开始了，如果你回答不是，那么紧接着面试官会问有没有什么数据结构可以保证线程安全。有一定研究的你可以会马上联想到有，比如ConcurrentHashMap。好戏开始上演……

请先看下面代码：

public class Test { private ConcurrentHashMap mMap = new ConcurrentHashMap(); // map中不存在才加入，否则不加入 public void addIfNotExists(String key, String value) { if (!mMap.containsKey(key)) { mMap.put(key, value); } } }

请问：是否是线程安全？

可能你会条件反射的回答，是线程安全的。因为之前的回答已经做了一定的铺垫。那么到底是不是线程安全的呢？

问题的背后，往往是深层次的原理考察。于是，我开始了相关知识模块V1.0的构建。

第一步，了解HashMap原理和特点，并同时对比联想相邻的知识点，在查阅大量资料后，下面直接说结论，不再此一一展开。

相关数据结构对比

HashMap

读取快，插入慢,线程不安全

底层是数组+链表 结构，当两个线程同时插入需要扩容的时候，获得改map的size()大小不一样，则会报错。当有两个线程在读，第三个线程正好在对map扩容时，这两个线程就会进入死循环，cup占用率就会高。

在多线程，使用HaspMap就行put操作会引起死循环，导致cpu100%。所在在并发情况不能使用HashMap。

HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry。

LinkedHashMap

​ 读取快，插入慢

treeMap

可以实现元素的自动排序

HashTable

线程安全。

HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下，因为在一个线程访问HashTable的同步方法，其它线程也访问HashTable的同步方法是，会进入阻塞或轮询状态

concurrentHashMap

线程安全，支持高并发的操作，特点：效率比Hashtable高，并发性比hashmap好。结合了两者的特点。（本文介绍的主角）

HashTable容器在竞争激烈的并发下表现出的效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁，加入容器里有多把锁，每一把锁用于容器其中一部分数据，那么当多线程访问容器里不同的数据段是，线程间就不会出现锁竞争，从而可以有效的提高并发效率。将数据分成一段一段的存储，然后给每一段分配一把锁，当前程占用锁访问其中的一个段的数据的时候，其它的数据也能被其它的线程访问

ConcurrentHashMap原理

ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。

不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。

每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁,可以简单理解成把一个大的HashTable分解成多个，形成了锁分离。

而Hashtable的实现方式是—锁整个hash表。 （图片来源于网络）

走进源码：

public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { //不允许 key或value为null if (key == null || value == null) throw new NullPointerException(); //计算hash值 int hash = spread(key.hashCode()); int binCount = 0; //死循环 何时插入成功 何时跳出 for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; //如果table为空的话，初始化table if (tab == null || (n = tab.length) == 0) tab = initTable(); //根据hash值计算出在table里面的位置 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果这个位置没有值 ，直接放进去，不需要加锁 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } //当遇到表连接点时，需要进行整合表的操作 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; //结点上锁 这里的结点可以理解为hash值相同组成的链表的头结点 synchronized (f) { if (tabAt(tab, i) == f) { //fh〉0 说明这个节点是一个链表的节点 不是树的节点 if (fh >= 0) { binCount = 1; //在这里遍历链表所有的结点 for (Node<K,V> e = f;; ++binCount) { K ek; //如果hash值和key值相同 则修改对应结点的value值 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; //如果遍历到了最后一个结点，那么就证明新的节点需要插入 就把它插入在链表尾部 if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } //如果这个节点是树节点，就按照树的方式插入值 else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { //如果链表长度已经达到临界值8 就需要把链表转换为树结构 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } //将当前ConcurrentHashMap的元素数量+1 addCount(1L, binCount); return null; }

ConcurrentHashMap的put方法和HashMap的逻辑差不多，主要是新增了线程安全部分，在添加元素时候，采用synchronized来保证线程安全，然后计算size的时候采用CAS操作进行计算。put流程小结：

1.判断key和vaule是否为空，如果为空，直接抛出异常。

2.判断table数组是否已经初始化完毕，如果没有初始化，进行初始化。

3.计算key的hash值，如果该位置为空，直接构造节点放入。

4.如果table正在扩容，进入帮助扩容方法。

5.最后开启同步锁，进行插入操作，如果开启了覆盖选项，直接覆盖，否则，构造节点添加到尾部，如果节点数超过红黑树阈值，进行红黑树转换。如果当前节点是树节点，进行树插入操作。

6.最后统计size大小，并计算是否需要扩容。

总结

JDK6,7中的ConcurrentHashmap主要使用Segment来实现减小锁粒度，把HashMap分割成若干个Segment，在put的时候需要锁住Segment，get时候不加锁，使用volatile来保证可见性，当要统计全局时（比如size），首先会尝试多次计算modcount来确定，这几次尝试中，是否有其他线程进行了修改操作，如果没有，则直接返回size。如果有，则需要依次锁住所有的Segment来计算。

最后，回答开头的问题。

我的研究结果是：线程安全，因为通过put源码分析，在插入数据时用了同步锁synchronized。

对于赶时间的面试官来说，是还是不是，就够了，至于为什么，想扩展什么的根据情况再说，但是我们自己得知道问题的背后以及是否触及到你的知识的盲区，这也是本文总结的动机由来。

如有不足之处，欢迎PK。毕竟，知识无边界，我们需要多个角度看世界。

参考资料：

1.多线程为什么要用ConcurrentHashMap

2.ConcurrentHashMap总结

3.ConcurrentHashMap的实现 get put remove 详解