文档章节

ConcurrentHashMap 锁分段 源码分析

w
 wannshan
发布于 2017/04/10 17:38
字数 1274
阅读 30
收藏 1
点赞 0
评论 0

看ConcurrentHashMap下几个属性:

/**
     * The default concurrency level for this table, used when not
     * otherwise specified in a constructor.
     * 默认的分段锁个数
     */
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;

     /**
     * The minimum capacity for per-segment tables.  Must be a power
     * of two, at least two to avoid immediate resizing on next use
     * after lazy construction. 每个分段锁,最小容量
     */
    static final int MIN_SEGMENT_TABLE_CAPACITY = 2;


     /**
     * 尝试获取锁的次数
     * Number of unsynchronized retries in size and containsValue
     * methods before resorting to locking. This is used to avoid
     * unbounded retries if tables undergo continuous modification
     * which would make it impossible to obtain an accurate result.
     */
    static final int RETRIES_BEFORE_LOCK = 2;

    /**
     * The segments, each of which is a specialized hash table.
     * 分段锁数组 
     */
    final Segment<K,V>[] segments;

 

/**
     * Segments are specialized versions of hash tables.  This
     * Segments 也是一个定制的hashtable
     * subclasses from ReentrantLock opportunistically, just to
     * 同时他也是 ReentrantLock的子类
     * simplify some locking and avoid separate construction.
     */
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
    .....
    }
  //以put为例分析

 /**
     * Maps the specified key to the specified value in this table.
     * Neither the key nor the value can be null.
     * key 和 value 都不能为null 否则抛异常
     * <p> The value can be retrieved by calling the <tt>get</tt> method
     * with a key that is equal to the original key.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>
     * @throws NullPointerException if the specified key or value is null
     */
    @SuppressWarnings("unchecked")
    public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key);//先通过key求hash,再获取当前hash在哪个分段锁内,这些全是位操作,比较烦,也能分析透,还有UNSAFE类的使用比较多。UNSAFE是高危操作类,但是高效,功能强大。
        int j = (hash >>> segmentShift) & segmentMask;
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);//没找到合适分段,调用ensureSegment() 看下面,
        return s.put(key, hash, value, false);//调用的分段锁Segment的put方法
    }


    /**
     * Returns the segment for the given index, creating it and
     * recording in segment table (via CAS) if not already present.
     *  返回给定的索引的分段,不存在就创建一个。
     * @param k the index
     * @return the segment
     */
    @SuppressWarnings("unchecked")
    private Segment<K,V> ensureSegment(int k) {
        final Segment<K,V>[] ss = this.segments;
        long u = (k << SSHIFT) + SBASE; // raw offset
        Segment<K,V> seg;
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {//通过索引没取到分段,创建分段
            Segment<K,V> proto = ss[0]; // use segment 0 as prototype  //总是以ss[0]为例 这点写死了
            int cap = proto.table.length;
            float lf = proto.loadFactor;
            int threshold = (int)(cap * lf);
            HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
            if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                == null) { // recheck//再检查一次,有没有合适的分段
                Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);//创建分段
                while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                       == null) { //再检查一次,有没有合适的分段  第三次检查,
                    if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))//最后用cas方法,把新建的分段放到分段数组中
                        break;
                }
            }
        }
        return seg;
    }

    //  关键看下Segment类 
      /**
     * Segments are specialized versions of hash tables.  This 
     * subclasses from ReentrantLock opportunistically, just to
     * simplify some locking and avoid separate construction.
     * 它是ReentrantLock的子类
     */
      static final class Segment<K,V> extends ReentrantLock implements Serializable {}
	
     //看下Segment的put方法
      final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);//先用tryLock()获取锁,如果成功node=null ,否则进入scanAndLockForPut(key, hash, value)方法,看下面scanAndLockForPut方法
            V oldValue;
            try {
                HashEntry<K,V>[] tab = table;
                int index = (tab.length - 1) & hash;
                HashEntry<K,V> first = entryAt(tab, index);
                for (HashEntry<K,V> e = first;;) {
                    if (e != null) {//key 的hash位置有值了
                        K k;
                        if ((k = e.key) == key ||
                            (e.hash == hash && key.equals(k))) {
                            oldValue = e.value;
                            if (!onlyIfAbsent) {
                                e.value = value;
                                ++modCount;
                            }
                            break;
                        }
                        e = e.next;
                    }
                    else {
                        if (node != null)
                            node.setNext(first);
                        else
                            node = new HashEntry<K,V>(hash, key, value, first);
                        int c = count + 1;
                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                            rehash(node);//扩容 *2的大小
                        else
                            setEntryAt(tab, index, node);。
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                unlock();//释放锁
            }
            return oldValue;
        }


	  /**
         * Scans for a node containing given key while trying to
         * acquire lock, creating and returning one if not found. Upon
         * return, guarantees that lock is held. UNlike in most
         * methods, calls to method equals are not screened: Since
         * traversal speed doesn't matter, we might as well help warm
         * up the associated code and accesses as well.
         *  通过key找对应node.没有就创建一个。
         * @return a new node if key not found, else null
         */
        private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
            HashEntry<K,V> first = entryForHash(this, hash);
            HashEntry<K,V> e = first;
            HashEntry<K,V> node = null;
            int retries = -1; // negative while locating node
            while (!tryLock()) {//没有获取锁,重试
                HashEntry<K,V> f; // to recheck first below
                if (retries < 0) {
                    if (e == null) {
                        if (node == null) // speculatively create node
                            node = new HashEntry<K,V>(hash, key, value, null);
                        retries = 0;
                    }
                    else if (key.equals(e.key))
                        retries = 0;
                    else
                        e = e.next;
                }
                else if (++retries > MAX_SCAN_RETRIES) {//大于最大尝试次数
                    lock();//等待,阻塞锁
                    break;
                }
                else if ((retries & 1) == 0 &&
                         (f = entryForHash(this, hash)) != first) {
                    e = first = f; // re-traverse if entry changed
                    retries = -1;
                }
            }
            return node;
        }

     /**  get 方法不加锁
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code key.equals(k)},
     * then this method returns {@code v}; otherwise it returns
     * {@code null}.  (There can be at most one such mapping.)
     *
     * @throws NullPointerException if the specified key is null
     */
    public V get(Object key) {
        Segment<K,V> s; // manually integrate access methods to reduce overhead
        HashEntry<K,V>[] tab;
        int h = hash(key);
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
            (tab = s.table) != null) {
            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
                 e != null; e = e.next) {
                K k;
                if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                    return e.value;
            }
        }
        return null;
    }

 

