面试中常常问到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 采用了分段锁技术,其中 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 详解