//默認初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;

//默認加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//默認并發(fā)級別
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

//集合最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//分段鎖的最小數(shù)量
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

//分段鎖的最大數(shù)量
static final int MAX_SEGMENTS = 1 << 16;

//加鎖前的重試次數(shù)
static final int RETRIES_BEFORE_LOCK = 2;

//分段鎖的掩碼值
final int segmentMask;

//分段鎖的移位值
final int segmentShift;

//分段鎖數(shù)組
final Segment<K,V>[] segments;

//分段鎖
static final class Segment<K,V> extends ReentrantLock implements Serializable {
  //自旋最大次數(shù)
  static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
  //哈希表
  transient volatile HashEntry<K,V>[] table;
  //元素總數(shù)
  transient int count;
  //修改次數(shù)
  transient int modCount;
  //元素閥值
  transient int threshold;
  //加載因子
  final float loadFactor;
  //省略以下內(nèi)容
  ...
}

//核心構(gòu)造器
@SuppressWarnings("unchecked")
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
  if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
    throw new IllegalArgumentException();
  }
  //確保并發(fā)級別不大于限定值
  if (concurrencyLevel > MAX_SEGMENTS) {
    concurrencyLevel = MAX_SEGMENTS;
  }
  int sshift = 0;
  int ssize = 1;
  //保證ssize為2的冪, 且是最接近的大于等于并發(fā)級別的數(shù)
  while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
  }
  //計算分段鎖的移位值
  this.segmentShift = 32 - sshift;
  //計算分段鎖的掩碼值
  this.segmentMask = ssize - 1;
  //總的初始容量不能大于限定值
  if (initialCapacity > MAXIMUM_CAPACITY) {
    initialCapacity = MAXIMUM_CAPACITY;
  }
  //獲取每個分段鎖的初始容量
  int c = initialCapacity / ssize;
  //分段鎖容量總和不小于初始總?cè)萘?
  if (c * ssize < initialCapacity) {
    ++c;
  }
  int cap = MIN_SEGMENT_TABLE_CAPACITY;
  //保證cap為2的冪, 且是最接近的大于等于c的數(shù)
  while (cap < c) {
    cap <<= 1;
  }
  //新建一個Segment對象模版
  Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[])new HashEntry[cap]);
  //新建指定大小的分段鎖數(shù)組
  Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
  //使用UnSafe給數(shù)組第0個元素賦值
  UNSAFE.putOrderedObject(ss, SBASE, s0);
  this.segments = ss;
}

//根據(jù)哈希碼獲取分段鎖
@SuppressWarnings("unchecked")
private Segment<K,V> segmentForHash(int h) {
  long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
}

//根據(jù)哈希碼獲取元素
@SuppressWarnings("unchecked")
static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
  HashEntry<K,V>[] tab;
  return (seg == null || (tab = seg.table) == null) ? null :
  (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
}

//根據(jù)key獲取value
public V get(Object key) {
  Segment<K,V> s;
  HashEntry<K,V>[] tab;
  //使用哈希函數(shù)計算哈希碼
  int h = hash(key);
  //根據(jù)哈希碼計算分段鎖的索引
  long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  //獲取分段鎖和對應(yīng)的哈希表
  if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) {
    //根據(jù)哈希碼獲取鏈表頭結(jié)點, 再對鏈表進行遍歷
    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;
      //根據(jù)key和hash找到對應(yīng)元素后返回value值
      if ((k = e.key) == key || (e.hash == h && key.equals(k))) {
        return e.value;
      }
    }
  }
  return null;
}

//向集合添加鍵值對(若存在則替換)
@SuppressWarnings("unchecked")
public V put(K key, V value) {
  Segment<K,V> s;
  //傳入的value不能為空
  if (value == null) throw new NullPointerException();
  //使用哈希函數(shù)計算哈希碼
  int hash = hash(key);
  //根據(jù)哈希碼計算分段鎖的下標(biāo)
  int j = (hash >>> segmentShift) & segmentMask;
  //根據(jù)下標(biāo)去嘗試獲取分段鎖
  if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) {
    //獲得的分段鎖為空就去構(gòu)造一個
    s = ensureSegment(j);
  }
  //調(diào)用分段鎖的put方法
  return s.put(key, hash, value, false);
}

//向集合添加鍵值對(不存在才添加)
@SuppressWarnings("unchecked")
public V putIfAbsent(K key, V value) {
  Segment<K,V> s;
  //傳入的value不能為空
  if (value == null) throw new NullPointerException();
  //使用哈希函數(shù)計算哈希碼
  int hash = hash(key);
  //根據(jù)哈希碼計算分段鎖的下標(biāo)
  int j = (hash >>> segmentShift) & segmentMask;
  //根據(jù)下標(biāo)去嘗試獲取分段鎖
  if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) {
    //獲得的分段鎖為空就去構(gòu)造一個
    s = ensureSegment(j);
  }
  //調(diào)用分段鎖的put方法
  return s.put(key, hash, value, true);
}

//添加鍵值對
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;
    //計算元素在數(shù)組中的下標(biāo)
    int index = (tab.length - 1) & hash;
    //根據(jù)下標(biāo)獲取鏈表頭結(jié)點
    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;
          //根據(jù)參數(shù)決定是否替換舊值
          if (!onlyIfAbsent) {
            e.value = value;
            ++modCount;
          }
          break;
        }
        e = e.next;
      //沒找到則在鏈表添加一個結(jié)點
      } else {
        //將node結(jié)點插入鏈表頭部
        if (node != null) {
          node.setNext(first);
        } else {
          node = new HashEntry<K,V>(hash, key, value, first);
        }
        //插入結(jié)點后將元素總是加1
        int c = count + 1;
        //元素超過閥值則進行擴容
        if (c > threshold && tab.length < MAXIMUM_CAPACITY) {
          rehash(node);
        //否則就將哈希表指定下標(biāo)替換為node結(jié)點
        } else {
          setEntryAt(tab, index, node);
        }
        ++modCount;
        count = c;
        oldValue = null;
        break;
      }
    }
  } finally {
    unlock();
  }
  return oldValue;
}

//刪除指定元素(找到對應(yīng)元素后直接刪除)
public V remove(Object key) {
  //使用哈希函數(shù)計算哈希碼
  int hash = hash(key);
  //根據(jù)哈希碼獲取分段鎖的索引
  Segment<K,V> s = segmentForHash(hash);
  //調(diào)用分段鎖的remove方法
  return s == null ? null : s.remove(key, hash, null);
}

//刪除指定元素(查找值等于給定值才刪除)
public boolean remove(Object key, Object value) {
  //使用哈希函數(shù)計算哈希碼
  int hash = hash(key);
  Segment<K,V> s;
  //確保分段鎖不為空才調(diào)用remove方法
  return value != null && (s = segmentForHash(hash)) != null && s.remove(key, hash, value) != null;
}

//刪除指定元素
final V remove(Object key, int hash, Object value) {
  //嘗試獲取鎖, 若失敗則進行自旋
  if (!tryLock()) {
    scanAndLock(key, hash);
  }
  V oldValue = null;
  try {
    HashEntry<K,V>[] tab = table;
    //計算元素在數(shù)組中的下標(biāo)
    int index = (tab.length - 1) & hash;
    //根據(jù)下標(biāo)取得數(shù)組元素(鏈表頭結(jié)點)
    HashEntry<K,V> e = entryAt(tab, index);
    HashEntry<K,V> pred = null;
    //遍歷鏈表尋找要刪除的元素
    while (e != null) {
      K k;
      //next指向當(dāng)前結(jié)點的后繼結(jié)點
      HashEntry<K,V> next = e.next;
      //根據(jù)key和hash尋找對應(yīng)結(jié)點
      if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
        V v = e.value;
        //傳入的value不等于v就跳過, 其他情況就進行刪除操作
        if (value == null || value == v || value.equals(v)) {
          //如果pred為空則代表要刪除的結(jié)點為頭結(jié)點
          if (pred == null) {
            //重新設(shè)置鏈表頭結(jié)點
            setEntryAt(tab, index, next);
          } else {
            //設(shè)置pred結(jié)點的后繼為next結(jié)點
            pred.setNext(next);
          }
          ++modCount;
          --count;
          //記錄元素刪除之前的值
          oldValue = v;
        }
        break;
      }
      //若e不是要找的結(jié)點就將pred引用指向它
      pred = e;
      //檢查下一個結(jié)點
      e = next;
    }
  } finally {
    unlock();
  }
  return oldValue;
}

//替換指定元素(CAS操作)
public boolean replace(K key, V oldValue, V newValue) {
  //使用哈希函數(shù)計算哈希碼
  int hash = hash(key);
  //保證oldValue和newValue不為空
  if (oldValue == null || newValue == null) throw new NullPointerException();
  //根據(jù)哈希碼獲取分段鎖的索引
  Segment<K,V> s = segmentForHash(hash);
  //調(diào)用分段鎖的replace方法
  return s != null && s.replace(key, hash, oldValue, newValue);
}

