一、ConcurrentHashMap数据结构

image.png

二、ConHashMap关键属性介绍

//默认初始数组的开辟空间
//通过(CAPCITY/LEVEL)<<1 即:(16/16)<<1的到2为默认Segment中HashEntry[] table 默认长度
static final int DEFAULT_INITIAL_CAPACITY = 16;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认并发级别，也是默认Segment[] segments数组的长度
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//最大扩展空间
static final int MAXIMUM_CAPACITY = 1 << 30;
//Segment中table数组的最小长度
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
//Segment[] segments的最大长度
static final int MAX_SEGMENTS = 1 << 16;
//Segment数组
 final Segment<K,V>[] segments;

三、Segment对象中的关键属性介绍 segment和HashMap对象类似

//Segment本身继承了锁本身就是锁
static final class Segment<K,V> extends ReentrantLock implements Serializable {
   /**分段表。通过以下方式访问元素
 entryAt/setEntryAt提供volatile语义 
 */
transient volatile HashEntry<K,V>[] table;
/*元素的数量*/
transient int count;
/**
 此段中变化操作的总数。
即使这可能溢出32位，它提供
对CHM isEmpty()的稳定性检查有足够的准确性
和size()方法。只能在锁或
在其他保持可见性的volatile读操作中。
 */
transient int modCount;

/**
当表的大小超过这个阈值时，会重新散列。
这个字段的值总是<tt>(int)(capacity *)
*负载系数)< / tt >)
即:扩展临界值
 */
transient int threshold;

/**
*哈希表的装载因子。尽管这个值
*对于所有段都是相同的，它被复制以避免需要
*到外部对象的链接。
 */
final float loadFactor;
}

四、ConHashMap构造器简单介绍

/*
DEFAULT_INITIAL_CAPACITY:默认初始数组的开辟空间16用来计算
每个Segment中HashEntry[] table的容量
DEFAULT_LOAD_FACTOR：默认加载因子：0.75f
DEFAULT_CONCURRENCY_LEVEL:默认并发级别：就是segement数组的默认容量

*/
public ConcurrentHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

/*
构造器中做了什么？
1.计算segements数组的长度
2.计算segment[i]中HashEntry[]数组长度
3.创建一个sement对象
  s0=new Segment(loadFactor, (int)(cap * loadFactor),(HashEntry<K,V>[])new HashEntry[cap])
4.创建segments数组ss
5.把创建的s0对象放入到数组ss的第一个位置ss[0]
6.当前segments=ss
思考：为什么会先创建一个s0对象放入到ss[0]?
因为在put元素时，如果计算出来的segment下标i中为null，可以复用s0的属性的初始值。
*/
 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;
        //通过这个运算后可以得到一个大于等于concurrencyLevel的2的幂次方数ssize
        //ssize:就是segment数组的长度
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        this.segmentShift = 32 - sshift;
        //算数组下标时需要使用
        this.segmentMask = ssize - 1;
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //计算每个segment中HashEntry数组的长度，最终计算出长度至少为2    
        int c = initialCapacity / ssize; 
        if (c * ssize < initialCapacity)
            ++c;
        int cap = MIN_SEGMENT_TABLE_CAPACITY;//值为2
        //最终计算出一个2的幂次方数作为HshEntry数组的长度。
        while (cap < c)
            cap <<= 1;
        // 创建一个segment对象放到segments[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);              
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        //赋值给当前对象的segment的属性
        this.segments = ss;
    }

五、ConHashMap的put方法

/*
     1.判断value是否为null，如果为null抛异常
     2.根据key计算hash值
     3.根据hash值和segements数组长度计算数组segment数组下标
     4.获取segments[index] 如果为空，通过UNSAFE方法创建
     5.调用segments[index]的put方法put值。
     */
     public V put(K key, V value) {
        Segment<K,V> s;
        //value不能为null，会抛异常
        if (value == null)
            throw new NullPointerException();
        //根据key获取hash值  
        int hash = hash(key);
        //根据hash值的高位计算segments数组下标
        int j = (hash >>> segmentShift) & segmentMask;
        //判断segment[j]是否是null，如果是null就会创建一个segment对象放入到segment[j]
        //通过UNSAFE方法直接操作共享区内存，而不是线程工作内存。
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        //调用segment[j]的put方法
        return s.put(key, hash, value, false);
    }

