HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!(下)

简介: Map 这样的 Key Value 在软件开发中是非常经典的结构,常用于在内存中存放数据。 本篇主要想讨论 ConcurrentHashMap 这样一个并发容器,在正式开始之前我觉得有必要谈谈 HashMap,没有它就不会有后面的 ConcurrentHashMap。

Base 1.7



先来看看 1.7 的实现,下面是他的结构图:



如图所示,是由 Segment 数组、HashEntry 组成,和 HashMap 一样,仍然是数组加链表。


它的核心成员变量:


/**
     * Segment 数组,存放数据时首先需要定位到具体的 Segment 中。
     */
    final Segment<K,V>[] segments;
    transient Set<K> keySet;
    transient Set<Map.Entry<K,V>> entrySet;


Segment 是 ConcurrentHashMap 的一个内部类,主要的组成如下:


static final class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        // 和 HashMap 中的 HashEntry 作用一样,真正存放数据的桶
        transient volatile HashEntry<K,V>[] table;
        transient int count;
        transient int modCount;
        transient int threshold;
        final float loadFactor;
  }


看看其中 HashEntry 的组成:



和 HashMap 非常类似,唯一的区别就是其中的核心数据如 value ,以及链表都是 volatile 修饰的,保证了获取时的可见性。


原理上来说:ConcurrentHashMap 采用了分段锁技术,其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理,理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时,不会影响到其他的 Segment。


下面也来看看核心的 put get 方法。

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


首先是通过 key 定位到 Segment,之后在对应的 Segment 中进行具体的 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;
        }


虽然 HashEntry 中的 value 是用 volatile 关键词修饰的,但是并不能保证并发的原子性,所以 put 操作时仍然需要加锁处理。


首先第一步的时候会尝试获取锁,如果获取失败肯定就有其他线程存在竞争,则利用 scanAndLockForPut() 自旋获取锁。



  1. 尝试自旋获取锁。


  1. 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取,保证能获取成功。



再结合图看看 put 的流程。


  1. 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。


  1. 遍历该 HashEntry,如果不为空则判断传入的 key 和当前遍历的 key 是否相等,相等则覆盖旧的 value。


  1. 不为空则需要新建一个 HashEntry 并加入到 Segment 中,同时会先判断是否需要扩容。


  1. 最后会解除在 1 中所获取当前 Segment 的锁。


get 方法


public V get(Object key) {
        Segment<K,V> s; // manually integrate access methods to reduce overhead
        HashEntry<K,V>[] tab;
        int h = hash(key);
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
            (tab = s.table) != null) {
            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
                 e != null; e = e.next) {
                K k;
                if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                    return e.value;
            }
        }
        return null;
    }


get 逻辑比较简单:


只需要将 Key 通过 Hash 之后定位到具体的 Segment ,再通过一次 Hash 定位到具体的元素上。


由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的,保证了内存可见性,所以每次获取时都是最新值。


ConcurrentHashMap 的 get 方法是非常高效的,因为整个过程都不需要加锁


Base 1.8


1.7 已经解决了并发问题,并且能支持 N 个 Segment 这么多次数的并发,但依然存在 HashMap 在 1.7 版本中的问题。


那就是查询遍历链表效率太低。


因此 1.8 做了一些数据结构上的调整。


首先来看下底层的组成结构:



看起来是不是和 1.8 HashMap 结构类似?


其中抛弃了原有的 Segment 分段锁,而采用了 CAS + synchronized 来保证并发安全性。



也将 1.7 中存放数据的 HashEntry 改为 Node,但作用都是相同的。


其中的 val next 都用了 volatile 修饰,保证了可见性。


put 方法


重点来看看 put 函数:



  • 根据 key 计算出 hashcode 。


  • 判断是否需要进行初始化。


  • f 即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功。


  • 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。


  • 如果都不满足,则利用 synchronized 锁写入数据。


  • 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。


get 方法



  • 根据计算出来的 hashcode 寻址,如果就在桶上那么直接返回值。


  • 如果是红黑树那就按照树的方式获取值。


  • 就不满足那就按照链表的方式遍历获取值。


1.8 在 1.7 的数据结构上做了大的改动,采用红黑树之后可以保证查询效率(O(logn)),甚至取消了 ReentrantLock 改为了 synchronized,这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。


总结


看完了整个 HashMap 和 ConcurrentHashMap 在 1.7 和 1.8 中不同的实现方式相信大家对他们的理解应该会更加到位。


其实这块也是面试的重点内容,通常的套路是:


  1. 谈谈你理解的 HashMap,讲讲其中的 get put 过程。


  1. 1.8 做了什么优化?


  1. 是线程安全的嘛?


  1. 不安全会导致哪些问题?


  1. 如何解决?有没有线程安全的并发容器?


  1. ConcurrentHashMap 是如何实现的? 1.7、1.8 实现有何不同?为什么这么做?

这一串问题相信大家仔细看完都能怼回面试官。


除了面试会问到之外平时的应用其实也蛮多,像之前谈到的 Guava 中 Cache 的实现就是利用 ConcurrentHashMap 的思想。


同时也能学习 JDK 作者大牛们的优化思路以及并发解决方案。


其实写这篇的前提是源于 GitHub 上的一个 Issues,也希望大家能参与进来,共同维护好这个项目。


相关文章
|
6月前
|
存储 安全 算法
详解Java中HashMap、HashTable、ConcurrentHashMap常见问题
详解Java中HashMap、HashTable、ConcurrentHashMap常见问题
68 0
|
28天前
|
存储 开发者
HashMap和Hashtable的key和value可以为null吗,ConcurrentHashMap呢
HashMap的key可以为null,value也可以为null;Hashtable的key不允许为null,value也不能为null;ConcurrentHashMap的key不允许为null
|
3月前
|
存储 Java 开发者
HashMap线程安全问题大揭秘:ConcurrentHashMap、自定义同步,一文让你彻底解锁!
【8月更文挑战第24天】HashMap是Java集合框架中不可或缺的一部分,以其高效的键值对存储和快速访问能力广受开发者欢迎。本文深入探讨了HashMap在JDK 1.8后的底层结构——数组+链表+红黑树混合模式,这种设计既利用了数组的快速定位优势,又通过链表和红黑树有效解决了哈希冲突问题。数组作为基石,每个元素包含一个Node节点,通过next指针形成链表;当链表长度过长时,采用红黑树进行优化,显著提升性能。此外,还介绍了HashMap的扩容机制,确保即使在数据量增大时也能保持高效运作。通过示例代码展示如何使用HashMap进行基本操作,帮助理解其实现原理及应用场景。
51 1
|
3月前
|
安全 Java
【Java集合类面试十六】、HashMap与ConcurrentHashMap有什么区别?
HashMap是非线程安全的,而ConcurrentHashMap通过减少锁粒度来提高并发性能,检索操作无需锁,从而提供更好的线程安全性和性能。
|
3月前
|
开发者 C# UED
WPF与多媒体:解锁音频视频播放新姿势——从界面设计到代码实践,全方位教你如何在WPF应用中集成流畅的多媒体功能
【8月更文挑战第31天】本文以随笔形式介绍了如何在WPF应用中集成音频和视频播放功能。通过使用MediaElement控件,开发者能轻松创建多媒体应用程序。文章详细展示了从创建WPF项目到设计UI及实现媒体控制逻辑的过程,并提供了完整的示例代码。此外,还介绍了如何添加进度条等额外功能以增强用户体验。希望本文能为WPF开发者提供实用的技术指导与灵感。
136 0
|
4月前
|
安全 Java
多线程线程安全问题之避免ThreadLocal的内存泄漏,如何解决
多线程线程安全问题之避免ThreadLocal的内存泄漏,如何解决
|
4月前
|
存储 安全 Java
Java面试题:请解释Java内存模型,并说明如何在多线程环境下使用synchronized关键字实现同步,阐述ConcurrentHashMap与HashMap的区别,以及它如何在并发环境中提高性能
Java面试题:请解释Java内存模型,并说明如何在多线程环境下使用synchronized关键字实现同步,阐述ConcurrentHashMap与HashMap的区别,以及它如何在并发环境中提高性能
36 0
|
6月前
|
存储 C++
为什么HashMap的键值可以为null,而ConcurrentHashMap不行?
为什么HashMap的键值可以为null,而ConcurrentHashMap不行?
83 1
|
6月前
|
安全 Java 调度
HashMap很美好,但线程不安全怎么办?ConcurrentHashMap告诉你答案!
HashMap很美好,但线程不安全怎么办?ConcurrentHashMap告诉你答案!
95 1
|
6月前
|
存储 并行计算 安全
【Java编程进阶之路 01】深入探索:HashMap、ConcurrentHashMap与HashTable的演进之路
HashMap、ConcurrentHashMap与HashTable均为Java中的哈希表实现。HashMap非线程安全但性能高,适用于单线程;HashTable线程安全但性能较低,已少用;ConcurrentHashMap线程安全且高性能,是并发环境下的首选。三者在线程安全性与性能间各有侧重。
65 1