//替換元素操作(CAS操作)
final boolean replace(K key, int hash, V oldValue, V newValue) {
  //嘗試獲取鎖, 若失敗則進行自旋
  if (!tryLock()) {
    scanAndLock(key, hash);
  }
  boolean replaced = false;
  try {
    HashEntry<K,V> e;
    //通過hash直接找到頭結(jié)點然后對鏈表遍歷
    for (e = entryForHash(this, hash); e != null; e = e.next) {
      K k;
      //根據(jù)key和hash找到要替換的結(jié)點
      if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
        //如果指定的當(dāng)前值正確則進行替換
        if (oldValue.equals(e.value)) {
          e.value = newValue;
          ++modCount;
          replaced = true;
        }
        //否則不進行任何操作直接返回
        break;
      }
    }
  } finally {
    unlock();
  }
  return replaced;
}

//自旋等待獲取鎖(put操作)
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
  //根據(jù)哈希碼獲取頭結(jié)點
  HashEntry<K,V> first = entryForHash(this, hash);
  HashEntry<K,V> e = first;
  HashEntry<K,V> node = null;
  int retries = -1;
  //在while循環(huán)內(nèi)自旋
  while (!tryLock()) {
    HashEntry<K,V> f;
    if (retries < 0) {
      //如果頭結(jié)點為空就新建一個node
      if (e == null) {
        if (node == null) {
          node = new HashEntry<K,V>(hash, key, value, null);
        }
        retries = 0;
      //否則就遍歷鏈表定位該結(jié)點
      } else if (key.equals(e.key)) {
        retries = 0;
      } else {
        e = e.next;
      }
     //retries每次在這加1, 并判斷是否超過最大值
    } else if (++retries > MAX_SCAN_RETRIES) {
      lock();
      break;
     //retries為偶數(shù)時去判斷first有沒有改變
    } else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) {
      e = first = f;
      retries = -1;
    }
  }
  return node;
}

//自旋等待獲取鎖(remove和replace操作)
private void scanAndLock(Object key, int hash) {
  //根據(jù)哈希碼獲取鏈表頭結(jié)點
  HashEntry<K,V> first = entryForHash(this, hash);
  HashEntry<K,V> e = first;
  int retries = -1;
  //在while循環(huán)里自旋
  while (!tryLock()) {
    HashEntry<K,V> f;
    if (retries < 0) {
      //遍歷鏈表定位到該結(jié)點
      if (e == null || key.equals(e.key)) {
        retries = 0;
      } else {
        e = e.next;
      }
     //retries每次在這加1, 并判斷是否超過最大值
    } else if (++retries > MAX_SCAN_RETRIES) {
      lock();
      break;
     //retries為偶數(shù)時去判斷first有沒有改變
    } else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) {
      e = first = f;
      retries = -1;
    }
  }
}

//再哈希
@SuppressWarnings("unchecked")
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數(shù)組
  HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
  //生成新的掩碼值
  int sizeMask = newCapacity - 1;
  //遍歷舊表的所有元素
  for (int i = 0; i < oldCapacity ; i++) {
    //取得鏈表頭結(jié)點
    HashEntry<K,V> e = oldTable[i];
    if (e != null) {
      HashEntry<K,V> next = e.next;
      //計算元素在新表中的索引
      int idx = e.hash & sizeMask;
      //next為空表明鏈表只有一個結(jié)點
      if (next == null) {
        //直接把該結(jié)點放到新表中
        newTable[idx] = e;
      }else {
        HashEntry<K,V> lastRun = e;
        int lastIdx = idx;
        //定位lastRun結(jié)點, 將lastRun之后的結(jié)點直接放到新表中
        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結(jié)點之前的元素, 將它們依次復(fù)制到新表中
        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);
        }
      }
    }
  }
  //計算傳入結(jié)點在新表中的下標(biāo)
  int nodeIndex = node.hash & sizeMask;
  //將傳入結(jié)點添加到鏈表頭結(jié)點
  node.setNext(newTable[nodeIndex]);
  //將新表指定下標(biāo)元素換成傳入結(jié)點
  newTable[nodeIndex] = node;
  //將哈希表引用指向新表
  table = newTable;
}