jdk1.7底层结构：
concurrenthashmap jdk1.7结构
如上图，concurrenthashmap是由多个segment组成，每个segment里面包含了entry的数组。
1、初始化方法：
public ConcurrentHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}
DEFAULT_INITIAL_CATATICY: 每个segment里面的entrylist长度，默认为16
DEFAULT_LOAD_FACTOR：加载因子 默认0.75
DEFAULT_CONCURRENCY_LEVEL：并发级别（segment桶的个数）默认16
/**
*初始化map
*/
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;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
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;
while (cap < c)
cap <<= 1;
// create segments and segments[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
按照字面理解，一个segment中entry数组的长度应该是 DEFAULT_INITIAL_CATATICY /
DEFAULT_CONCURRENCY_LEVEL = 1，其实不然。
#####计算segment数组长度
//Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
这里可以看到，Segment数组的长度为ssize，ssize计算过程如下：
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
这段代码的意思是，当前桶的个数，要取大于concurrencyLevel的2n次方的数，是2的n次方，hashcode&ssize 才不会出现数组下标越界。
#####计算entry数组长度
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
#####初始化一个segment放到segment数组第一个位置。作用：预生成，后面其他桶初始化的时候直接拿过去用。
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
2、put方法
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); //将entry放入到Segment里面的 entrylist中去
}
/**
*获取segment对象
*/
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> proto = ss[0]; // use segment 0 as prototype
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // recheck
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
/**
*将entry放入到Segment里面的 entrylist中去
*/
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;
int index = (tab.length - 1) & hash;
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;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
注意：tryLock将当前方法加锁，代表只能有一个线程进行当前的entryList操作。
tryLock()是segment继承的ReentrantLock中的方法，非阻塞的 ps.lock()方法是阻塞的
这里为什么不用lock()，二用tryLock，因为tryLock非阻塞的，可以进行其他操作 -- 可以先获取entry对象。
/**
*tryLock非阻塞锁的时候对当前Segment.entryList遍历生成entry
*/
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1; // negative while locating node
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
if (retries < 0) {
if (e == null) {
if (node == null) // speculatively create node
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
e = e.next;
}
else if (++retries > MAX_SCAN_RETRIES) {
lock();
break;
}
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
如果加锁失败，根据当前segment.entryList信息新建HashEntry；HashEntry新建完成之后，retries标志位变为0，retries++操作并且retries为偶数（考虑性能，所以在偶数情况下才会判断头部是否变化），继续判断当前entryList头对应的链表头部是不是变化（因为可能其他线程已经对当前链表插入了数据，JDK1.7是头插法），如果变化，将retries变为-1，继续获取HashEntry。当retries > MAX_SCAN_RETRIES（貌似是64？）的时候，锁将变成lock()阻塞状态，防止CAS空转影响CPU性能，直到加锁成功。
如果加锁成功，则返回entry并且在put方法中进行entry设置；
jdk1.8底层结构
数组 + 链表 + 红黑树 + 大量CAS，与1.7相比，去掉了segment的概念
1、初始化
public ConcurrentHashMap() {
}
2、put方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//如果数组为空，则初始化，initTable里面有CAS操作
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果通过hashCode & table.length - 1（table[i]）计算出的下标没有node，则CAS创建头结点Node
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)
//当前节点hash值为-1，代表concurrentHashMap当前节点正在扩容，就帮助扩容
tab = helpTransfer(tab, f);
else {
//新的Node是插入到红黑树或者链表中，直接通过synchronized对链表的头结点加锁
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
//如果是链表
binCount = 1;
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)
//如果链表node数量大于8，进行树化，生成红黑树
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
addCount(1L, binCount)方法
/**
*计算count，并且根据数组长度进行初始化
*/
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的大致意思：baseCount进行cas操作+1，如果baseCount cas失败，直接cas CounterCell，在CounterCell中cas的时候如果失败也会返回cas baseCount。最终计算出map的长度。 PS.代码太复杂
addCount原理图
扩容大体流程
注意，节点进行扩容的时候，(fh = f.hash) == MOVED，线程不能put元素，直接帮助扩容 helptransfer
put方法流程：
1、判断table是否为空，如果为空，初始化table （cas自旋初始化）
2、判断头结点是否为空，如果为空，CAS自旋添加头结点
3、如果数组当前节点正在扩容，帮助扩容（helptransfer）
4、头结点不为空，synchronized头结点，将node放到链表或者treeBin
5、如果链表node数量大于8，进行树化，生成红黑树
6、利用CounterCell计算count
7、如果需要扩容，多线程进行扩容
8、线程自旋，扩容完成后再进行put操作
