ConcurrentHashMap

1.7

map-001.jpg

JDK 1.5出现，HashMap是1.2
HashMap的bin有红黑树，而该版本没有；1.8中，ConcurrentHashMap增加了红黑树
核心：锁分段技术
- 数据分段，每个segment配锁
- ConcurrentHashMap包含Segment<K,V>[] segments
- Segment包含HashEntry<K,V>[] table
- table的元素是HashEntry链表
初始化
- 根据concurrencyLevel计算ssize（Segments数组大小），ssize为大于concurrencyLevel的ceil 2次幂
数据分段对hash要求较高，所以进行了rehash，比较复杂

private int hash(Object k) {
    int h = hashSeed;
    if ((0 != h) && (k instanceof String)) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

get
- 高效在于整个过程无需加锁，除非读到值为空才会加锁重读，利用volatile实现
- int h = hash(key); // rehash
- long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; // 选取h的高位用于Segement定位
- 定位Segment中HashEntry直接用h
- 两个定位用的索引逻辑是一致的，都是hash值与数组length-1相与
- 整个hash逻辑的目的在于，保证HashEntry在Segments数组中分散，以及在Segment内部分散
put
- 先判断锁定到的Segment是否存在，不存在则创建，返回Segment
- 在Segment中进行插入，需要拿到Segment的锁才能进行插入
- 插入时先判断是否需要扩容
- HashMap的实现是先插入后扩容，理论上先扩容会好一点，可以避免可能的无效扩容
- 而且，不同于HashMap中对于整个table的扩容，ConcurrentHashMap的扩容级别为Segment级别
- 执行插入
size
- 不加锁累加各Segment的count得到map的size
- 监控modCount是否变化，判断是否需要加锁重新计算

1.8

改进
- 取消segments字段，采用volatile Node<K,V>[] table保存数据
- 用table数组元素做锁，实现bin级别加锁，减少并发冲突
- 对bin增加树化

性能比较

public class CompareConcurrentHashMap {
    private static ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<String, Integer>(40000);
    public static void putPerformance(int index, int num) {
        for (int i = index; i < (num + index) ; i++)
            map.put(String.valueOf(i), i);
    }
    public static void getPerformance2() {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 400000; i++)
            map.get(String.valueOf(i));
        long end = System.currentTimeMillis();
        System.out.println("get: it costs " + (end - start) + " ms");
    }
    public static void main(String[] args) throws InterruptedException {
        long start = System.currentTimeMillis();
        final CountDownLatch cdLatch = new CountDownLatch(4);
        for (int i = 0; i < 4; i++) {
            final int finalI = i;
            new Thread(new Runnable() {
                public void run() {
                    CompareConcurrentHashMap.putPerformance(100000 * finalI, 100000);
                    cdLatch.countDown();
                }
            }).start();
        }
        cdLatch.await();
        long end = System.currentTimeMillis();
        System.out.println("put: it costs " + (end - start) + " ms");
        CompareConcurrentHashMap.getPerformance2();
    }
}