Java并发系列之ConcurrentHashMap源码分析

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

//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//默认并发级别
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

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

//分段锁的最小数量
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

//分段锁的最大数量
static final int MAX_SEGMENTS = 1 << 16;

//加锁前的重试次数
static final int RETRIES_BEFORE_LOCK = 2;

//分段锁的掩码值
final int segmentMask;

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

//分段锁数组
final Segment[] segments;

//分段锁
static final class Segment extends ReentrantLock implements Serializable {
  //自旋最大次数
  static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
  //哈希表
  transient volatile HashEntry[] table;
  //元素总数
  transient int count;
  //修改次数
  transient int modCount;
  //元素阀值
  transient int threshold;
  //加载因子
  final float loadFactor;
  //省略以下内容
  ...
}

//核心构造器
@SuppressWarnings("unchecked")
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;
  }
  int sshift = 0;
  int ssize = 1;
  //保证ssize为2的幂, 且是最接近的大于等于并发级别的数
  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;
  //分段锁容量总和不小于初始总容量
  if (c * ssize < initialCapacity) {
    ++c;
  }
  int cap = MIN_SEGMENT_TABLE_CAPACITY;
  //保证cap为2的幂, 且是最接近的大于等于c的数
  while (cap < c) {
    cap <<= 1;
  }
  //新建一个Segment对象模版
  Segment s0 = new Segment(loadFactor, (int)(cap * loadFactor), (HashEntry[])new HashEntry[cap]);
  //新建指定大小的分段锁数组
  Segment[] ss = (Segment[])new Segment[ssize];
  //使用UnSafe给数组第0个元素赋值
  UNSAFE.putOrderedObject(ss, SBASE, s0);
  this.segments = ss;
}

//根据哈希码获取分段锁
@SuppressWarnings("unchecked")
private Segment segmentForHash(int h) {
  long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  return (Segment) UNSAFE.getObjectVolatile(segments, u);
}

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

//根据key获取value
public V get(Object key) {
  Segment s;
  HashEntry[] tab;
  //使用哈希函数计算哈希码
  int h = hash(key);
  //根据哈希码计算分段锁的索引
  long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  //获取分段锁和对应的哈希表
  if ((s = (Segment)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) {
    //根据哈希码获取链表头结点, 再对链表进行遍历
    for (HashEntry e = (HashEntry) UNSAFE.getObjectVolatile
         (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
       e != null; e = e.next) {
      K k;
      //根据key和hash找到对应元素后返回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 s;
  //传入的value不能为空
  if (value == null) throw new NullPointerException();
  //使用哈希函数计算哈希码
  int hash = hash(key);
  //根据哈希码计算分段锁的下标
  int j = (hash >>> segmentShift) & segmentMask;
  //根据下标去尝试获取分段锁
  if ((s = (Segment)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) {
    //获得的分段锁为空就去构造一个
    s = ensureSegment(j);
  }
  //调用分段锁的put方法
  return s.put(key, hash, value, false);
}

//向集合添加键值对(不存在才添加)
@SuppressWarnings("unchecked")
public V putIfAbsent(K key, V value) {
  Segment s;
  //传入的value不能为空
  if (value == null) throw new NullPointerException();
  //使用哈希函数计算哈希码
  int hash = hash(key);
  //根据哈希码计算分段锁的下标
  int j = (hash >>> segmentShift) & segmentMask;
  //根据下标去尝试获取分段锁
  if ((s = (Segment)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) {
    //获得的分段锁为空就去构造一个
    s = ensureSegment(j);
  }
  //调用分段锁的put方法
  return s.put(key, hash, value, true);
}

//添加键值对
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
  //尝试获取锁, 若失败则进行自旋
  HashEntry node = tryLock() ? null : scanAndLockForPut(key, hash, value);
  V oldValue;
  try {
    HashEntry[] tab = table;
    //计算元素在数组中的下标
    int index = (tab.length - 1) & hash;
    //根据下标获取链表头结点
    HashEntry first = entryAt(tab, index);
    for (HashEntry 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 {
        //将node结点插入链表头部
        if (node != null) {
          node.setNext(first);
        } else {
          node = new HashEntry(hash, key, value, first);
        }
        //插入结点后将元素总是加1
        int c = count + 1;
        //元素超过阀值则进行扩容
        if (c > threshold && tab.length < MAXIMUM_CAPACITY) {
          rehash(node);
        //否则就将哈希表指定下标替换为node结点
        } else {
          setEntryAt(tab, index, node);
        }
        ++modCount;
        count = c;
        oldValue = null;
        break;
      }
    }
  } finally {
    unlock();
  }
  return oldValue;
}

//删除指定元素(找到对应元素后直接删除)
public V remove(Object key) {
  //使用哈希函数计算哈希码
  int hash = hash(key);
  //根据哈希码获取分段锁的索引
  Segment s = segmentForHash(hash);
  //调用分段锁的remove方法
  return s == null ? null : s.remove(key, hash, null);
}

//删除指定元素(查找值等于给定值才删除)
public boolean remove(Object key, Object value) {
  //使用哈希函数计算哈希码
  int hash = hash(key);
  Segment s;
  //确保分段锁不为空才调用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[] tab = table;
    //计算元素在数组中的下标
    int index = (tab.length - 1) & hash;
    //根据下标取得数组元素(链表头结点)
    HashEntry e = entryAt(tab, index);
    HashEntry pred = null;
    //遍历链表寻找要删除的元素
    while (e != null) {
      K k;
      //next指向当前结点的后继结点
      HashEntry next = e.next;
      //根据key和hash寻找对应结点
      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为空则代表要删除的结点为头结点
          if (pred == null) {
            //重新设置链表头结点
            setEntryAt(tab, index, next);
          } else {
            //设置pred结点的后继为next结点
            pred.setNext(next);
          }
          ++modCount;
          --count;
          //记录元素删除之前的值
          oldValue = v;
        }
        break;
      }
      //若e不是要找的结点就将pred引用指向它
      pred = e;
      //检查下一个结点
      e = next;
    }
  } finally {
    unlock();
  }
  return oldValue;
}

//替换指定元素(CAS操作)
public boolean replace(K key, V oldValue, V newValue) {
  //使用哈希函数计算哈希码
  int hash = hash(key);
  //保证oldValue和newValue不为空
  if (oldValue == null || newValue == null) throw new NullPointerException();
  //根据哈希码获取分段锁的索引
  Segment s = segmentForHash(hash);
  //调用分段锁的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 e;
    //通过hash直接找到头结点然后对链表遍历
    for (e = entryForHash(this, hash); e != null; e = e.next) {
      K k;
      //根据key和hash找到要替换的结点
      if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
        //如果指定的当前值正确则进行替换
        if (oldValue.equals(e.value)) {
          e.value = newValue;
          ++modCount;
          replaced = true;
        }
        //否则不进行任何操作直接返回
        break;
      }
    }
  } finally {
    unlock();
  }
  return replaced;
}

//自旋等待获取锁(put操作)
private HashEntry scanAndLockForPut(K key, int hash, V value) {
  //根据哈希码获取头结点
  HashEntry first = entryForHash(this, hash);
  HashEntry e = first;
  HashEntry node = null;
  int retries = -1;
  //在while循环内自旋
  while (!tryLock()) {
    HashEntry f;
    if (retries < 0) {
      //如果头结点为空就新建一个node
      if (e == null) {
        if (node == null) {
          node = new HashEntry(hash, key, value, null);
        }
        retries = 0;
      //否则就遍历链表定位该结点
      } else if (key.equals(e.key)) {
        retries = 0;
      } else {
        e = e.next;
      }
     //retries每次在这加1, 并判断是否超过最大值
    } else if (++retries > MAX_SCAN_RETRIES) {
      lock();
      break;
     //retries为偶数时去判断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) {
  //根据哈希码获取链表头结点
  HashEntry first = entryForHash(this, hash);
  HashEntry e = first;
  int retries = -1;
  //在while循环里自旋
  while (!tryLock()) {
    HashEntry f;
    if (retries < 0) {
      //遍历链表定位到该结点
      if (e == null || key.equals(e.key)) {
        retries = 0;
      } else {
        e = e.next;
      }
     //retries每次在这加1, 并判断是否超过最大值
    } else if (++retries > MAX_SCAN_RETRIES) {
      lock();
      break;
     //retries为偶数时去判断first有没有改变
    } else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) {
      e = first = f;
      retries = -1;
    }
  }
}

//再哈希
@SuppressWarnings("unchecked")
private void rehash(HashEntry node) {
  //获取旧哈希表的引用
  HashEntry[] oldTable = table;
  //获取旧哈希表的容量
  int oldCapacity = oldTable.length;
  //计算新哈希表的容量(为旧哈希表的2倍)
  int newCapacity = oldCapacity << 1;
  //计算新的元素阀值
  threshold = (int)(newCapacity * loadFactor);
  //新建一个HashEntry数组
  HashEntry[] newTable = (HashEntry[]) new HashEntry[newCapacity];
  //生成新的掩码值
  int sizeMask = newCapacity - 1;
  //遍历旧表的所有元素
  for (int i = 0; i < oldCapacity ; i++) {
    //取得链表头结点
    HashEntry e = oldTable[i];
    if (e != null) {
      HashEntry next = e.next;
      //计算元素在新表中的索引
      int idx = e.hash & sizeMask;
      //next为空表明链表只有一个结点
      if (next == null) {
        //直接把该结点放到新表中
        newTable[idx] = e;
      }else {
        HashEntry lastRun = e;
        int lastIdx = idx;
        //定位lastRun结点, 将lastRun之后的结点直接放到新表中
        for (HashEntry 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 p = e; p != lastRun; p = p.next) {
          V v = p.value;
          int h = p.hash;
          int k = h & sizeMask;
          HashEntry n = newTable[k];
          newTable[k] = new HashEntry(h, p.key, v, n);
        }
      }
    }
  }
  //计算传入结点在新表中的下标
  int nodeIndex = node.hash & sizeMask;
  //将传入结点添加到链表头结点
  node.setNext(newTable[nodeIndex]);
  //将新表指定下标元素换成传入结点
  newTable[nodeIndex] = node;
  //将哈希表引用指向新表
  table = newTable;
}