Java并发编程之ConcurrentHashMap原理解析

简介: 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操作的时候,会进行扩容操作,而扩容时候比较耗时的,在实际应用过程中,如果需要大量数据的频繁写入,可以在初始化的时候指定一个较大的容量,避免频率扩容带来的开销。


目录
相关文章
|
1月前
|
Java
Java的CAS机制深度解析
CAS(Compare-And-Swap)是并发编程中的原子操作,用于实现多线程环境下的无锁数据同步。它通过比较内存值与预期值,决定是否更新值,从而避免锁的使用。CAS广泛应用于Java的原子类和并发包中,如AtomicInteger和ConcurrentHashMap,提升了并发性能。尽管CAS具有高性能、无死锁等优点,但也存在ABA问题、循环开销大及仅支持单变量原子操作等缺点。合理使用CAS,结合实际场景选择同步机制,能有效提升程序性能。
|
18天前
|
机器学习/深度学习 JSON Java
Java调用Python的5种实用方案:从简单到进阶的全场景解析
在机器学习与大数据融合背景下,Java与Python协同开发成为企业常见需求。本文通过真实案例解析5种主流调用方案,涵盖脚本调用到微服务架构,助力开发者根据业务场景选择最优方案,提升开发效率与系统性能。
168 0
|
14天前
|
Java 开发者
Java并发编程:CountDownLatch实战解析
Java并发编程:CountDownLatch实战解析
301 100
|
2月前
|
存储 缓存 Java
Java数组全解析:一维、多维与内存模型
本文深入解析Java数组的内存布局与操作技巧,涵盖一维及多维数组的声明、初始化、内存模型,以及数组常见陷阱和性能优化。通过图文结合的方式帮助开发者彻底理解数组本质,并提供Arrays工具类的实用方法与面试高频问题解析,助你掌握数组核心知识,避免常见错误。
|
2月前
|
缓存 安全 Java
Java并发性能优化|读写锁与互斥锁解析
本文深入解析Java中两种核心锁机制——互斥锁与读写锁,通过概念对比、代码示例及性能测试,揭示其适用场景。互斥锁适用于写多或强一致性场景,读写锁则在读多写少时显著提升并发性能。结合锁降级、公平模式等高级特性,助你编写高效稳定的并发程序。
141 0
|
9天前
|
Java 开发者
Java 函数式编程全解析:静态方法引用、实例方法引用、特定类型方法引用与构造器引用实战教程
本文介绍Java 8函数式编程中的四种方法引用:静态、实例、特定类型及构造器引用,通过简洁示例演示其用法,帮助开发者提升代码可读性与简洁性。
|
18天前
|
安全 Java API
Java SE 与 Java EE 区别解析及应用场景对比
在Java编程世界中,Java SE(Java Standard Edition)和Java EE(Java Enterprise Edition)是两个重要的平台版本,它们各自有着独特的定位和应用场景。理解它们之间的差异,对于开发者选择合适的技术栈进行项目开发至关重要。
85 1
|
2月前
|
存储 缓存 算法
Java数据类型与运算符深度解析
本文深入解析Java中容易混淆的基础知识,包括八大基本数据类型(如int、Integer)、自动装箱与拆箱机制,以及运算符(如&与&&)的使用区别。通过代码示例剖析内存布局、取值范围及常见陷阱,帮助开发者写出更高效、健壮的代码,并附有面试高频问题解析,夯实基础。
|
2月前
|
算法 Java 测试技术
零基础学 Java: 从语法入门到企业级项目实战的详细学习路线解析
本文为零基础学习者提供完整的Java学习路线,涵盖语法基础、面向对象编程、数据结构与算法、多线程、JVM原理、Spring框架、Spring Boot及项目实战,助你从入门到进阶,系统掌握Java编程技能,提升实战开发能力。
122 0

推荐镜像

更多
  • DNS