欢迎光临
我们一起进阶

Java并发编程(十九):ConcurrentHashMap

扫码或搜索:沉默王二
发送 290992
即可立即永久解锁本站全部文章

java多线程高级-concurrentHashMap

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组,一个Sement由若干个HashEntry对象组成的数组。Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶,每个桶是由若干个 HashEntry 对象链接起来的链表;HashEntry 用来封装映射表的键 / 值对。
结构图如下:

分段锁设计

先来看一下Hashtable的线程安全设计

现在索引3,4,8被三个线程操作着,他们同时需要put数据时,需要竞争同一把锁,这个时候只允许一个线程插入操作,另外一个2线程则等待。不管他们的key对应的索引值是否一样,他们都会产生互斥,只有一个线程能做插入操作,另外一个线程必须得等待。

再来看看CMP的设计。

现在索引0,5,11被线程1,2,3同时操作,他们同时插入put数据时,由于加锁是在HashEntry里面做的,1,2,3线程并不会产生互斥,他们可以同时进行,互不影响。只有当多个线程同时操作同一个索引值的时候他们才会产生互斥,才会加锁。比如线程1,2同时操作索引0进行put操作。

concurrentHashMap源码jkd1.7

先来看看有哪些成员变量

    // 散列映射表的默认初始容量为 16,即初始默认为 16 个桶,在构造函数中没有指定这个参数时,使用本参数
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /** 
    * 散列映射表的默认装载因子为 0.75,该值是 table 中包含的 HashEntry 元素的个数与
* table 数组长度的比值
    * 当 table 中包含的 HashEntry 元素的个数超过了 table 数组的长度与装载因子的乘积时,
* 将触发 再散列
    * 在构造函数中没有指定这个参数时,使用本参数
    */ 
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /** 
    * 散列表的默认并发级别为 16。该值表示当前更新线程的估计数
    * 在构造函数中没有指定这个参数时,使用本参数.
    * 和DEFAULT_INITIAL_CAPACITY这个默认的桶数息息相关后面会讲哦!
    */ 
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    /**
     * The maximum capacity, used if a higher value is implicitly
     * specified by either of the constructors with arguments.  MUST
     * be a power of two <= 1<<30 to ensure that entries are indexable
     * using ints.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
      默认的一个HashEntry[]数组长度为2
    */
    static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

    //英文写的很清楚啦,就是segments数组的最大长度为2的16次方
    /**
     * The maximum number of segments to allow; used to bound
     * constructor arguments. Must be power of two less than 1 << 24.
     */
    static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

   //获取size时的一个重试次数默认值
    /**
     * 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;

    /** 
    * segments 的掩码值
    * key 的散列码的高位用来选择具体的 segment 
    */ 
    final int segmentMask;

    /** 
    * 偏移量
    */ 
    final int segmentShift;

    /** 
    * 由 Segment 对象组成的数组
    */ 
    final Segment<K,V>[] segments;

初始化

//初始化ConcurrentHashMap的时候会先初始化静态方法哦!
//求key的hash值的时候使用到哦!
private transient final int hashSeed = randomHashSeed(this);

    private static int randomHashSeed(ConcurrentHashMap instance) {
        if (sun.misc.VM.isBooted() && Holder.ALTERNATIVE_HASHING) {
            return sun.misc.Hashing.randomHashSeed(instance);
        }

        return 0;
    }

//默认值为16,0.75f,16
public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;    
        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        this.segmentShift = 32 - sshift; //sshift=4 //偏移量值
        this.segmentMask = ssize - 1; //ssize=16 
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        int c = initialCapacity / ssize;   
        if (c * ssize < initialCapacity)
            ++c;
        int cap = MIN_SEGMENT_TABLE_CAPACITY; //设置HashEntry数组的大小
        while (cap < c)
            cap <<= 1;
        // create segments and segments[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);//创建了一个segment,这个里面包含了一个HashEntry[],数组长度为2.
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];//初始化Segment数组
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

