java.util.concurrent源码分析（五）ConcurrentHashMap实现

- 日理万妓 2022-05-28 01:57 67阅读 0赞

### 1、线程安全和非线程安全 ###

**引入问题：**

ArrayList和Vector有什么区别？
    HashMap和HashTable有什么区别？
    StringBuilder和StringBuffer有什么区别？
    以上是Java面试中常见的提问，众所周知，前者是非线程安全的，后者是线程安全的。
    那何为非线程安全？何为线程安全？

**线程安全：**

线程安全就是说多线程访问同一代码(临界资源)，不会产生不确定的结果(比如脏读)。
    线程安全必须要使用synchronized等来同步控制，所以必然会导致性能的降低。

### 2、ConcurrentMap VS HashTable ###

> 要实现线程安全,就需要加锁, HashTable就是线程安全的, 但是HashTable对整张表加锁的做法非常消耗性能, ConcurrentMap的做法简单来说, 就是把哈希表分成若干段, 对其中某一段操作时, 只锁住这一段, 其他段可以不受影响。

整个ConcurrentMap由一个segment数组组成(即segments),
    数组中每一个segment是一张哈希表, 哈希表中存放的是一张hashentry链表。

### 3、ConcurrentHashMap构造方法 ###

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
            if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
                throw new IllegalArgumentException();
            if (initialCapacity < concurrencyLevel)   // Use at least as many bins
                initialCapacity = concurrencyLevel;   // as estimated threads
            long size = (long)(1.0 + (long)initialCapacity / loadFactor);
            int cap = (size >= (long)MAXIMUM_CAPACITY) ?
                MAXIMUM_CAPACITY : tableSizeFor((int)size);
            this.sizeCtl = cap;
        }

### 4、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          
                     (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
                    s = ensureSegment(j);
            return s.put(key, hash, value, false);
        }

**过程:**

a.通过第一次哈希算法,计算当前key属于哪一个segment;
    b.果映射到的segment为空, 则执行3, 否则执行4;
    c.借助UNSAFE类, 使用线程安全的方式, 构建一个新的segment, 并且放入segments中相应的位置;
    d.调用segment中的put方法, 将key, value对放入segment中;

可以看到, 最终存储key,value时是对segment操作, 因此只要对需要插入键值对的segment上锁就可以保证线程安全。

### 5、Segment的put方法 ###

看segment的定义, 它是ConcurrentHashMap的内部类, 该类继承了ReentrantLock：

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

构造方法：

Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
        this.loadFactor = lf;
        this.threshold = threshold;
        this.table = tab;
    }
    //Segment的主要构成是一张哈希表(存储hashentry)和threshold(当哈希表尺寸大于threshold时扩容)

**put方法：**

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

**put流程：**

1.尝试获取当前segment的锁,若成功则执行3, 若失败则执行2;
    2.根据key在hashtable中搜索hashentry, 并且获取锁(此处会进行阻塞操作);
    3.根据key在hashtable中搜索hashentry,如果当前位置已经存在值, 则使用链接的方式解决冲突;
    4.如果当前尺寸超过了threshold,则执行rehash(将segment中的所有键值对重新hash).

**小结：**

ConcurrentHashMap的实现,主要原理就是使用segments将原本唯一的hashtable分段, 增加并发能力；
    ConcurrentHashMap中还有比较重要的一点就是使用的两次哈希算法(第一次哈希算法找到segment, 第二次哈希算法找到hashentry)；