六、ensureSegment方法通过UNSAFE获取Segment对象

 /*
     生成一个segment对象
     这里都是用UNSAFE方法进行直接操作共享内存。
     保证立即可见。
     1.从共享内存中获取Segment对象，如果过去成功，直接诶返回
     2.如果没有获取成功，创建Segment对象，并通过CAS设置到segments[index]中.
     */
     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
            int cap = proto.table.length;
            float lf = proto.loadFactor;
            int threshold = (int)(cap * lf);
            HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
            //重新检查是否已经存在了Segment对象，双重检查
            if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                == null) { // recheck
                Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
                //自旋检查是否已存在，不存在用过cas设置
                while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                       == null) {
                    if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                        break;
                }
            }
        }
        return seg;
    }

七、Segment中的put方法，真正put HashEntry元素

/*
    Segment中的put方法
    1.尝试获取锁，如果获取到了进入到下面的流程
      如果第一次没获取到，就会循环尝试获取锁，在尝试获取锁的过程中根据当前key和value创建一个HashEntry node
    2.根据hash和table数组长度计算要插入的table的数组下标index
    3.获取table[index]中的头元素
    4.从头元素开始循环遍历查询key是否在链表中已经存在，如果存在更新最新的value
    5.如果不存在key，根据头插法，用UNSAFE方法插入到table[index]中
    */
     final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            //加锁并创建一个键值对对象
            //逻辑是：tryLock成功node=null,tryLock不成功会调用 scanAndLockForPut
            HashEntry<K,V> node = tryLock() ? null :scanAndLockForPut(key, hash, value);
            V oldValue;
            try {
                HashEntry<K,V>[] tab = table;
                //根据hash值的低位，计算table的数组下标
                int index = (tab.length - 1) & hash;
                //根据数组下标获取table[index]中的头元素
                HashEntry<K,V> first = entryAt(tab, index);
                //根据头元素往下遍历，查询是否已经存在当前key，如果存在
                //更新为当前最新的value
                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;
                            //concurrenthashmap中存在putIfAbsent()方法
                            //如果调用该方法就会设置onlyIfAbsent=true
                            //意思是如果已存在key，什么都不做
                            if (!onlyIfAbsent) {
                                //更新为最新的value
                                e.value = value;
                                ++modCount;
                            }
                            break;
                        }
                        e = e.next;
                    }
                    //table[index]为null或者循环完成之后不存在key
                    //把新增的node根据头插法插入到table数组中
                    else {
                        if (node != null)
                            //把头元素设置为当前元素的下一个元素
                            node.setNext(first);
                        else
                            //
                            node = new HashEntry<K,V>(hash, key, value, first);
                        int c = count + 1;
                        //判断table扩容的条件 
                        //count当前SegmentHashEntry元素的数量.
                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                            //扩容代码
                            rehash(node);
                        else
                            //通过UNSAFE设置table[index]=node
                            setEntryAt(tab, index, node);
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                unlock();
            }
            return oldValue;
        }

