美文网首页
ConcurrentHashMap源码解析(3)

ConcurrentHashMap源码解析(3)

作者: yijian2595 | 来源:发表于2018-12-20 09:50 被阅读4次

    此文已由作者赵计刚授权网易云社区发布。

    欢迎访问网易云社区,了解更多网易技术产品运营经验。


    4、get(Object key)

    使用方法:

    map.get("hello");

    源代码:

     ConcurrentHashMap的get(Object key)

        /**
         * 根据key获取value
         * 步骤:
         * 1)根据key获取hash值
         * 2)根据hash值找到相应的Segment
         * 调用Segment的get(Object key, int hash)
         * 3)根据hash值找出HashEntry数组中的索引index,并返回HashEntry[index]
         * 4)遍历整个HashEntry[index]链表,找出hash和key与给定参数相等的HashEntry,例如e,
         * 4.1)如没找到e,返回null
         * 4.2)如找到e,获取e.value
         * 4.2.1)如果e.value!=null,直接返回
         * 4.2.2)如果e.value==null,则先加锁,等并发的put操作将value设置成功后,再返回value值
         */
        public V get(Object key) {
            int hash = hash(key.hashCode());
            return segmentFor(hash).get(key, hash);
        }

    Segment的get(Object key, int hash)

            /**
             * 根据key和hash值获取value
             */
            V get(Object key, int hash) {
                if (count != 0) { // read-volatile
                    HashEntry<K, V> e = getFirst(hash);//找到HashEntry[index]
                    while (e != null) {//遍历整个链表
                        if (e.hash == hash && key.equals(e.key)) {
                            V v = e.value;
                            if (v != null)
                                return v;
                            /*
                             * 如果V等于null,有可能是当下的这个HashEntry刚刚被创建,value属性还没有设置成功,
                             * 这时候我们读到是该HashEntry的value的默认值null,所以这里加锁,等待put结束后,返回value值
                             */
                            return readValueUnderLock(e); 
                        }
                        e = e.next;
                    }
                }
                return null;
            }

    Segment的getFirst(int hash)

            /**
             * 根据hash值找出HashEntry数组中的索引index,并返回HashEntry[index]
             */
            HashEntry<K, V> getFirst(int hash) {
                HashEntry<K, V>[] tab = table;
                return tab[hash & (tab.length - 1)];
            }

    Segment的readValueUnderLock(HashEntry<K, V> e)

            V readValueUnderLock(HashEntry<K, V> e) {
                lock();
                try {
                    return e.value;
                } finally {
                    unlock();
                }
            }

    注意点:

     

    • 注释很重要,一定要看

    • 注释已经写明了详细流程,这里说一下大致流程:

      • 如没找到e,返回null

      • 如找到e,获取e.value

      • 如果e.value!=null,直接返回

      • 如果e.value==null,则先加锁,等并发的put操作将value设置成功后,再返回value值

      • 根据key获取hash值

      • 根据hash值找到相应的Segment

      • 根据hash值找出Segment中的哪一个HashEntry[index]

      • 遍历整个HashEntry[index]链表,找出hash和key与给定参数相等的HashEntry,例如e

    • 对于get操作而言,基本没有锁,只有当找到了e且e.value等于null,有可能是当下的这个HashEntry刚刚被创建,value属性还没有设置成功,这时候我们读到是该HashEntry的value的默认值null,所以这里加锁,等待put结束后,返回value值

    • 据说,上边这一点还没有发生过

     

    5、remove(Object key)

    使用方法:

    map.remove("hello");

    源代码:

    ConcurrentHashMap的remove(Object key)

        /**
         * 删除指定key的元素
         * 步骤:
         * 1)根据key获取hash值
         * 2)根据hash值获取Segment
         * 调用Segment的remove(Object key, int hash, Object value)
         * 1)count-1
         * 2)获取将要删除的元素所在的HashEntry[index]
         * 3)遍历链表,
         * 3.1)若没有hash和key都与指定参数相同的节点e,返回null
         * 3.2)若有e,删除指定节点e,并将e之前的节点重新排序后,将排序后的最后一个节点的下一个节点指定为e的下一个节点
         * (很绕,不知道JDK为什么这样实现)
         */
        public V remove(Object key) {
            int hash = hash(key.hashCode());
            return segmentFor(hash).remove(key, hash, null);
        }

    Segment的remove(Object key, int hash, Object value)

            V remove(Object key, int hash, Object value) {
                lock();
                try {
                    int c = count - 1;//key-value对个数-1
                    HashEntry<K, V>[] tab = table;
                    int index = hash & (tab.length - 1);
                    HashEntry<K, V> first = tab[index];//获取将要删除的元素所在的HashEntry[index]
                    HashEntry<K, V> e = first;
                    //从头节点遍历到最后,若未找到相关的HashEntry,e==null,否则,有
                    while (e != null && (e.hash != hash || !key.equals(e.key)))
                        e = e.next;
    
                    V oldValue = null;
                    if (e != null) {//将要删除的节点e
                        V v = e.value;
                        if (value == null || value.equals(v)) {
                            oldValue = v;
                            // All entries following removed node can stay
                            // in list, but all preceding ones need to be
                            // cloned.
                            ++modCount;
                            HashEntry<K, V> newFirst = e.next;
                            /*
                             * 从头结点遍历到e节点,这里将e节点删除了,但是删除节点e的前边的节点会倒序
                             * eg.原本的顺序:E3-->E2-->E1-->E0,删除E1节点后的顺序为:E2-->E3-->E0
                             * E1前的节点倒序排列了
                             */
                            for (HashEntry<K, V> p = first; p != e; p = p.next)
                                newFirst = new HashEntry<K, V>(p.key, p.hash, newFirst, p.value);
                            tab[index] = newFirst;
                            count = c; // write-volatile
                        }
                    }
                    return oldValue;
                } finally {
                    unlock();
                }
            }

    注意:具体的实现方式看注释,个人感觉比较绕,所以有兴趣的朋友可以按照如下步骤实现了一遍:(实现的过程可以参照HashMap的remove(Object key))

    • 根据key获取hash值

    • 根据hash值获取Segment

    • 获取将要删除的元素所在的HashEntry[index]

    • 遍历链表

      • 若没有hash和key都与指定参数相同的节点e,返回null

      • 若有e,删除指定节点e,并将e的前一个节点的next指向e的下一个节点,之后count-1

     

    6、containsKey(Object key)

    使用方法:

    map.containsKey("hello")

    源代码:

     ConcurrentHashMap的containsKey(Object key)

        /**
         * 是否包含指定key的数据
         * 步骤:
         * 1)根据key计算hash值
         * 2)根据hash获取相应的Segment
         * 调用Segment的containsKey(Object key, int hash)
         * 3)根据hash值找出HashEntry数组中的索引index,并返回HashEntry[index]
         * 4)遍历整个HashEntry[index]链表,找出hash和key与给定参数相等的HashEntry,例如e,
         * 4.1)如找到e,返回true
         * 4.2)如没找到e,返回false
         */
        public boolean containsKey(Object key) {
            int hash = hash(key.hashCode());
            return segmentFor(hash).containsKey(key, hash);
        }

    Segment的containsKey(Object key, int hash)

            boolean containsKey(Object key, int hash) {
                if (count != 0) { // read-volatile
                    HashEntry<K, V> e = getFirst(hash);
                    while (e != null) {
                        if (e.hash == hash && key.equals(e.key))
                            return true;
                        e = e.next;
                    }
                }
                return false;
            }

    说明:代码清晰简单,流程步骤查看注释即可

     

    7、keySet().iterator()

    使用方法:

            Map<String, Object> map = new ConcurrentHashMap<String, Object>();
            map.put("hello3", "world2");
            map.put("hello2", "world");
            for(String key : map.keySet()){
                System.out.println(map.get(key));
            }

    源代码不写了。

    流程:

    遍历每个Segment中的HashEntry[],完成所有对象的读取,不加锁。

     

    8、size()

    源代码:

        /**
         * 计算map中的key-value对总数
         * 步骤:
         * 1)遍历所有段,计算总的count值sum,计算总的modCount值
         * 2)如果有数据的话(modCount!=0),再遍历所有段一遍,计算总的count值check,在这期间只要有一个段的modCount发生了变化,就再重复如上动作两次
         * 3)若三次后,还未成功,遍历所有Segment,分别加锁(即建立全局锁),然后计算,最后释放所有锁
         */
        public int size() {
            final Segment<K, V>[] segments = this.segments;
            long sum = 0;//总量
            long check = 0;//标志位
            int[] mc = new int[segments.length];//存放每个段的modCount
            
            
            for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
                check = 0;
                sum = 0;//总的count值
                int mcsum = 0;//总的modCount值
                for (int i = 0; i < segments.length; ++i) {//遍历所有段
                    sum += segments[i].count;//计算总的count值
                    mcsum += mc[i] = segments[i].modCount;//计算总的modCount值
                }
                if (mcsum != 0) {//有数据的话,再检查一遍
                    for (int i = 0; i < segments.length; ++i) {
                        check += segments[i].count;//计算总的count
                        if (mc[i] != segments[i].modCount) {//只要有一个段发生了变化(在遍历期间发生了增删变化)
                            check = -1; 
                            break;//跳出所有循环
                        }
                    }
                }
                if (check == sum)//成功
                    break;
            }
            if (check != sum) { //以上三次都为成功的话
                sum = 0;
                //每一个段全部加锁(相当于加了一个全局锁)
                for (int i = 0; i < segments.length; ++i)
                    segments[i].lock();
                //进行统计
                for (int i = 0; i < segments.length; ++i)
                    sum += segments[i].count;
                //全部解锁
                for (int i = 0; i < segments.length; ++i)
                    segments[i].unlock();
            }
            if (sum > Integer.MAX_VALUE)
                return Integer.MAX_VALUE;
            else
                return (int) sum;
        }

    在不加锁的情况下遍历所有Segment,读取每个Segment的count和modCount,并进行统计;

    完毕后,再遍历一遍所有Segment,比较modCount,是否发生了变化,若发生了变化,则再重复如上动作两次;

    若三次后,还未成功,遍历所有Segment,分别加锁(即建立全局锁),然后计算,最后释放所有锁。

    注:以如上的方式,大部分情况下,不需要加锁就可以获取size()

     

    总结:

    • 数据结构:一个指定个数的Segment数组,数组中的每一个元素Segment相当于一个HashTable

    • 加锁情况(分段锁):

      • put

      • get中找到了hash与key都与指定参数相同的HashEntry,但是value==null的情况

      • remove

      • size():三次尝试后,还未成功,遍历所有Segment,分别加锁(即建立全局锁)

    jdk1.8 concurrentHashMap的实现

    免费领取验证码、内容安全、短信发送、直播点播体验包及云服务器等套餐

    更多网易技术、产品、运营经验分享请点击

    相关文章:
    【推荐】 “网易大数据讲堂第一期:数说”直播活动资料:课程回放收看及PPT下载
    【推荐】 Hive中文注释乱码解决方案(2)
    【推荐】 聊聊WS-Federation

    相关文章

      网友评论

          本文标题:ConcurrentHashMap源码解析(3)

          本文链接:https://www.haomeiwen.com/subject/qvbekqtx.html