注意:Segment这个数组是不会在元素增加时候自动扩充一倍哦!一旦初始化后Segment数组长度就不变了。之后自动扩展的是HashEntry数组哦!
Segment这个其实使用来做分段锁的,所以它的数组长度设置的和评估线程并发数相关。我们在手动设置大小的时候不用乱设置,也不用设置过大,不然反而影响了本来的性能。

HashEntry

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        /**
         * Sets next field with volatile write semantics.  (See above
         * about use of putOrderedObject.)
         */
        final void setNext(HashEntry<K,V> n) {
            UNSAFE.putOrderedObject(this, nextOffset, n);
        }

        // Unsafe mechanics
        static final sun.misc.Unsafe UNSAFE;
        static final long nextOffset;
        static {
            try {
                UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class k = HashEntry.class;
                nextOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("next"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }
    }

put方法

public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key); 
        int j = (hash >>> segmentShift) & segmentMask;
        //计算key值应该被分派到segments的哪个下标下(j << SSHIFT) + SBASE
        //查找segments[i]是否=null,如果为null则初始化它。
        if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        return s.put(key, hash, value, false);
}


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;
        //再次检查是否为null
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
           //记得前面的初始化吗?this.segments数组的第0个元素里面的segment也被初始化了一个HashEntry数组哦!,这里相当于参照第0个的参数创建第u个
            Segment<K,V> proto = ss[0]; // use segment 0 as prototype
            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
                Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
                //再次检查
                while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))== null) {
                    //把s添加到segments数组中的u位置
                    if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                        break;
                }
            }
        }
        return seg;
}

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            //尝试能否获取锁,获取到锁后往下执行
            HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);
            V oldValue;
            try {
                HashEntry<K,V>[] tab = table;
                //hash值与数组长度-1做与运算,计算数组的下标值
                int index = (tab.length - 1) & hash;
                //直接操作内存的方式,获取tab数组中的index元素
                HashEntry<K,V> first = entryAt(tab, index);
                for (HashEntry<K,V> e = first;;) {
                    if (e != null) {
                        K k;
                        //如果key相同,则新值覆盖老值
                        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);
                        else
                            setEntryAt(tab, index, node);//添加node到数组的第index下面
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                unlock();
            }
            return oldValue;
        }

 static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
        return (tab == null) ? null :
            (HashEntry<K,V>) UNSAFE.getObjectVolatile
            (tab, ((long)i << TSHIFT) + TBASE);
    }

//查看CPU的线程数,如果大于1则返回64
static final int MAX_SCAN_RETRIES =  Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;    
//没有获取到锁后,开始加锁,进入锁队列    
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;
                }
                //尝试次数为线程所允许的最大值,多核下最多尝试64次
                //一直没有获取到锁后,则调用lock,lock里面是能否获取锁,如果不能则进入阻塞队列,线程挂起。
                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;
        }           

解说:

  • 可以看到ensureSegment里面在实例化一个Segment使用了无锁实现的吗?里面使用UNSAFE.compareAndSwapObject不断重试的去把Segment添加到数组中。
    而在此之前也不断的判断是否为null,这个就是在多线程下也是安全的无锁实现的一个版本啦!不然的话要加锁哦!

  • 可以看到在put时,scanAndLockForPut这个方法里面也是在不断自旋,不断尝试能否获取锁,如果超过设置的阀值后,还不能获取锁,才开始加锁,进入阻塞队列,线程挂起。

rehash扩展数组