八、Segment中scanAndLockForPut尝试获取锁，并在尝试获取锁时，组装需要插入的HashEntry元素

 /*
     1.获取头结点
     2.while循环尝试获取锁，在尝试获取锁的同时做了一些事情：
       循环尝试创建node= new HashEntry<K,V>(hash, key, value, null);
     3.循环达到一定的次数后，会lock，退出。
     这个方法的巧妙之处是，不是立马进行lock，而是不停的trylock(),trylock
     是不会阻塞的，所以在trylock的过程中可以先把创建node需要的元素创建出来
     这样会提高代码的效率。
     */  
     private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
            //根据hash和this(当前segment对象).table的长度算出key的数组下标
            //获取头节点segment.table[index]         
            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;
                    }
                    //如果已经包含了key，就进行new了
                    else if (key.equals(e.key))
                        retries = 0;
                    else
                        e = e.next;
                }
                //达到最大重试次数后不在尝试获取锁，直接调用lock锁住
                //cpu核心数大于1就是64次，否则就是1次
                //MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
                else if (++retries > MAX_SCAN_RETRIES) {
                    lock();
                    break;
                }
                else if ((retries & 1) == 0 //偶数次
                      //根据hash和table.lenth再次获取table[index]的头结点
                      //判断和当前拿到的头结点是不是一样，如果不一样说明有线程已经
                      //通过头插法插入了新的node，把first赋值为最新拿到的table[index]的头结点
                      //把retries = -1，会再次进入while循环重新走逻辑。
                      &&(f = entryForHash(this, hash)) != first) {
                    e = first = f; // re-traverse if entry changed
                    retries = -1;
                }
            }
            return node;
        }

九、Segment中的rehash 进行table数组扩容

/*
        数组扩容:就是Segment对象里面 HashEntry[] table的长度扩容
        素组扩容的条件是：当所有Segment对象中所有HashEntry[]所有的HashEntry之和
        count>扩展临界值length,并且当前Segment对象中table.length的长度小于MAXIMUM_CAPACITY = 1 << 30
        扩容的新数组长度老数组长度的2倍
        */
         private void rehash(HashEntry<K,V> node) {
            HashEntry<K,V>[] oldTable = table;
            int oldCapacity = oldTable.length;
            //扩容的新数组长度老数组长度的2倍
            int newCapacity = oldCapacity << 1;
            //重新计算扩展临界值
            threshold = (int)(newCapacity * loadFactor);
            //创建新数组
            HashEntry<K,V>[] newTable =(HashEntry<K,V>[]) new HashEntry[newCapacity];
            //2的幂次方数-1 低位为1的特性，用来计算数组下标
            int sizeMask = newCapacity - 1;
            //遍历老数组
            for (int i = 0; i < oldCapacity ; i++) {
                //获取老数组某个元素的头节点e
                HashEntry<K,V> e = oldTable[i];
                if (e != null) {
                    HashEntry<K,V> next = e.next;
                    //重新获取新的数组下标
                    int idx = e.hash & sizeMask;
                    if (next == null)   //  证明该链表只有一个元素，新数组下标直接指向该HashEntry元素。
                        newTable[idx] = e;
                    else { // Reuse consecutive sequence at same slot
                        HashEntry<K,V> lastRun = e;
                        int lastIdx = idx;
                        /*这个循环，是从第二个元素开始循环，每循环一次会判断新计算的数组
下标与astIdx是否相等，如果相等不做任何操作，如果不等，
会把lastIdx更新为新计算的数组下标k当次循环计算出来的新数组下标。
并记录这个元素循环结束后最终会记录:
最后几个新计算的数组下标相等的连续节点的头节点（他们的next指针没有变化）
把lastRun作为新数组的某个数组元素的头节点newTable[lastIdx] = lastRun;
这样就可能一次转移一批节点会提高转移的效率*/
                        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] = lastRun;
                        // 这里只会循环lastRun之前的元素重新一个一个重新算下标
                        //利用头插法往新数组中插入元素。
                        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);
                        }
                    }
                }
            }
            //当前这次需要插入的HashEntry重新计算数组下标
            //利用头插法插入新数组中。
            int nodeIndex = node.hash & sizeMask; 
            node.setNext(newTable[nodeIndex]);
            newTable[nodeIndex] = node;
            table = newTable;
        }
   

十、ConHashMap中get方法

/**
   根据UNSAFE直接从共享内存中获取最新的value
   */
   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;
    }