Java并发编程之ConcurrentHashMap原理解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: Java并发编程之ConcurrentHashMap原理解析

ConcurrentHashMap



  1. get


/**
 *  根据键值key获取value,根据key.equals方法判断两个元素是否相同
 *  @param key 键
 *  @return 如果key存在则返回对应的value,否则返回null
 */
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //将key的hashcode进一步散列,减少hash碰撞
    int h = spread(key.hashCode());
    //具体的元素信息是存在Node[]数组中,先判断key对应hash值映射到数组元素的位置释放有值
    //如果对应的数组位置没有值,直接返回null,否则继续判断
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //如果当前数组位置的元素的hash值和key值均相等,则直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //如果hash值为负数,说明相同hash值的元素组成了红黑树,则直接在红黑数内部查找:TreeBin.find
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        //有相同hash值(发生了hash碰撞)的元素组成一个链表,依次在链表中查询目标元素
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}


可以看到get操作完全没有加锁,那么多线程操作的时候如何保证正确性呢?通过上面get操作的源码可以看到,每一个key,value会被封装成一个Node,继续看Node的源码。


2.Node:


static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //value为volatile类型的,从而保证了多线程读写的可见性
    volatile V val;
    //发生hash碰撞时,记录下一个元素,类型也是volatile的,从而保证可见性
    volatile Node<K,V> next;
    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
}


这里ConcurrentHashMap是使用volatile来保证多线程操作的可见性的,从而避免了加锁逻辑。


3.put:


public V put(K key, V value) {
    //具体的实现逻辑在putVal
    return putVal(key, value, false);
}
/**
  * 将key,value键值对放入到map中
  * @param key 键
  * @param value 值
  * @return 如果先前key的位置有值,则返回老的值,否则返回null
  */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    //可以看到ConcurrentHashMap的key和value都不允许为null
    if (key == null || value == null) throw new NullPointerException();
    //将key的hashcode进一步散列,减少hash碰撞
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //记录元素的Node数组为null时要先进行初始化
        if (tab == null || (n = tab.length) == 0)
            //初始化table,见下文分析
            tab = initTable();
        //如果当前位置为null,可以直接放入元素
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //CAS写入元素,如果成功则返回;CAS失败说明有另外的线程在进行put操作,需要自旋等待
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //数组在扩容中
        else if ((fh = f.hash) == MOVED)
            //当前线程帮助执行扩容操作,将数组划分执行数据移动
            tab = helpTransfer(tab, f);
        else {//当前数组位置已经有值了
            V oldVal = null;
            //对当前节点加锁,防止其他线程并发更新
            synchronized (f) {
                if (tabAt(tab, i) == f) {//防止其他线程更改tabb在i位置的值,如果发生更新则继续循环
                    if (fh >= 0) {//hash值相同的节点为链表
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //如果找到key值相同的节点,说明需要更新数据
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                //保存原来的值
                                oldVal = e.val;
                                //putIfAbsent?
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            //更新节点的next节点为新加入的节点
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    //如果hash值相同的节点为红黑树,则在红黑树内部执行节点新增或者更新逻辑
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            //hash值相同的元素个数>0
            if (binCount != 0) {
                //节点超过8个,若<64则扩容链表,否则从链表转化为红黑树,提升查询效率
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    //增加数组元素个数,并判断是否需要扩容,若需要则进行扩容操作
    addCount(1L, binCount);
    return null;
}
/**
  * 初始化Node数组
  */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    //数组为空时,持续循环
    while ((tab = table) == null || tab.length == 0) {
        //sc == -1,说明有多个线程同时在执行初始化操作,此线程竞争失败,让出cpu执行权
        if ((sc = sizeCtl) < 0)
            Thread.yield(); //让出cpu控制权,自旋等待
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//cas成功,进行初始化,并将sizectl的值设置为-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;
}


4.总结:可以看到ConcurrentHashMap的get操作完全没有加锁,put操作只有在hash碰撞的时候才会在冲突节点上加上Sychronized锁,整体的效率是非常高的。另外,需要注意的是:在执行put操作的时候,会进行扩容操作,而扩容时候比较耗时的,在实际应用过程中,如果需要大量数据的频繁写入,可以在初始化的时候指定一个较大的容量,避免频率扩容带来的开销。


目录
打赏
0
0
0
0
4
分享
相关文章
Java中Log级别和解析
日志级别定义了日志信息的重要程度,从低到高依次为:TRACE(详细调试)、DEBUG(开发调试)、INFO(一般信息)、WARN(潜在问题)、ERROR(错误信息)和FATAL(严重错误)。开发人员可根据需要设置不同的日志级别,以控制日志输出量,避免影响性能或干扰问题排查。日志框架如Log4j 2由Logger、Appender和Layout组成,通过配置文件指定日志级别、输出目标和格式。
Java二维数组的使用技巧与实例解析
本文详细介绍了Java中二维数组的使用方法
49 15
深潜数据海洋:Java文件读写全面解析与实战指南
通过本文的详细解析与实战示例,您可以系统地掌握Java中各种文件读写操作,从基本的读写到高效的NIO操作,再到文件复制、移动和删除。希望这些内容能够帮助您在实际项目中处理文件数据,提高开发效率和代码质量。
12 0
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
68 6
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
138 2
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
101 1
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
87 0
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
创建型模式的主要关注点是“怎样创建对象?”,它的主要特点是"将对象的创建与使用分离”。这样可以降低系统的耦合度,使用者不需要关注对象的创建细节。创建型模式分为5种:单例模式、工厂方法模式抽象工厂式、原型模式、建造者模式。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分派行为,后者采用组合或聚合在对象间分配行为。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象行为模式比类行为模式具有更大的灵活性。 行为型模式分为: • 模板方法模式 • 策略模式 • 命令模式 • 职责链模式 • 状态模式 • 观察者模式 • 中介者模式 • 迭代器模式 • 访问者模式 • 备忘录模式 • 解释器模式
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式,前者采用继承机制来组织接口和类,后者釆用组合或聚合来组合对象。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象结构型模式比类结构型模式具有更大的灵活性。 结构型模式分为以下 7 种: • 代理模式 • 适配器模式 • 装饰者模式 • 桥接模式 • 外观模式 • 组合模式 • 享元模式
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等