© 著作权归作者所有

共有 人打赏支持
w
粉丝 16
博文 39
码字总数 79122
作品 0
浦东
技术主管
ConcurrentHashMap源码分析

前言 JDK中的Hashtable是一个线程安全的K-V形式的容器,它实现线程安全的原理十分简单,就是在所有涉及对该哈希表操作的方法上都加上了synchronized关键字,进行加锁操作。这么做实现了线程安...

Justlearn ⋅ 2017/04/13 ⋅ 0

探究Java的ConcurrentHashMap实现机制

原文地址: http://blog.csdn.net/u011080472/article/details/51392712 在学习ConcurrentHashMap的高并发时,找到了一些高质量的博客,就没有重复转载了。分别列出了JDK6中的Segment分段加锁...

Gavin__Zhou ⋅ 2017/08/06 ⋅ 0

ConcurrentHashMap源码跟踪记录

concurrentHashMap源码解读 主要理解几个问题1 ConcurrentHashMap如何实现分段锁2 存取数据是否读写分离 1 分段锁的实现 ①创建默认长度16的segments数组 ② put方法 1 从segments数组获取s...

xuklc ⋅ 03/26 ⋅ 0

并发十六:并发容器ConcurrentHashMap实现分析

J.U.C中实现Map接口的并容器有ConcurrentHashMap和ConcurrentSkipListMap。 ConcurrentHashMap ConcurrentHashMap是并发容器中锁分拆的一个经典设计。 ConcurrentHashMap 内部布局: Concur...

