JUC 八股17 - 并发工具类 (ConcurrentHashMap)

static final class HashEntry<K,V> {
  final int hash;
  final K key;
  volatile V value;
  final HashEntry<K,V> next;
}

static final class Segment<K,V> extends ReentrantLock {
  transient volatile HashEntry<K,V>[] table;
  transient int count;
}

public V put(K key, V value) {
  Segment<K,V> s;
  if (value == null)
      throw new NullPointerException();
  int hash = hash(key);
  int j = (hash >>> segmentShift) & segmentMask;
  if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
        (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
      s = ensureSegment(j);
  return s.put(key, hash, value, false);
}

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

public V put(K key, V value) {
  return putVal(key, value, false);
}

// 计算 hash
int hash = spread(key.hashCode());

// 初始化数组
if (tab == null || (n = tab.length) == 0)
  tab = initTable();

// 计算桶的位置
int i = (n - 1) & hash;

// CAS 插入节点
if (tabAt(tab, i) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
        break;
}

// 否则，使用 synchronized 代码块插入节点
else {
  synchronized (f) {  // **只锁当前桶**
    if (tabAt(tab, i) == f) { // 确保未被其他线程修改
      if (f.hash >= 0) { // 链表处理
          for (Node<K,V> e = f;;) {
              K ek;
              if (e.hash == hash && ((ek = e.key) == key || (key != null && key.equals(ek)))) {
                  e.val = value;
                  break;
              }
              e = e.next;
          }
      } else if (f instanceof TreeBin) { // **红黑树处理**
          ((TreeBin<K,V>) f).putTreeVal(hash, key, value);
      }
    }
  }
}

if (binCount >= TREEIFY_THRESHOLD)
  treeifyBin(tab, i);

addCount(1L, binCount);

public V get(Object key) {
  Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  int h = spread(key.hashCode());
  if ((tab = table) != null && (n = tab.length) > 0 &&
    (e = tabAt(tab, (n - 1) & h)) != null) {
    if ((eh = e.hash) == h) {
        if ((ek = e.key) == key || (ek != null && key.equals(ek)))
            return e.val;
    }
    else if (eh < 0)
        return (p = e.find(h, key)) != null ? p.val : null;
    while ((e = e.next) != null) {
        if (e.hash == h &&
            ((ek = e.key) == key || (ek != null && key.equals(ek))))
            return e.val;
    }
}
  return null;
}

static final int spread(int h) {
  return (h ^ (h >>> 16)) & HASH_BITS;
}

// HashMap
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 特殊节点的 hash 值定义
static final int MOVED   = -1;  // 正在扩容迁移的 ForwardingNode
static final int TREEBIN = -2;  // 红黑树根节点
static final int RESERVED = -3; // 临时保留节点

if (f.hash >= 0) {      // 链表处理
  // ...
} else if (f instanceof TreeBin) {  // 红黑树处理
  // ...
}

// get 中的判断
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
if ((eh = e.hash) == h) {
  // hash 相等，直接返回
} else if (eh < 0) {
  // 特殊节点，调用 find 方法处理
  return (p = e.find(h, key)) != null ? p.val : null;
}

static final class ForwardingNode<K,V> extends Node<K,V> {
  final Node<K,V>[] nextTable;
  ForwardingNode(Node<K,V>[] tab) {
      super(MOVED, null, null, null);
      this.nextTable = tab;
  }
}