juc 下的集合之二 (ConcurrentHashMap)

一、基本思想

基于HASH表的并发map（map怎么翻译，感觉叫E文更加通用点吧）。有跟java.lang.HashMap一样的方法，但是每个方法都是线程安全的。

建议对HashMap了解之后再看这篇文章，关于HashMap本人之前写过一篇博客来说明

http://tangmingjie2009.iteye.com/blog/1698595

二、源码解析

2.1 基本常量

 /**
     * The default initial capacity for this table,
     * used when not otherwise specified in a constructor.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    //默认初始化容量
    /**
     * The default load factor for this table, used when not
     * otherwise specified in a constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //可以理解为容量百分比的一个阈值
    /**
     * The default concurrency level for this table, used when not
     * otherwise specified in a constructor.
     */
    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;
    //最大容量
    /**
     * 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;
    //最小段容量
    /**
     * 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
    //最大段
    /**
     * 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;
    //上锁前的重试次数

 2.2 内部类

类中有三个内部类

private static class Holder;
//JVM 启动的时候加载jdk.map.althashing.threshold值
static final class HashEntry<K,V>;
//永远不被暴露出去的Key value实体
static final class Segment<K,V> extends ReentrantLock implements Serializable;
//将ReentrantLock 和Entry<K,V>结合到一起的东西

 2.3 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;
    }

这个比较简单，因为不牵涉到节点的删除，如果把下面的put看懂之后，理解就更加容易些了。

 

2.4 put

 public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)//值不为空
            throw new NullPointerException();
        int hash = hash(key);//获得hashCode
        int j = (hash >>> segmentShift) & segmentMask; 
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);//根据key的hash值计算看是否有个节点，如果没有就创建一个
        return s.put(key, hash, value, false);//将key,value放入这个节点中
    }

要知道segmentShift 和segmentMash 可以从构造方法来看

 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;
        this.segmentMask = ssize - 1;
        。。。。。。后面省略

 按照无参的构造方法来看的话，三个值分别是16,0.75,16，这样如果算下来segmentShift=28，segmentMask=15。

那么它是怎么存放的呢，看下面的方法，这里有重入锁的概念了

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;
                int index = (tab.length - 1) & hash;
                HashEntry<K,V> first = entryAt(tab, index);//找到所在位置，然后就进行赋值
                                 //如果发现要超出容量的阈值了扩容后重新计算一遍
                for (HashEntry<K,V> e = first;;) {
                    if (e != null) {
                        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);
                        else
                            setEntryAt(tab, index, node);
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                unlock();
            }
            return oldValue;
        }

 

2.5 遍历

通过迭代器来实现遍历的，对于所有的map来说通常都是这样

Iterator<Entry<Integer, String>> iterator = map.entrySet().iterator();
		while(iterator.hasNext()){
		    Entry<Integer, String> next = iterator.next();
		    next.getKey();
		    next.getValue();
		}

 

 

 

三、适用范围

源代码的文档的解释：

        这个类和它的视图和迭代器实现了所有的Map 和Interator的接口。相比较而言更像HashTable而不想HashMap,因为它不允许空值作为key和value.

个人理解:

        多线程编程中非常常用的一个类。不会出现HashMap中ConcurrentModificationException。可以不加锁的情况下放心使用。

四、测试