资讯专栏INFORMATION COLUMN

[学习笔记-Java集合-8] Map - ConcurrentHashMap 源码分析(二)

2501207950 / 1676人阅读

摘要:那么,如果之后不是简单的操作,而是还有其它业务操作,之后才是,比如下面这样,这该怎么办呢其它业务操作这时候就没办法使用提供的方法了,只能业务自己来保证线程安全了,比如下面这样其它业务操作这样虽然不太友好,但是最起码能保证业务逻辑是正确的。

删除元素

删除元素跟添加元素一样,都是先找到元素所在的桶,然后采用分段锁的思想锁住整个桶,再进行操作。

public V remove(Object key) {
    // 调用替换节点方法
    return replaceNode(key, null, null);
}

final V replaceNode(Object key, V value, Object cv) {
    // 计算hash
    int hash = spread(key.hashCode());
    // 自旋
    for (Node[] tab = table;;) {
        Node f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
            // 如果目标key所在的桶不存在,跳出循环返回null
            break;
        else if ((fh = f.hash) == MOVED)
            // 如果正在扩容中,协助扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 标记是否处理过
            boolean validated = false;
            synchronized (f) {
                // 再次验证当前桶第一个元素是否被修改过
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        // fh>=0表示是链表节点
                        validated = true;
                        // 遍历链表寻找目标节点
                        for (Node e = f, pred = null;;) {
                            K ek;
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {
                                // 找到了目标节点
                                V ev = e.val;
                                // 检查目标节点旧value是否等于cv
                                if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                    oldVal = ev;
                                    if (value != null)
                                        // 如果value不为空则替换旧值
                                        e.val = value;
                                    else if (pred != null)
                                        // 如果前置节点不为空
                                        // 删除当前节点
                                        pred.next = e.next;
                                    else
                                        // 如果前置节点为空
                                        // 说明是桶中第一个元素,删除之
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            // 遍历到链表尾部还没找到元素,跳出循环
                            if ((e = e.next) == null)
                                break;
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 如果是树节点
                        validated = true;
                        TreeBin t = (TreeBin)f;
                        TreeNode r, p;
                        // 遍历树找到了目标节点
                        if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                            V pv = p.val;
                            // 检查目标节点旧value是否等于cv
                            if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) {
                                oldVal = pv;
                                if (value != null)
                                    // 如果value不为空则替换旧值
                                    p.val = value;
                                else if (t.removeTreeNode(p))
                                    // 如果value为空则删除元素
                                    // 如果删除后树的元素个数较少则退化成链表
                                    // t.removeTreeNode(p)这个方法返回true表示删除节点后树的元素个数较少
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            // 如果处理过,不管有没有找到元素都返回
            if (validated) {
                // 如果找到了元素,返回其旧值
                if (oldVal != null) {
                    // 如果要替换的值为空,元素个数减1
                    if (value == null)
                        addCount(-1L, -1);
                    return oldVal;
                }
                break;
            }
        }
    }
    // 没找到元素返回空
    return null;
}

计算hash;

如果所在的桶不存在,表示没有找到目标元素,返回;

如果正在扩容,则协助扩容完成后再进行删除操作;

如果是以链表形式存储的,则遍历整个链表查找元素,找到之后再删除;

如果是以树形式存储的,则遍历树查找元素,找到之后再删除;

如果是以树形式存储的,删除元素之后树较小,则退化成链表;

如果确实删除了元素,则整个map元素个数减1,并返回旧值;

如果没有删除元素,则返回null;

获取元素

获取元素,根据目标key所在桶的第一个元素的不同采用不同的方式获取元素,关键点在于find()方法的重写。

public V get(Object key) {
    Node[] tab; Node e, p; int n, eh; K ek;
    // 计算hash
    int h = spread(key.hashCode());
    // 如果元素所在的桶存在且里面有元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果第一个元素就是要找的元素,直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            // hash小于0,说明是树或者正在扩容
            // 使用find寻找元素,find的寻找方式依据Node的不同子类有不同的实现方式
            return (p = e.find(h, key)) != null ? p.val : null;

        // 遍历整个链表寻找元素
        while ((e = e.next) != null) {
            if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

hash到元素所在的桶;

如果桶中第一个元素就是该找的元素,直接返回;

如果是树或者正在迁移元素,则调用各自Node子类的find()方法寻找元素;

如果是链表,遍历整个链表寻找元素;

获取元素没有加锁;

获取元素个数

元素个数的存储也是采用分段的思想,获取元素个数时需要把所有段加起来。

public int size() {
    // 调用sumCount()计算元素个数
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                    (int)n);
}

final long sumCount() {
    // 计算CounterCell所有段及baseCount的数量之和
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

元素的个数依据不同的线程存在在不同的段里;(见addCounter()分析)

计算CounterCell所有段及baseCount的数量之和;

获取元素个数没有加锁;

总结

(1)ConcurrentHashMap是HashMap的线程安全版本;

(2)ConcurrentHashMap采用(数组 + 链表 + 红黑树)的结构存储元素;

(3)ConcurrentHashMap相比于同样线程安全的HashTable,效率要高很多;

(4)ConcurrentHashMap采用的锁有 synchronized,CAS,自旋锁,分段锁,volatile等;

(5)ConcurrentHashMap中没有threshold和loadFactor这两个字段,而是采用sizeCtl来控制;

(6)sizeCtl = -1,表示正在进行初始化;

(7)sizeCtl = 0,默认值,表示后续在真正初始化的时候使用默认容量;

(8)sizeCtl > 0,在初始化之前存储的是传入的容量,在初始化或扩容后存储的是下一次的扩容门槛;

(9)sizeCtl = (resizeStamp << 16) + (1 + nThreads),表示正在进行扩容,高位存储扩容邮戳,低位存储扩容线程数加1;

(10)更新操作时如果正在进行扩容,当前线程协助扩容;

(11)更新操作会采用synchronized锁住当前桶的第一个元素,这是分段锁的思想;

(12)整个扩容过程都是通过CAS控制sizeCtl这个字段来进行的,这很关键;

(13)迁移完元素的桶会放置一个ForwardingNode节点,以标识该桶迁移完毕;

(14)元素个数的存储也是采用的分段思想,类似于LongAdder的实现;

(15)元素个数的更新会把不同的线程hash到不同的段上,减少资源争用;

(16)元素个数的更新如果还是出现多个线程同时更新一个段,则会扩容段(CounterCell);

(17)获取元素个数是把所有的段(包括baseCount和CounterCell)相加起来得到的;

(18)查询操作是不会加锁的,所以ConcurrentHashMap不是强一致性的;

(19)ConcurrentHashMap中不能存储key或value为null的元素;

学习重点

ConcurrentHashMap中值得学习的技术

(1)CAS + 自旋,乐观锁的思想,减少线程上下文切换的时间;

(2)分段锁的思想,减少同一把锁争用带来的低效问题;

(3)CounterCell,分段存储元素个数,减少多线程同时更新一个字段带来的低效;

(4)@sun.misc.Contended(CounterCell上的注解),避免伪共享;

(5)多线程协同进行扩容;

ConcurrentHashMap 并发下使用问题

看下面的使用例子:

private static final Map map = new ConcurrentHashMap<>();

public void unsafeUpdate(Integer key, Integer value) {
    Integer oldValue = map.get(key);
    if (oldValue == null) {
        map.put(key, value);
    }
}

如果有多个线程同时调用unsafeUpdate()这个方法,ConcurrentHashMap是无法保证线程安全的。

因为get()之后if之前可能有其它线程已经put()了这个元素,这时候再put()就把那个线程put()的元素覆盖了。

那怎么修改呢?

使用putIfAbsent()方法,它会保证元素不存在时才插入元素,如下:

public void safeUpdate(Integer key, Integer value) {
    map.putIfAbsent(key, value);
}

那么,如果上面oldValue不是跟null比较,而是跟一个特定的值比如1进行比较怎么办?也就是下面这样:

public void unsafeUpdate(Integer key, Integer value) {
    Integer oldValue = map.get(key);
    if (oldValue == 1) {
        map.put(key, value);
    }
}

这样的话就没办法使用putIfAbsent()方法了。

其实,ConcurrentHashMap还提供了另一个方法叫replace(K key, V oldValue, V newValue)可以解决这个问题。

replace(K key, V oldValue, V newValue)这个方法可不能乱用,如果传入的newValue是null,则会删除元素。

public void safeUpdate(Integer key, Integer value) {
    map.replace(key, 1, value);
}

那么,如果if之后不是简单的put()操作,而是还有其它业务操作,之后才是put(),比如下面这样,这该怎么办呢?

public void unsafeUpdate(Integer key, Integer value) {
    Integer oldValue = map.get(key);
    if (oldValue == 1) {
        System.out.println(System.currentTimeMillis());
        /**
         * 其它业务操作
         */
        System.out.println(System.currentTimeMillis());

        map.put(key, value);
    }
}

这时候就没办法使用ConcurrentHashMap提供的方法了,只能业务自己来保证线程安全了,比如下面这样:

public void safeUpdate(Integer key, Integer value) {
    synchronized (map) {
        Integer oldValue = map.get(key);
        if (oldValue == null) {
            System.out.println(System.currentTimeMillis());
            /**
             * 其它业务操作
             */
            System.out.println(System.currentTimeMillis());

            map.put(key, value);
        }
    }
}

这样虽然不太友好,但是最起码能保证业务逻辑是正确的。
当然,这里使用ConcurrentHashMap的意义也就不大了,可以换成普通的HashMap了。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/76238.html

相关文章

  • [学习笔记-Java集合-7] Map - ConcurrentHashMap 源码分析(一)

    摘要:简介是的线程安全版本,内部也是使用数组链表红黑树的结构来存储元素。相比于同样线程安全的来说,效率等各方面都有极大地提高。中的关键字,内部实现为监视器锁,主要是通过对象监视器在对象头中的字段来表明的。 简介 ConcurrentHashMap是HashMap的线程安全版本,内部也是使用(数组 + 链表 + 红黑树)的结构来存储元素。 相比于同样线程安全的HashTable来说,效率等各方...

    SoapEye 评论0 收藏0
  • 一文掌握关于Java数据结构所有知识点(欢迎一起完善)

    摘要:是栈,它继承于。满二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。没有键值相等的节点。这是数据库选用树的最主要原因。 在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系统的Java学习以及面试的相关知识。本来是想通过Gitbook的...

    keithxiaoy 评论0 收藏0
  • Java 容器学习之 HashMap

    摘要:底层的数据结构就是数组链表红黑树,红黑树是在中加进来的。负载因子哈希表中的填满程度。 前言 把 Java 容器的学习笔记放到 github 里了,还在更新~其他的目前不打算抽出来作为文章写,感觉挖的还不够深,等对某些东西理解的更深了再写文章吧Java 容器目录如下: Java 容器 一、概述 二、源码学习 1. Map 1.1 HashMap 1.2 LinkedHashM...

    Alex 评论0 收藏0
  • Java相关

    摘要:本文是作者自己对中线程的状态线程间协作相关使用的理解与总结,不对之处,望指出,共勉。当中的的数目而不是已占用的位置数大于集合番一文通版集合番一文通版垃圾回收机制讲得很透彻,深入浅出。 一小时搞明白自定义注解 Annotation(注解)就是 Java 提供了一种元程序中的元素关联任何信息和着任何元数据(metadata)的途径和方法。Annotion(注解) 是一个接口,程序可以通过...

    wangtdgoodluck 评论0 收藏0
  • 这几道Java集合框架面试题在面试中几乎必问

    摘要:若遇到哈希冲突,则将冲突的值加到链表中即可。之后相比于之前的版本,之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值默认为时,将链表转化为红黑树,以减少搜索时间。有序,唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容: Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

    bigdevil_s 评论0 收藏0

发表评论

0条评论

2501207950

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<