JDK1.8下ConcurrentHashMap的一些理解(一)

栏目: Java · 发布时间: 5年前

内容简介:在JDK1.8里面,

在JDK1.8里面, ConcurrentHashMap 在put方法里面已经将分段锁移除了,转而是CAS锁和synchronized

ConcurrentHashMapJava 里面同时兼顾性能和线程安全的一个键值对集合,同属于键值对的集合还有 HashTable 以及 HashMap

HashTable 是一个线程安全的类,因为它的所有 public 方法都被 synchronized 修饰,这样就导致了一个问题,就是效率太低。

虽然 HashMapJDK1.8 的并发场景下触发扩容时不会出现成环了,但是会出现数据丢失的情况。

所以如果需要在多线程的情况下(多读少写))使用Map集合的话, ConcurrentHashMap 是一个不错的选择。

ConcurrentHashMap 在JDK1.8的时候将put()方法中的分段锁 Segment 移除,转而采用一种 CAS 锁和 synchronized 来实现插入方法的线程安全。

如下代码:

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
       //省略相关代码
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            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;
                synchronized (f) {
                    //省略相关代码
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

可以看到在 JDK1.8 里面, ConcurrentHashMap 是直接采用 数组 + 链表 + 红黑树 来实现,时间复杂度在O(1)和O(n)之间,如果链表转化为红黑树了,那么就是O(1)到O(nlogn)。

在这里值得一提的是, ConcurrentHashMap 会判断 tabAt(tab, i = (n - 1) & hash) 是不是 null,是的话就直接采用 CAS 进行插入,而如果不为空的话,则是 synchronized 锁住当前 Node 的首节点,这是因为当该 Node 不为空的时候,证明了此时出现了 Hash 碰撞,就会涉及到 链表 的尾节点新增或者 红黑树 的节点新增以及 红黑树 的平衡,这些操作自然都是非原子性的。

从而导致无法使用 CAS ,当 Node 的当前下标为null的时候,由于只是涉及数组的新增,所以用 CAS 即可。

因为CAS是一种基于版本控制的方式来实现,而碰撞之后的操作太多,所以直接用 synchronized 比较合适。

ConcurrentHashMap在迭代时和HashMap的区别

当一个集合在迭代的时候如果动态的添加或者删除元素,那么就会抛出 Concurrentmodificationexception ,但是在 ConcurrentHashMap 里面却不会,例如如下代码:

public static void main(String[] args) {
    Map<String,String> map = new ConcurrentHashMap<String, String>();
    map.put("a","a1");
    map.put("b","b1");
    map.put("c","c1");
    map.put("d","d1");
    map.put("e","e1");
    Iterator<String> iterator = map.keySet().iterator();
    while (iterator.hasNext()){
        String it = iterator.next();
        if("b".equals(it)){
            map.remove("d");
        }
        System.out.println(it);
    }
}

控制台打印如下:
a
b
c
e

而当你把 ConcurrentHashMap 换成 HashMap 的时候,控制台就会抛出一个异常:

Exception in thread "main" a
b
java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextNode(HashMap.java:1442)
    at java.util.HashMap$KeyIterator.next(HashMap.java:1466)
    at xyz.somersames.ListTest.main(ListTest.java:22)

原因在于 ConcurrentHashMapnext 方法并不会去检查 modCountexpectedModCount ,但是会检查下一个节点是不是为空

if ((p = next) == null)
    throw new NoSuchElementException();

当我们进行remove的时候, ConcurrentHashMap 会直接通过修改指针的方式来进行移除操作,同样的,也会锁住 数组 的头节点直至移除结束,所以在同一个时刻,只会有一个线程对 当前数组下标的所有节点 进行操作。

但是在 HashMap 里面, next 方法会进行一个check,而remove操作会修改 modCount ,导致 modCountexpectedModCount 不相等,所以就会导致

ConcurrentModificationException

稍微修改下代码:

public static void main(String[] args) {
    Map<String,String> map = new ConcurrentHashMap<String, String>();
    map.put("a","a1");
    map.put("b","b1");
    map.put("c","c1");
    map.put("d","d1");
    map.put("e","e1");
    Iterator<String> iterator = map.keySet().iterator();
    while (iterator.hasNext()){
        if("b".equals(iterator.next())){
            map.remove("d");
        }
        System.out.println(iterator.next());
    }
}
控制台打印如下:
b
d
Exception in thread "main" java.util.NoSuchElementException
    at java.util.concurrent.ConcurrentHashMap$KeyIterator.next(ConcurrentHashMap.java:3416)
    at com.xzh.ssmtest.ListTest.main(ListTest.java:25)

并发下的处理

由于每一个 Node 的首节点都会被 synchronized 修饰,从而将一个元素的新增转化为一个原子操作,同时 Nodevaluenext 都是由 volatile 关键字进行修饰,从而可以保证可见性。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python算法教程

Python算法教程

[挪威] Magnus Lie Hetland 赫特兰 / 凌杰、陆禹淳、顾俊 / 人民邮电出版社 / 2016-1-1 / 69.00元

本书用Python语言来讲解算法的分析和设计。本书主要关注经典的算法,但同时会为读者理解基本算法问题和解决问题打下很好的基础。全书共11章。分别介绍了树、图、计数问题、归纳递归、遍历、分解合并、贪心算法、复杂依赖、Dijkstra算法、匹配切割问题以及困难问题及其稀释等内容。本书在每一章结束的时候均有练习题和参考资料,这为读者的自我检查以及进一步学习提供了较多的便利。在全书的最后,给出了练习题的提......一起来看看 《Python算法教程》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

MD5 加密
MD5 加密

MD5 加密工具

SHA 加密
SHA 加密

SHA 加密工具