ConcurrentHashMap1.7 最最最最最详细源码分析

声明:本文只有源码分析注释,提供正在研究ConcurrentHashMap源码的同学参考!!!

1、内部结构:

ConcurrentHashMap1.7 最最最最最详细源码分析

2、Segment 分析

 static final class Segment<K,V> extends ReentrantLock implements Serializable {   	// 尝试获取锁最大次数,可以理解为自旋次数  	 static final int MAX_SCAN_RETRIES =             Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;   	 // 用来存放key-value对象,并且扩容也是针对这个对象  	 transient volatile HashEntry<K,V>[] table;   	 // 元素个数  	 transient int count;   	 // 修改次数,和hashmap一样  	 transient int modCount;   	 // 扩容阀值 ,容量 * 加载因子      transient int threshold;       // 加载因子      final float loadFactor;  }

 3、HashEntry 分析

  static final class HashEntry<K,V> {         // hash 值         final int hash;         // 键         final K key;         // 值         volatile V value;         // 下一个元素         volatile HashEntry<K,V> next;     }

4、ConcurrentHashMap 基本分析

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>         implements ConcurrentMap<K, V>, Serializable {      // 默认HashEntry容量     static final int DEFAULT_INITIAL_CAPACITY = 16;      // 加载因子     static final float DEFAULT_LOAD_FACTOR = 0.75f;      // 默认Segment容量,并发度,默认支持16个线程同时操作     static final int DEFAULT_CONCURRENCY_LEVEL = 16;      // ConcurrentHashMap最大容量     static final int MAXIMUM_CAPACITY = 1 << 30;      // Segment中HashEntry最小容量     static final int MIN_SEGMENT_TABLE_CAPACITY = 2;     	// Segment最大容量     static final int MAX_SEGMENTS = 1 << 16;      	// 非锁定情况下,调用size方法和contains方法的重试次数,如果超过该次数,直接全部上锁在进行操作     static final int RETRIES_BEFORE_LOCK = 2;   // 构造方法: 计算Segment、以及Segment对应的HashEntry数组容量大小,然后进行,并且初始化Segment中下标为0的元素   public ConcurrentHashMap(int initialCapacity,                              float loadFactor, int concurrencyLevel) {   		// 校验参数         if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)             throw new IllegalArgumentException();          //  并发级别,也就是对应Segment数组对应大小,如果超过最大容量,则直接取最大容量         if (concurrencyLevel > MAX_SEGMENTS)             concurrencyLevel = MAX_SEGMENTS;         //          int sshift = 0;         // ssize = 大于等于并发级数的2的幂次方数         int ssize = 1;         // while 去找,         while (ssize < concurrencyLevel) {             ++sshift;             ssize <<= 1;         }         this.segmentShift = 32 - sshift;         // segment长度 - 1 ,用来计算下标:hash & segmentMask         this.segmentMask = ssize - 1;          // 校验是否大于最大容量         if (initialCapacity > MAXIMUM_CAPACITY)             initialCapacity = MAXIMUM_CAPACITY;          // 这一整块代码是用来计算最后HashEntry数组容量的值,cap          // 先用HashEntry数组大小 / Segment数组大小,默认 16 / 16 = 1         int c = initialCapacity / ssize;         // 判断计算结果c & Segment数组大小,是否HashEntry数组大小,如果小于c + 1 ,         // 向上取整,假设initialCapacity = 17,而ssize 只有16个,那么Segment下面就不够存放17个HashEntry,所以这里就需要这么操作         // 1 * 16 < 17,最后c的结果就是2         if (c * ssize < initialCapacity)             ++c;          // cap 默认等于HashEntry最小值 2          int cap = MIN_SEGMENT_TABLE_CAPACITY;         // 如果cap 小于 c,则cap需要左移动来获取最终HashEntry的值         while (cap < c)         	// cap最后的结果是2的幂次方数             cap <<= 1;          // 初始化Segment第0个对象,以后调用put方式时候,需要添加到其他Segment中,如果Segment为null,         // 则参考Segment下标为0这个对象的属性,避免重复计算Segment、HashEntry容量值         Segment<K,V> s0 =             new Segment<K,V>(loadFactor, (int)(cap * loadFactor),                              (HashEntry<K,V>[])new HashEntry[cap]);         // 创建Segment对象             Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];         // 利用UNSAFE类,直接把s0赋值到ss当中         UNSAFE.putOrderedObject(ss, SBASE, s0);         // 最后把当前ConcurrentHashMap中的segments属性赋值         this.segments = ss;     }

5、Put 分析

 public V put(K key, V value) {         Segment<K,V> s;         // 如果value为null,直接抛出异常         if (value == null)             throw new NullPointerException();         // 获取key 对应的hey值         int hash = hash(key);         // 计算该key存放segment对应的下标, hahs & segmentMask(segment数组长度 -  1)         int j = (hash >>> segmentShift) & segmentMask;          // 查看第j个位置的segment的元素是否为空,如果为空则去创建         if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null)              s = ensureSegment(j);          // 调用segment元素的put方法,插入到链表中         return s.put(key, hash, value, false);     }

6、ensureSegment 分析

// 创建Segment 对象,通过UnSafe类保证线程安全   private Segment<K,V> ensureSegment(int k) {         // 获取整个segment数组对象         final Segment<K,V>[] ss = this.segments;         // 获取偏移量,帮助UnSafe类来定位数组中具体的位置         long u = (k << SSHIFT) + SBASE; // raw offset         Segment<K,V> seg;         // 判断当前位置的segment是否为空         if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {             // 以segment[0]为基础,来创建其他segment对象             Segment<K,V> proto = ss[0];              // 取Segment[0]中HashEntry数组大小             int cap = proto.table.length;             // 取Segment[0]中的加载因子             float lf = proto.loadFactor;             // 计算扩容阀值             int threshold = (int)(cap * lf);             // 创建HashEntry对象             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);                 // 通过CAS方式,将新增的segment元素放入到segment数组当中                 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))                        == null) {                     if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))                         break;                 }             }         }         // 返回对象         return seg;     }

7、put 添加元素

// 添加元素     final V put(K key, int hash, V value, boolean onlyIfAbsent) {             // 先尝试获取锁,tryLock()直接返回结果,不阻塞             // 如果拿到锁则可以进行执行,否则调用scanAndLockForPut(key, hash, value)方法进行其他操作             HashEntry<K,V> node = tryLock() ? null :                 scanAndLockForPut(key, hash, value);             V oldValue;             try {                 // 获取当前Segment对象的table元素                 HashEntry<K,V>[] tab = table;                 // 计算当前key所存放在HashEntry对应下标位置                 int index = (tab.length - 1) & hash;                 // 获取存放具体元素的链表,头节点                 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;                             // 如果onlyIfAbsent = false,则会替换之前key的值,并且修改次数+1                             // 如果为ture,则不进行替换,直接结束循环                             // 主要功能是为了:在put时,判断需不需要如果key重复就不需要进行修改                             if (!onlyIfAbsent) {                                 e.value = value;                                 ++modCount;                             }                             break;                         }                         // 元素后移,继续循环                         e = e.next;                     }                     else {                         // 这里node不等于null的情况,是因为最开始没有获取到锁,然后进行了创建                         if (node != null)                             node.setNext(first);                         else                         // 线程第一次正常拿到锁执行到这,node应该是null,然后进行创建 头插法                             node = new HashEntry<K,V>(hash, key, value, first);                         // 节点数量 + 1                          int c = count + 1;                         // 判断是否需要扩容,这里的扩容只是针对HashEntry数组                         // 当前HashEntry全部元素 > 扩容阀值 && 当前HashEntry数组大小 < 最大容量                         if (c > threshold && tab.length < MAXIMUM_CAPACITY)                             // 扩容                             rehash(node);                         else                             // 将当前新元素设置成tab数组中index下标的第一个元素,成为头节点                             setEntryAt(tab, index, node);                         // 修改次数++                         ++modCount;                         // 更新节点数量                         count = c;                         // 老的元素赋值为空                         oldValue = null;                         break;                     }                 }             } finally {                 // 解锁                 unlock();             }             // 返回老的值             return oldValue;         }

8、scanAndLockForPut 未获取到锁执行的方法

// 当put时,线程没有获取到锁的时候,执行这个方法  private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {             // 获取当前segment中HashEntry第一个元素             HashEntry<K,V> first = entryForHash(this, hash);             HashEntry<K,V> e = first;             HashEntry<K,V> node = null;             // 用来控制循环流程标识             int retries = -1;              // 循环尝试获取锁,如果获取到了结束循环,如果没有获取到执行while中的逻辑             while (!tryLock()) {                 HashEntry<K,V> f;                  // 第一次retires默认=-1,                 if (retries < 0) {                     // e == null 分为两种情况:                     // 1、当前HashEntry元素是初始化状态,元素为空                     // 2、遍历完整个链表,一直到链表尾部                     if (e == null) {                         if (node == null)                             // 获取一个新节点                             node = new HashEntry<K,V>(hash, key, value, null);                         // 并且把流程控制状态为0                         retries = 0;                     }                     // 如果元素不为空,则判断key是否相等                     else if (key.equals(e.key))                         retries = 0;                     // 以上条件不满足,则元素后移,继续循环                     else                         e = e.next;                 }                 // 控制循环次数,当retries操作数,大于了最大自旋数,则进行lock进行阻塞                 else if (++retries > MAX_SCAN_RETRIES) {                     // 如果lock没获取到锁,则进行阻塞,阻塞被唤醒获取到锁之后,终止循环                     lock();                     break;                 }                 // 这里判断是因为:如果在while循环当中,可能链表结构被其他线程所修改了,所以这里会进行最新的头节点,和之前获取的头节点进行判断                 // (retries & 1) == 0 ,判断奇偶数,当retries为偶数的时候,条件成立                 // (f = entryForHash(this, hash)) != first ,获取最新的当前链表头节点,与之前对比                 // 如果被修改,                 else if ((retries & 1) == 0 &&                          (f = entryForHash(this, hash)) != first) {                     // 把e 、first 全部更新为最新的头节点                     e = first = f;                     // 改为-1,重新遍历链表                     retries = -1;                 }             }             return node;         }

8、rehash 扩容

private void rehash(HashEntry<K,V> node) {             // 记录老的table数组             HashEntry<K,V>[] oldTable = table;             // 记录老的容量             int oldCapacity = oldTable.length;             // 获取新数组的容量,之前的两倍             int newCapacity = oldCapacity << 1;             // 计算新的阀值             threshold = (int)(newCapacity * loadFactor);             // 创建新容量的HashEntry数组             HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];             // 用来计算下标             int sizeMask = newCapacity - 1;              // 遍历老的table进行元素转移             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;                     // 如果next == null,则表示链表元素只有一个                     if (next == null)                          // 直接把当前元素转移到新数组上面即可                         newTable[idx] = e;                     else {                         // 如果不止一个就需要进行转移了                         // 先把头节点赋值给lastRun,以及新数组中的下标                         HashEntry<K,V> lastRun = e;                         int lastIdx = idx;                         // 遍历每一个元素,找下标相同的元素,以最后一组为准                         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);                         }                     }                 }             }             // 扩容完成还需要将新的元素添加到链表当中             int nodeIndex = node.hash & sizeMask; // add the new node             node.setNext(newTable[nodeIndex]);             newTable[nodeIndex] = node;             // 把当前segment的table 更新成扩容后的元素             table = newTable;         }

9、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;         // 判断当前segment对象不为空,并且segment中的table不为空         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;     }

10、size 方法

public int size() {         // 获取当前整个segment数组         final Segment<K,V>[] segments = this.segments;         // 声明变量,便于统计         int size;         boolean overflow; // true if size overflows 32 bits         long sum;         // sum of modCounts         long last = 0L;   // previous sum         int retries = -1; // first iteration isn't retry         try {             // 上来就一个死循环             for (;;) {                 // 判断循环次数是否等于自旋次数                 if (retries++ == RETRIES_BEFORE_LOCK) {                     // 对每个segment对象进行加锁,加锁后再进行统计                     for (int j = 0; j < segments.length; ++j)                         ensureSegment(j).lock(); // force creation                 }                 sum = 0L;                 size = 0;                 overflow = false;                 // 对每个segmentAt的数量进行统计                 for (int j = 0; j < segments.length; ++j) {                     Segment<K,V> seg = segmentAt(segments, j);                     if (seg != null) {                         // 进行统计                         sum += seg.modCount;                         int c = seg.count;                         if (c < 0 || (size += c) < 0)                             overflow = true;                     }                 }                 // 如果循环两次的结果都是一样,则表示没有线程进行操作,直接返回                 // 如果不一致,则继续重新赋值循环操作,超过一定的循环次数就整个加锁进行统计                 if (sum == last)                     break;                 last = sum;             }         } finally {             // 循环进行解锁操作             if (retries > RETRIES_BEFORE_LOCK) {                 for (int j = 0; j < segments.length; ++j)                     segmentAt(segments, j).unlock();             }         }         return overflow ? Integer.MAX_VALUE : size;     }

 

版权声明:玥玥 发表于 2021-05-19 14:10:39。
转载请注明:ConcurrentHashMap1.7 最最最最最详细源码分析 | 女黑客导航