Java集合-ConcurrentHashMap

前面通过分析HashMap的数据结构发现，HashMap通过Hash表和链表的结构构成的一个数据结构，当有两个hash值相同的数据需要并发插入（删除）时，可能会造成数据丢失的情况。那么HashTable的存在就是为了保证Map的线程安全的，但是，当Hashtable操作数据时，是将整个table都加入Sync，造成全部数据同时lock，效率比较低。

HashMap和HashTable结构

!

那么ConcurrentHashMap在并发方面对数据结构做了微调，同时结合了并发操作进行了一些算法改进。首先看一下ConcurrentHashMap的数据结构：

ConcurrentHashMap结构【摘自网络】

那么可以看出，他在HashTable的table结构上再加了一层segment，ConcurrentHashMap就是通过加入多一层的segment，通过锁去独立控制每一个segment，来优化数据不用同时lock。
看一下segment的定义：

final Segment<K,V>[] segments;
static final class Segment<K,V> extends ReentrantLock implements Serializable{
    
    ... ...
}

其中Segment<K,V>继承了ReentrantLock（重入锁，后续开文详细分析），那么每一个segment都有一个单独的lock进行管理和分配。
Segment<K,V>实现的是一个类似HashMap的结构，如上图可以看出，其实ConcurrentHashMap就是定义了一层Segment来包含每个单独的HashMap，也可以肤浅的认为，ConcurrentHashMap就是由多个HashTable构成的（每个HashTable独立控制自己的锁）。

那么，数据通过怎么样落入到不同的segment中呢？这里同样是使用hash算法进行segment的选择：

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

一眼看上去，好长，不就一个hash算法么，为什么会这么复杂，注释中还涉及到了 Wang/Jenkins的hash算法。如果不详细探讨这个hash算法的数据理论的话，可以简单的这么理解：如果使用一般的hash算法，有可能造成很多的值同时落到一个segment中，那么最终这些数据都公用这个segment中的lock，那么多一层segments的结构就起不到独立锁的目的；所以这个算法就是用来调和让每个segment都能落入接近数量的数据，让segments层的lock真正独立起来。

我们来看一下ConcurrentHashMap是怎么实现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);
}

可以看到，他是通过hash算法先找到对应的segment，然后交由这个segement去处理put方法，看一下segment的put方法：

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);
    ... ...
}

这里先通过ReentrantLock获取锁。然后，通过hash值计算，得到table的bucket中的链表 ，在获取链表的第一个元素：

HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);

然后，看一下如果这个bucket为空的即链表为空的情况：

setEntryAt(tab, index, node);

将此对象设为header，并将header放入table中，如果bucket不为空时：

e = e.next;

类似hashmap的结构，把table的header换成当前，并将当前的next指针指向原来的header。

putentry

ConcurrentHashMap暂时分析到这里，后续分析并发编程再重新回来分析这里的并发编程的技术。