ConcurrentHashMap学习
属性
代码语言：javascript复制//最大容量 2的30次方
private static final int MAXIMUM_CAPACITY = 1 << 30;
//初始容量
private static final int DEFAULT_CAPACITY = 16;
/**
* 虚拟机限制的最大数组长度，在ArrayList中有说过，jdk1.8新引入的，
* ConcurrentHashMap的主体代码中是不使用这个的，主要用在Collection.toArray两个方法中
*/
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
*默认并行级别，主体代码中未使用此常量，为了兼容性，保留了之前的定义，
*主要是配合同样是为了兼容性的Segment使用
*/
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//默认加载因子
private static final float LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
//并发扩容时每个线程最少处理16个桶
private static final int MIN_TRANSFER_STRIDE = 16;
//扩容时使用 一个标识戳
private static int RESIZE_STAMP_BITS = 16;
//标识并发扩展的最大线程数量
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
//扩容相关
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
//表示当前节点是forwarding nodes
static final int MOVED = -1;
//红黑树的代理结点
static final int TREEBIN = -2;
// 临时保留的散列表
static final int RESERVED = -3;
// 0x7fffffff = 31个1 用于将一个负数变成一个正数 但不是取绝对值
static final int HASH_BITS = 0x7fffffff;
//全局table volatile保证可见性 例如初始化时，多个线程操作
transient volatile Node<K,V>[] table;
//扩容时的临时散列表
private transient volatile Node<K,V>[] nextTable;
private transient volatile long baseCount;
//默认 0 -1 表示其他线程已经在扩容 -2 当前有俩个线程在扩容
private transient volatile int sizeCtl;
//扩容过程中，记录当前进度
private transient volatile int transferIndex;
// 0 无锁 1 加锁
private transient volatile int cellsBusy;
private transient volatile CounterCell[] counterCells;
// views
private transient KeySetView<K,V> keySet;
private transient ValuesView<K,V> values;
private transient EntrySetView<K,V> entrySet;构造函数
代码语言：javascript复制//默认无参构造函数
public ConcurrentHashMap() {
}
public ConcurrentHashMap(int initialCapacity) {
//初始容量小于0，则抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException();
//判断初始容量是否大于等于2的29次方，是则取最大值2的30次方，否则
//tableSizeFor： 返回一个比给定整数大且最接近的2的幂次方整数，如给定10，返回2的4次方16.
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity (initialCapacity >>> 1) 1));
this.sizeCtl = cap;
}
// 带初始集合数据参数的构造函数
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
//指定初始容量和负载因子
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
//指定初始容量、负载因子、并发数量
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// 初始容量参数小于并发线程数，将初始容量参数赋值为并发线程数
if (initialCapacity < concurrencyLevel)
initialCapacity = concurrencyLevel;
//计算容量 (需要存储的元素个数 / 负载因子) 1
long size = (long)(1.0 (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}实现存储的数据结构
代码语言：javascript复制//与HashMap的区别是volatile
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString(){ return key "=" val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}put方法
代码语言：javascript复制public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
//不支持key或者value为空
if (key == null || value == null) throw new NullPointerException();
//计算hash值
int hash = spread(key.hashCode());
//记录链表的长度 如果大于8的情况下，则转为红黑树
int binCount = 0;
//自旋
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//判断全局table
if (tab == null || (n = tab.length) == 0)
//初始化
tab = initTable();
/* 计算该key存放的index下标位置，查找该node节点 如果没发生index冲突
*（n-1）&hash 计算当前key存放在table的哪个下标位置
*/
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//使用cas操作去修改
//同时有多个线程同时修改 没有发生index冲突下标位置 cas修改 如果cas修改成功的
//情况下 break 退出自旋
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//下标发生冲突的情况下
else {
V oldVal = null;
synchronized (f) {
//自旋再查一次
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
//链表的情况下追加元素，break跳出synchronized锁
for (Node<K,V> e = f;; binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//是红黑树的情况
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//转红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}initTable方法
代码语言：javascript复制 //初始化
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//判断table是否为空 自旋：消耗cpu资源，但可以提高效率
while ((tab = table) == null || tab.length == 0) {
//如果发现有其他的线程正在扩容的时候，当前线程释放cpu执行权
if ((sc = sizeCtl) < 0)
//线程优先级释放
Thread.yield(); // lost initialization race; just spin
//使用cas操作修改当前sizeCtl为-1
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
//初始化
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
//假如此线程走到这步挂掉了，没有给table赋值，那么其他线程会一直在做自旋
//所以上面Thread.yield()很有用，在这种情况下最起码释放了其他线程的
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//sc 扩容阈值
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs 1 ||
sc == rs MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) 2))
transfer(tab, null);
s = sumCount();
}
}
}addCount方法
代码语言：javascript复制 private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs 1 ||
sc == rs MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) 2))
transfer(tab, null);
s = sumCount();
}
}
}spread方法（计算Hash值）
代码语言：javascript复制// 当前的hash右移16位 亦或 原来的hash & HASH_BITS 得到正数的hash值,让高16位 也参与到运算中来
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}tableSizeFor方法
代码语言：javascript复制//返回一个大于输入值 c 的2的幂
private static final int tableSizeFor(int c) {
//减一的作用是防止输入的值正好是2的幂，得到比输入值大一倍的值，例如 c = 8，如果不减1的话return 16
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}tabAt方法
代码语言：javascript复制 //获取数组指定下标位置的元素
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) ABASE);
}casTabAt方法
代码语言：javascript复制 //用cas的方式去tab指定位置设置值
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) ABASE, c, v);
}setTabAt方法
代码语言：javascript复制 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) ABASE, v);
}计算存放位置
- JDK1.7计算俩次，第一次计算存放在哪一个Segments中，第二次计算存放在Segments中的哪个下标位置。
- JDK1.8 一次，只需要计算在哪个下标位置。
我的博客即将同步至腾讯云 社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3kmaxlbket8g8