private void rehash(HashEntry<K,V> node) {
            //获取老表
            HashEntry<K,V>[] oldTable = table;
            int oldCapacity = oldTable.length;
            //新表在老表基础上扩展一倍
            int newCapacity = oldCapacity << 1;
            threshold = (int)(newCapacity * loadFactor);
            //创建一个新数组
            HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
            int sizeMask = newCapacity - 1;
            for (int i = 0; i < oldCapacity ; i++) {
                HashEntry<K,V> e = oldTable[i];
                if (e != null) {
                    HashEntry<K,V> next = e.next;
                    int idx = e.hash & sizeMask;
                    if (next == null)   //  Single node on list
                        newTable[idx] = e;
                    else { // Reuse consecutive sequence at same slot
                        HashEntry<K,V> lastRun = e;
                        int lastIdx = idx;
                        //遍历找到链表的最后一个节点,
                        //防止类似HashMap那种扩容时产生循环链表。
                        for (HashEntry<K,V> last = next;
                             last != null;
                             last = last.next) {
                            int k = last.hash & sizeMask;
                            if (k != lastIdx) {
                                lastIdx = k;
                                lastRun = last;
                            }
                        }
                        //把新的newTable数组的第lastIdx指向最后一个数组
                        newTable[lastIdx] = lastRun;
                        // Clone remaining nodes:克隆剩余节点
                        //这里使用拷贝,主要是为了get做铺垫,因为get是没有加锁的,如果在扩容时调用get方法获取元素就会有问题,所以这里使用克隆
                        //这样老数组里面的节点不变,新表重新建立。
                        for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                            V v = p.value;
                            int h = p.hash;
                            int k = h & sizeMask;
                            HashEntry<K,V> n = newTable[k];
                            newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                        }
                    }
                }
            }
            int nodeIndex = node.hash & sizeMask; // add the new node
            node.setNext(newTable[nodeIndex]);
            newTable[nodeIndex] = node;
            table = newTable;
        }

这里的扩容和HashMap不太一样哦!concurrentHashMap的扩容,是先找到最后链表的最后一个节点把新表的引用指向了它,然后把链表的其他节点给克隆过来(不是引用)。

HashMap里面是把老表的链表里面的元素的引用赋值过来,而CHM是把链表的最后一个元素的引用赋值给数组,然后其他元素克隆。
这样做的好处是:

  1. 防止类似HashMap那种扩容时产生循环链表。
  2. 新表不是简单的把引用赋值,而是直接克隆,主要是为了get做铺垫,因为get是没有加锁的,如果在扩容时调用get方法获取元素就会有问题,而现在使用克隆的情况,老数组里面的节点不变,新表重新建立。
  3. 扩容的时候链表是这样的A->B->C->null,扩容后B1-A1-C->null,扩容的时候同样会反转链表,只不过最后一个元素是引用且不反转,其他元素拷贝后反转。

get不加锁

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;
    }
  1. get方法里面没有加锁哦,它主要是通过UNSAFE.getObjectVolatile来获取的,UNSAFE.getObjectVolatile支持volatile load语义,而HashEntry数组里面的key,value都是volatile变量,这样就保证了其他线程修改数组值时对于get操作来说立即可见性。
  2. put中如果遇到扩容并不改变之前的数据,而是拷贝一份出来。

get弱一致性

先看下图什么意思?

线程1,2同时操作,线程1做了put操作,线程2做了get操作这个时候在concurrentHashMap里面是弱一致性的。什么意思呢?

线程1压入put(‘k’,3)操作,加锁了,防止其他线程的修改。但是这个时候get(‘k’)并没有加锁,线程2可以立即执行get操作,那么线程2可以立即获取到值吗?答案是不能,虽然value添加了volatile属性表示了value的可见性,但是如果put刚操作到图中1的地方,get是获取到的是null;那么加了volatile有毛用?有用,如果不加volatile那么线程2必须得等到线程1执行了unlocak之后线程2才能获取到值,现在加了volatile,那么线程1执行完tar[i]=addEntry(Node n)线程2就可以立马获取到值了。

Hashtable里面不管get,put都是加的锁。

同样的事,线程1做put操作,线程2做get操作,线程1做put操作的时候,图中1,2地方,线程2都必须等待线程1执行完毕然后才能继续get操作。