wangjie2016 ⋅ 04/14 ⋅ 0

Hashtable HashMap ConcurrentHashMap 源码分析

1.Hashtable与HashMap区别比较 先来说说这两者之间的不同: 1.Hashtable 是JDK1.2出现的, 父类继承Dictionary 实现的是Map, HashMap父类是AbstractMap实现的Map public class Hashtable exte...

陈小扁 ⋅ 2016/03/10 ⋅ 0

ConcurrentHashMap浅谈

1、实现原理介绍 ConcurrentHashMap采用分段锁的思想,将整个table分成不同的segment。每个Segment配有一个锁,这样每个段都能并行的做增删改查等功能。 2、ConcurrentHashMap在代码实现上有...

hyssop ⋅ 2016/02/02 ⋅ 0

ConcurrentHashMap总结

并发编程实践中,ConcurrentHashMap是一个经常被使用的数据结构,相比于Hashtable以及Collections.synchronizedMap(),ConcurrentHashMap在线程安全的基础上提供了更好的写并发能力,但同时降...

Hosee ⋅ 2016/05/16 ⋅ 6

从源码看concurrentHashMap的线程安全

从JDK1.2起,就有了HashMap,正如前一篇文章所说,HashMap不是线程安全的,因此多线程操作时需要格外小心。 在JDK1.5中,伟大的Doug Lea给我们带来了concurrent包,从此Map也有安全的了。 Co...

java一日一条 ⋅ 02/04 ⋅ 0

Java 并发实践 — ConcurrentHashMap 与 CAS

最近在做接口限流时涉及到了一个有意思问题,牵扯出了关于concurrentHashMap的一些用法,以及CAS的一些概念。限流算法很多,我主要就以最简单的计数器法来做引。先抽象化一下需求:统计每个接...

xrzs ⋅ 2012/10/07 ⋅ 0

并发编程(4)ConcurrentHashMap源码分析

概述 ConcurrentHashMap,通过这个名字,可以知道Concurrent是并发的,HashMap是我们常用的一种用来存放键值对的数据结构,所以ConcurrentHashMap就是一种用来解决高并发的HashMap。这个是JDK...

wustor ⋅ 2017/12/13 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

iExec Blockchain Marketplace for Cloud

iExec Releases the First-Ever Blockchain Marketplace for Trading Cloud Computing Berlin, Germany, May 29, 2018. iExec has released its blockchain-based decentralized cloud marke......

openthings ⋅ 28分钟前 ⋅ 0

OSChina 周二乱弹 —— 加班的代码不要枉费了我的童子功

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小小编辑:推荐歌曲《29》- 未完成乐队 《29》- 未完成乐队 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :#看球提醒# 02:00 巴西v...

小小编辑 ⋅ 47分钟前 ⋅ 13

Docker Swarm的前世今生

概述 在我的《Docker Swarm集群初探》一文中,我们实际体验了Docker Swarm容器集群技术的魅力,与《Kubernetes实践录》一文中提到的Kubernetes集群技术相比,Docker Swarm没有Kubernetes显得...

CodeSheep ⋅ 今天 ⋅ 0

骰子游戏代码开源地址

因为阿里云现在服务器已经停用了,所以上面的配置已经失效。 服务端开源地址:https://gitee.com/goalya/chat4.git 客户端开源地址:https://gitee.com/goalya/client4.git 具体运行界面请参考...

算法之名 ⋅ 今天 ⋅ 0

设计模式--装饰者模式

装饰者模式 定义 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比生成子类更为灵活。 通用类图 意图 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比...

gaob2001 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部