Java源码解析之ConcurrentHashMap

早期 ConcurrentHashMap，其实现是基于：

• 分离锁，也就是将内部进行分段（Segment），里面则是 HashEntry 的数组，和 HashMap 类似，哈希相同的条目也是以链表形式存放。
• HashEntry 内部使用 volatile 的 value 字段来保证可见性，也利用了不可变对象的机制以改进利用 Unsafe 提供的底层能力，比如 volatile access，去直接完成部分操作，以最优化性能，毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的。

在进行并发操作的时候，只需要锁定相应段，这样就有效避免了类似 Hashtable 整体同步的问题，大大提高了性能。

Put操作

通过二次哈希避免哈希冲突，然后以 Unsafe 调用方式，直接获取相应的 Segment，然后进行线程安全的 put 操作

public V put(K key, V value) {

        Segment<K,V> s;

        if (value == null)

            throw new NullPointerException();

        // 二次哈希，以保证数据的分散性，避免哈希冲突

        int hash = hash(key.hashCode());

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

    }

其核心逻辑实现在下面的内部方法中：

final V put(K key, int hash, V value, boolean onlyIfAbsent) {

            // scanAndLockForPut 会去查找是否有 key 相同 Node

            // 无论如何，确保获取锁

            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;

                        // 更新已有 value...

                    }

                    else {

                        // 放置 HashEntry 到特定位置，如果超过阈值，进行 rehash

                        // ...

                    }

                }

            } finally {

                unlock();

            }

            return oldValue;

        }

在写的时候：

• ConcurrentHashMap 会获取再入锁，以保证数据一致性，Segment 本身就是基于 ReentrantLock 的扩展实现，所以，在并发修改期间，相应 Segment 是被锁定的。
• 在最初阶段，进行重复性的扫描，以确定相应 key 值是否已经在数组里面，进而决定是更新还是放置操作。
• 在 ConcurrentHashMap 中解决扩容的问题，不是整体的扩容，而是单独对 Segment 进行扩容。
• 为了减少锁定segment的开销，ConcurrentHashMap 的实现是通过重试机制（RETRIES_BEFORE_LOCK，指定重试次数 2），来试图获得可靠值。如果没有监控到发生变化（通过对比 Segment.modCount），就直接返回，否则获取锁进行操作。

机制在Java 8 上的变化：

• 总体结构上，它的内部存储与HashMap 结构非常相似，同样是大的桶（bucket）数组，然后内部也是一个个所谓的链表结构（bin），同步的粒度要更细致一些。
• 其内部仍然有 Segment 定义，但仅仅是为了保证序列化时的兼容性而已，不再有任何结构上的用处。
• 因为不再使用 Segment，初始化操作大大简化，修改为 lazy-load 形式，这样可以有效避免初始开销。
• 数据存储利用 volatile 来保证可见性。
• 使用 CAS (Compare And Swap)等操作，在特定场景进行无锁并发操作。
• 使用 Unsafe、LongAdder 之类底层手段，进行极端情况的优化。

看看在java8上的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; K fk; V fv;

        if (tab == null || (n = tab.length) == 0)

            tab = initTable();

        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {

            // 利用 CAS 去进行无锁线程安全操作，如果 bin 是空的

            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))

                break;

        }

        else if ((fh = f.hash) == MOVED)

            tab = helpTransfer(tab, f);

        else if (onlyIfAbsent // 不加锁，进行检查

                 && fh == hash

                 && ((fk = f.key) == key || (fk != null && key.equals(fk)))

                 && (fv = f.val) != null)

            return fv;

        else {

            V oldVal = null;

            synchronized (f) {

                   // 细粒度的同步修改操作...

                }

            }

            // Bin 超过阈值，进行树化

            if (binCount != 0) {

                if (binCount >= TREEIFY_THRESHOLD)

                    treeifyBin(tab, i);

                if (oldVal != null)

                    return oldVal;

                break;

            }

        }

    }

    addCount(1L, binCount);

    return null;

}

初始化操作实现在 initTable 里面，这是一个典型的 CAS 使用场景，利用 volatile 的 sizeCtl 作为互斥手段：如果发现竞争性的初始化，就 spin 在那里，等待条件恢复；否则利用 CAS 设置排他标志。如果成功则进行初始化；否则重试。

private final Node<K,V>[] initTable() {

    Node<K,V>[] tab; int sc;

    while ((tab = table) == null || tab.length == 0) {

        // 如果发现冲突，进行 spin 等待

        if ((sc = sizeCtl) < 0)

            Thread.yield();

        // CAS 成功返回 true，则进入真正的初始化逻辑

        else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {

            try {

                if ((tab = table) == null || tab.length == 0) {

                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;

                    @SuppressWarnings("unchecked")

                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];

                    table = tab = nt;

                    sc = n - (n >>> 2);

                }

            } finally {

                sizeCtl = sc;

            }

            break;

        }                                                          

    }

    return tab;

}

当 bin 为空时，同样是没有必要锁定，也是以 CAS 操作去放置。

到此这篇关于Java源码解析之ConcurrentHashMap的文章就介绍到这了,更多相关Java ConcurrentHashMap内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！