jdk7

锁分离技术


static final class Segment< K,V> extends ReentrantLock implements Serializable

// The segments, each of which is a specialized hash table.
final Segment< K,V>[] segments;

Segment 是个特殊的 hashmap 
private void rehash(HashEntry< K,V> node)

在Segment上扩容


ReentrantLock+Segment+HashEntry

代码行数 1620

public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel)
根据 concurrencyLevel 计算 Segment 数量

        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    

    



jdk8

Node数组+链表+红黑树

synchronized+CAS+HashEntry+红黑树

注意使用的是 synchronized ,不是  ReentrantLock

数据结构类似HashMap

链表的数量大于8，转换成黑红树

代码行数 6312





1 整体结构

1.7 Segment + HashEntry + Unsafe
1.8 移除Segment，锁的粒度更小，Synchronized + CAS + Node + Unsafe

2 put
1.7 先定位Segment，再定位桶，put全程加锁，没有获取锁的线程提前找桶的位置，并最多自旋64次获取锁，超过则挂起。
1.8 移除Segment，类似HashMap，可以直接定位到桶，拿到first节点后进行判断，1、为空则CAS插入；2、为-1则说明在扩容，则跟着一起扩容；3、else则加锁put（类似1.7）

3 get

基本类似，value声明为volatile，保证了修改的可见性，不需要加锁。

4 resize
1.7 跟HashMap步骤一样，只不过是搬到单线程中执行，避免了HashMap在1.7中扩容时死循环的问题，保证线程安全。

1.8 支持并发扩容，HashMap扩容在1.8中由头插改为尾插（避免死循环问题），ConcurrentHashmap也是，迁移从尾部开始，扩容前在桶的头部放置一个hash值为-1的节点，这样别的线程访问时就能判断是否该桶已经被其他线程处理过了。

5 size
1.7  计算两次，如果不变则返回计算结果，若不一致，则锁住所有的Segment求和
1.8   参考 LongAdder  

final long sumCount() {
        CounterCell[] as = counterCells; CounterCell a;
        long sum = baseCount;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }