`
san_yun
  • 浏览: 2654830 次
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

ConcurrentHashMap 的实现原理

 
阅读更多

概述

我们在之前的博文中了解到关于 HashMap 和 Hashtable 这两种集合。其中 HashMap 是非线程安全的,当我们只有一个线程在使用 HashMap 的时候,自然不会有问题,但如果涉及到多个线程,并且有读有写的过程中,HashMap 就不能满足我们的需要了(fail-fast)。在不考虑性能问题的时候,我们的解决方案有 Hashtable 或者Collections.synchronizedMap(hashMap),这两种方式基本都是对整个 hash 表结构做锁定操作的,这样在锁表的期间,别的线程就需要等待了,无疑性能不高。

所以我们在本文中学习一个 util.concurrent 包的重要成员,ConcurrentHashMap。

ConcurrentHashMap 的实现是依赖于 Java 内存模型,所以我们在了解 ConcurrentHashMap 的前提是必须了解Java 内存模型。但 Java 内存模型并不是本文的重点,所以我假设读者已经对 Java 内存模型有所了解。

ConcurrentHashMap 分析

ConcurrentHashMap 的结构是比较复杂的,都深究去本质,其实也就是数组和链表而已。我们由浅入深慢慢的分析其结构。

先简单分析一下,ConcurrentHashMap 的成员变量中,包含了一个 Segment 的数组(final Segment<K,V>[] segments;),而 Segment 是 ConcurrentHashMap 的内部类,然后在 Segment 这个类中,包含了一个 HashEntry 的数组(transient volatile HashEntry<K,V>[] table;)。而 HashEntry 也是 ConcurrentHashMap 的内部类。HashEntry 中,包含了 key 和 value 以及 next 指针(类似于 HashMap 中 Entry),所以 HashEntry 可以构成一个链表。

所以通俗的讲,ConcurrentHashMap 数据结构为一个 Segment 数组,Segment 的数据结构为 HashEntry 的数组,而 HashEntry 存的是我们的键值对,可以构成链表。

首先,我们看一下 HashEntry 类。

HashEntry

HashEntry 用来封装散列映射表中的键值对。在 HashEntry 类中,key,hash 和 next 域都被声明为 final 型,value 域被声明为 volatile 型。其类的定义为:

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        ...
        ...
}

HashEntry 的学习可以类比着 HashMap 中的 Entry。我们的存储键值对的过程中,散列的时候如果发生“碰撞”,将采用“分离链表法”来处理碰撞:把碰撞的 HashEntry 对象链接成一个链表。

如下图,我们在一个空桶中插入 A、B、C 两个 HashEntry 对象后的结构图(其实应该为键值对,在这进行了简化以方便更容易理解):

图1

Segment

Segment 的类定义为static final class Segment<K,V> extends ReentrantLock implements Serializable。其继承于 ReentrantLock 类,从而使得 Segment 对象可以充当锁的角色。Segment 中包含HashEntry 的数组,其可以守护其包含的若干个桶(HashEntry的数组)。Segment 在某些意义上有点类似于 HashMap了,都是包含了一个数组,而数组中的元素可以是一个链表。

table:table 是由 HashEntry 对象组成的数组如果散列时发生碰撞,碰撞的 HashEntry 对象就以链表的形式链接成一个链表table数组的数组成员代表散列映射表的一个桶每个 table 守护整个 ConcurrentHashMap 包含桶总数的一部分如果并发级别为 16,table 则守护 ConcurrentHashMap 包含的桶总数的 1/16。

count 变量是计算器,表示每个 Segment 对象管理的 table 数组(若干个 HashEntry 的链表)包含的HashEntry 对象的个数。之所以在每个Segment对象中包含一个 count 计数器,而不在 ConcurrentHashMap 中使用全局的计数器,是为了避免出现“热点域”而影响并发性。

/**
     * Segments are specialized versions of hash tables.  This
     * subclasses from ReentrantLock opportunistically, just to
     * simplify some locking and avoid separate construction.
     */
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
      /**
         * The per-segment table. Elements are accessed via
         * entryAt/setEntryAt providing volatile semantics.
         */
        transient volatile HashEntry<K,V>[] table;

        /**
         * The number of elements. Accessed only either within locks
         * or among other volatile reads that maintain visibility.
         */
        transient int count;
        transient int modCount;
        /**
         * 装载因子
         */
        final float loadFactor;
    }

我们通过下图来展示一下插入 ABC 三个节点后,Segment 的示意图:

图2

其实从我个人角度来说,Segment结构是与HashMap很像的。

ConcurrentHashMap

ConcurrentHashMap 的结构中包含的 Segment 的数组,在默认的并发级别会创建包含 16 个 Segment 对象的数组。通过我们上面的知识,我们知道每个 Segment 又包含若干个散列表的桶,每个桶是由 HashEntry 链接起来的一个链表。如果 key 能够均匀散列,每个 Segment 大约守护整个散列表桶总数的 1/16。

下面我们还有通过一个图来演示一下 ConcurrentHashMap 的结构:

图3

并发写操作

在 ConcurrentHashMap 中,当执行 put 方法的时候,会需要加锁来完成。我们通过代码来解释一下具体过程: 当我们 new 一个 ConcurrentHashMap 对象,并且执行put操作的时候,首先会执行 ConcurrentHashMap 类中的 put 方法,该方法源码为:

/**
     * Maps the specified key to the specified value in this table.
     * Neither the key nor the value can be null.
     *
     * <p> The value can be retrieved by calling the <tt>get</tt> method
     * with a key that is equal to the original key.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>
     * @throws NullPointerException if the specified key or value is null
     */
    @SuppressWarnings("unchecked")
    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);
    }

我们通过注释可以了解到,ConcurrentHashMap 不允许空值。该方法首先有一个 Segment 的引用 s,然后会通过 hash() 方法对 key 进行计算,得到哈希值;继而通过调用 Segment 的 put(K key, int hash, V value, boolean onlyIfAbsent)方法进行存储操作。该方法源码为:

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    //加锁,这里是锁定的Segment而不是整个ConcurrentHashMap
    HashEntry<K,V> node = tryLock() ? null :scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        //得到hash对应的table中的索引index
        int index = (tab.length - 1) & hash;
        //找到hash对应的是具体的哪个桶,也就是哪个HashEntry链表
        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;
}

关于该方法的某些关键步骤,在源码上加上了注释。

需要注意的是:加锁操作是针对的 hash 值对应的某个 Segment,而不是整个 ConcurrentHashMap。因为 put 操作只是在这个 Segment 中完成,所以并不需要对整个 ConcurrentHashMap 加锁。所以,此时,其他的线程也可以对另外的 Segment 进行 put 操作,因为虽然该 Segment 被锁住了,但其他的 Segment 并没有加锁。同时,读线程并不会因为本线程的加锁而阻塞。

正是因为其内部的结构以及机制,所以 ConcurrentHashMap 在并发访问的性能上要比Hashtable和同步包装之后的HashMap的性能提高很多。在理想状态下,ConcurrentHashMap 可以支持 16 个线程执行并发写操作(如果并发级别设置为 16),及任意数量线程的读操作。

总结

在实际的应用中,散列表一般的应用场景是:除了少数插入操作和删除操作外,绝大多数都是读取操作,而且读操作在大多数时候都是成功的。正是基于这个前提,ConcurrentHashMap 针对读操作做了大量的优化。通过 HashEntry 对象的不变性和用 volatile 型变量协调线程间的内存可见性,使得 大多数时候,读操作不需要加锁就可以正确获得值。这个特性使得 ConcurrentHashMap 的并发性能在分离锁的基础上又有了近一步的提高。

ConcurrentHashMap 是一个并发散列映射表的实现,它允许完全并发的读取,并且支持给定数量的并发更新。相比于 HashTable 和用同步包装器包装的 HashMap(Collections.synchronizedMap(new HashMap())),ConcurrentHashMap 拥有更高的并发性。在 HashTable 和由同步包装器包装的 HashMap 中,使用一个全局的锁来同步不同线程间的并发访问。同一时间点,只能有一个线程持有锁,也就是说在同一时间点,只能有一个线程能访问容器。这虽然保证多线程间的安全并发访问,但同时也导致对容器的访问变成串行化的了。

ConcurrentHashMap 的高并发性主要来自于三个方面:

  • 用分离锁实现多个线程间的更深层次的共享访问。
  • 用 HashEntery 对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求。
  • 通过对同一个 Volatile 变量的写 / 读访问,协调不同线程间读 / 写操作的内存可见性。

使用分离锁,减小了请求 同一个锁的频率。

通过 HashEntery 对象的不变性及对同一个 Volatile 变量的读 / 写来协调内存可见性,使得 读操作大多数时候不需要加锁就能成功获取到需要的值。由于散列映射表在实际应用中大多数操作都是成功的 读操作,所以 2 和 3 既可以减少请求同一个锁的频率,也可以有效减少持有锁的时间。通过减小请求同一个锁的频率和尽量减少持有锁的时间 ,使得 ConcurrentHashMap 的并发性相对于 HashTable 和用同步包装器包装的 HashMap有了质的提高。

 
分享到:
评论

相关推荐

    程序员面试加薪必备:ConcurrentHashMap底层原理与源码分析深入详解

    程序员面试加薪必备_ConcurrentHashMap底层原理与源码分析深入详解

    ConcurrentHashMap的实现原理

    ConcurrentHashMap 的实现原理 ConcurrentHashMap 是 Java 中一个高效的线程安全的哈希表实现,它的实现原理可以分为两部分:JDK1.7 中的实现和 JDK8 中的实现。 JDK1.7 中的实现 在 JDK1.7 中,...

    ConcurrentHashMap的实现原理(JDK1.7和JDK1.8).pdf

    在理解`ConcurrentHashMap`的实现原理之前,我们先来看看哈希表的基本概念。 哈希表是一种键值对存储的数据结构,通过键(key)进行索引,可以高效地查找、插入和删除数据。如果键是整数,我们可以直接用它作为数组...

    【面试普通人VS高手系列】ConcurrentHashMap 底层具体实现知道吗?实现原理是什么?.doc

    ConcurrentHashMap 底层实现原理和优化策略 ConcurrentHashMap 是 Java 中一个常用的线程安全的 Hash 表实现,今天我们来讨论 ConcurrentHashMap 底层实现原理和优化策略。 ConcurrentHashMap 的整体架构 ...

    Java并发编程笔记之ConcurrentHashMap原理探究.docx

    在Java 7之前,ConcurrentHashMap主要依赖于Segment上的ReentrantLock来实现同步。每个Segment都有一个内部锁,当进行写操作时,会锁定对应Segment,读操作则不需要锁定。而从Java 8开始,ConcurrentHashMap改用CAS...

    ConcurrentHashMap之实现细节

    ### ConcurrentHashMap实现细节详解 #### 一、概述 `ConcurrentHashMap`是Java 5引入的一种高性能、线程安全的散列表实现。相较于传统的`HashMap`,`ConcurrentHashMap`能够支持高并发环境下的多线程读写操作。...

    Java中的ConcurrentHashMap:线程安全的哈希表实现与代码示例

    本文将深入探讨 ConcurrentHashMap 的内部实现原理,并通过代码示例展示其使用方法和优势。 通过本文,我们深入探讨了 ConcurrentHashMap 的内部实现原理,包括分段锁、CAS操作和红黑树等技术。此外,我们还通过代码...

    ConcurrentHashMap底层实现机制的分析1

    在本文中,我们将深入探索 ConcurrentHashMap 的高并发实现机制,并分析其在 Java 内存模型基础上的实现原理。了解 ConcurrentHashMap 的实现机制有助于我们更好地理解 Java 并发编程的原理和技术。 一、Java 内存...

    大厂的Android面试题.pdf

    17. **HashMap与ConcurrentHashMap实现原理** - HashMap不支持多线程安全操作,而ConcurrentHashMap通过锁分离技术实现了线程安全。 18. **BroadcastReceiver与LocalBroadcastReceiver区别** - BroadcastReceiver...

    阿里巴巴 面经

    ConcurrentHashMap实现原理** - 使用分段锁实现线程安全。 **21. Error与Exception的区别** - **Error**:通常表示程序无法处理的情况,比如虚拟机错误等。 - **Exception**:表示程序中可能发生的问题,但可以...

    java源码剖析-ConcurrentHashMap

    #### 六、`ConcurrentHashMap`的工作原理 1. **定位元素**:`ConcurrentHashMap`采用两次哈希来定位元素。第一次哈希定位到具体的`Segment`,第二次哈希则定位到该`Segment`内的`HashEntry`链表头部。 2. **写操作*...

    java7-8中的 HashMap和ConcurrentHashMap全解析

    本文将深入解析这两个类在Java 7和8版本中的实现原理、特点以及使用场景。 首先,`HashMap`是Java中最基本的非线程安全的散列映射容器。它基于哈希表实现,提供O(1)的平均时间复杂度进行插入、删除和查找操作。在...

    安卓java读取网页源码-interview:安卓面试

    自动装箱实现原理?类型转换实现原理? 对 String 的了解? String 为什么要设计成不可变的? 列举 Java 的集合以及集合之间的继承关系? List、Set、Map 的区别? HashMap,HashTable,ConcurrentHashMap 实现原理...

    ConcurrentHashMap源码剖析

    本文将深入探讨ConcurrentHashMap的内部结构、工作原理及其在实际场景中的应用。 #### 二、结构解析 **1. 锁分段技术** ConcurrentHashMap的核心思想是将一个大哈希表分割成多个小哈希表(称为段,Segment),每...

    第10讲 如何保证集合是线程安全的 ConcurrentHashMap如何实现高效地线程安全1

    在面试或实际开发中,理解ConcurrentHashMap的工作原理是非常重要的。面试官可能会询问关于它的内部实现,如Segment和HashEntry的结构,以及如何通过CAS操作避免锁竞争。此外,还需要了解从Java 5到Java 8,...

    深入Java集合学习系列:HashMap的实现原理

    在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...

    Java 中ConcurrentHashMap的实现

    Java中的`ConcurrentHashMap`是Java 1.5版本引入的一种高效、线程安全的Map实现,它是`Hashtable`和`synchronized Map`的有力替代品。`ConcurrentHashMap`不仅保证了线程安全性,而且在多线程环境下的性能表现优于...

    ConcurrentHashMap思维导图完整版

    分析JDK源代码,探索ConcurrentHashMap高并发的具体实现机制,包括其在JDK中的定义和结构、并发存取、重哈希和跨段操作,并着重剖析了ConcurrentHashMap读操作不需要加锁和分段锁机制的内在奥秘和原理。

    高薪程序员面试题精讲系列49之说说ConcurrentHashMap#put方法的源码及数。。。.pdf,这是一份不错的文件

    在面试中,ConcurrentHashMap的底层原理、put方法的实现细节都是高频考点。本文将对ConcurrentHashMap#put方法的源码进行详细分析,从而帮助读者更好地理解ConcurrentHashMap的工作机理。 一、ConcurrentHashMap的...

Global site tag (gtag.js) - Google Analytics