但也有get到null的情况,就是get操作先行了,put操作慢了一点,那么put操作是没发做的,只能等待get返回为null后才能继续put。

ConcurrentMap和Hashtable他们的get都可能获取到null值,那么他们的区别在哪里呢?就在图1的地方,cmp已经put操作加锁了, 但是程序才执行到图中1的地方,这个时候get肯定为null啊,按代码逻辑来说,put已经操作了,那么get就能获取到值,对于ht来说是这样的,但是对于cmp来说却不是这样的。所以ht是一个是强一致的要么get都为null,要么get都有值;但是对于cmp来说却是不一致的,如果get正好到了图的地方则为null,到了1之后则不为null。

remove加锁删除

final V remove(Object key, int hash, Object value) {
            if (!tryLock())
                scanAndLock(key, hash);
            V oldValue = null;
            try {
                HashEntry<K,V>[] tab = table;
                int index = (tab.length - 1) & hash;
                HashEntry<K,V> e = entryAt(tab, index);
                HashEntry<K,V> pred = null;
                while (e != null) {
                    K k;
                    HashEntry<K,V> next = e.next;
                    if ((k = e.key) == key ||
                        (e.hash == hash && key.equals(k))) {
                        V v = e.value;
                        if (value == null || value == v || value.equals(v)) {
                           //删除数组中链表的第一个元素,直接把数组指向下一个节点就OK了。
                            if (pred == null)
                                setEntryAt(tab, index, next);
                            else
                                pred.setNext(next);//删除元素,直接把上一个节点删除节点的下一个节点,就OK了
                            ++modCount;
                            --count;
                            oldValue = v;
                        }
                        break;
                    }
                    pred = e;
                    e = next;
                }
            } finally {
                unlock();
            }
            return oldValue;
}


//先自旋,达到最大自旋值时,然后开始加锁。
private void scanAndLock(Object key, int hash) {
            // similar to but simpler than scanAndLockForPut
            HashEntry<K,V> first = entryForHash(this, hash);
            HashEntry<K,V> e = first;
            int retries = -1;
            while (!tryLock()) {
                HashEntry<K,V> f;
                // 如果“遍历完该HashEntry链表,仍然没找到”要删除的键值对“对应的节点”
            // 或者“在该HashEntry链表上找到”要删除的键值对“对应的节点”,则设置retries=0
            // 否则,设置e为下一个HashEntry节点。
                if (retries < 0) {
                    if (e == null || key.equals(e.key))
                        retries = 0;
                    else
                        e = e.next;
                }
                //自旋超过限制次数之后,加锁
                else if (++retries > MAX_SCAN_RETRIES) {
                    lock();
                    break;//加锁后,这一步就不会被执行了,等解锁后,直接跳出while就是啦!
                }
                // 当“尝试了偶数次”时,就获取“当前Segment的第一个HashEntry”,即f。
               // 然后,通过f!=first来判断“当前Segment的第一个HashEntry是否发生了改变”。
               // 若是的话,则重置e,first和retries的值,并重新遍历。
                else if ((retries & 1) == 0 &&
                         (f = entryForHash(this, hash)) != first) {
                    e = first = f;
                    retries = -1;
                }
            }
        }

版本的差异:

这里介绍的和网上好多的分析有不太一样的点,网上好多是1.6的分析,我这里是jdk1.7版本。

  1. 删除的时候是把原表的链表复制一份,然后去掉删除的节点。这里并不是,而是A->B->C->null,删除了B,则为A->C-null,并没有看到复制的操作。
  2. 扩容的时候链表是这样的A->B->C->null,扩容后B1-A1-C->null,扩容的时候同样会反转链表,只不过最后一个元素是引用且不反转,其他元素拷贝后反转。
赞(0) 打赏
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

小白学堂,学的不止是技术,更是前程

关于我们免责声明

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