文档章节

Java并发编程总结4——ConcurrentHashMap在jdk1.8中的改进

tantexian
 tantexian
发布于 2016/11/22 22:46
字数 1553
阅读 36
收藏 2
点赞 0
评论 0

Java并发编程总结4——ConcurrentHashMap在jdk1.8中的改进

一、简单回顾ConcurrentHashMap在jdk1.7中的设计

    先简单看下ConcurrentHashMap类在jdk1.7中的设计,其基本结构如图所示:

每一个segment都是一个HashEntry<K,V>[] table, table中的每一个元素本质上都是一个HashEntry的单向队列。比如table[3]为首节点,table[3]->next为节点1,之后为节点2,依次类推。

复制代码

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {

    // 将整个hashmap分成几个小的map,每个segment都是一个锁;与hashtable相比,这么设计的目的是对于put, remove等操作,可以减少并发冲突,对
    // 不属于同一个片段的节点可以并发操作,大大提高了性能
    final Segment<K,V>[] segments;

    // 本质上Segment类就是一个小的hashmap,里面table数组存储了各个节点的数据,继承了ReentrantLock, 可以作为互拆锁使用
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
        transient volatile HashEntry<K,V>[] table;
        transient int count;
    }

    // 基本节点,存储Key, Value值
    static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
    }
}

复制代码

 

二、在jdk1.8中主要做了2方面的改进

改进一:取消segments字段,直接采用transient volatile HashEntry<K,V>[] table保存数据,采用table数组元素作为锁,从而实现了对每一行数据进行加锁,进一步减少并发冲突的概率。

改进二:将原先table数组+单向链表的数据结构,变更为table数组+单向链表+红黑树的结构。对于hash表来说,最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀,那么table数组中的每个队列长度主要为0或者1。但实际情况并非总是如此理想,虽然ConcurrentHashMap类默认的加载因子为0.75,但是在数据量过大或者运气不佳的情况下,还是会存在一些队列长度过长的情况,如果还是采用单向列表方式,那么查询某个节点的时间复杂度为O(n);因此,对于个数超过8(默认值)的列表,jdk1.8中采用了红黑树的结构,那么查询的时间复杂度可以降低到O(logN),可以改进性能。

为了说明以上2个改动,看一下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;
        // 如果table为空,初始化;否则,根据hash值计算得到数组索引i,如果tab[i]为空,直接新建节点Node即可。注:tab[i]实质为链表或者红黑树的首节点。
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // 如果tab[i]不为空并且hash值为MOVED,说明该链表正在进行transfer操作,返回扩容完成后的table。
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 针对首个节点进行加锁操作,而不是segment,进一步减少线程冲突
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果在链表中找到值为key的节点e,直接设置e.val = value即可。
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            // 如果没有找到值为key的节点,直接新建Node并加入链表即可。
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    // 如果首节点为TreeBin类型,说明为红黑树结构,执行putTreeVal操作。
                    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;
                        }
                    }
                }
            }
            if (binCount != 0) {
                // 如果节点数>=8,那么转换链表结构为红黑树结构。
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 计数增加1,有可能触发transfer操作(扩容)。
    addCount(1L, binCount);
    return null;
}

复制代码

另外,在其他方面也有一些小的改进,比如新增字段 transient volatile CounterCell[] counterCells; 可方便的计算hashmap中所有元素的个数,性能大大优于jdk1.7中的size()方法。

 

三、ConcurrentHashMap jdk1.7、jdk1.8性能比较

测试程序如下:

复制代码

public class CompareConcurrentHashMap {
    private static ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<String, Integer>(40000);


    public static void putPerformance(int index, int num) {
        for (int i = index; i < (num + index) ; i++)
            map.put(String.valueOf(i), i);
    }
public static void getPerformance2() {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 400000; i++)
            map.get(String.valueOf(i));
        long end = System.currentTimeMillis();
        System.out.println("get: it costs " + (end - start) + " ms");
    }

    public static void main(String[] args) throws InterruptedException {
        long start = System.currentTimeMillis();
        final CountDownLatch cdLatch = new CountDownLatch(4);
        for (int i = 0; i < 4; i++) {
            final int finalI = i;
            new Thread(new Runnable() {
                public void run() {
                    CompareConcurrentHashMap.putPerformance(100000 * finalI, 100000);
                    cdLatch.countDown();
                }
            }).start();
        }
        cdLatch.await();
        long end = System.currentTimeMillis();
        System.out.println("put: it costs " + (end - start) + " ms");
        CompareConcurrentHashMap.getPerformance2();
    }
}

复制代码

程序运行多次后取平均值,结果如下:

 

四、Collections.synchronizedList和CopyOnWriteArrayList性能分析

CopyOnWriteArrayList在线程对其进行变更操作的时候,会拷贝一个新的数组以存放新的字段,因此写操作性能很差;而Collections.synchronizedList读操作采用了synchronized,因此读性能较差。以下为测试程序:

复制代码

public class App {
    private static List<String> arrayList = Collections.synchronizedList(new ArrayList<String>());
    private static List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<String>();
    private static CountDownLatch cdl1 = new CountDownLatch(2);
    private static CountDownLatch cdl2 = new CountDownLatch(2);
    private static CountDownLatch cdl3 = new CountDownLatch(2);
    private static CountDownLatch cdl4 = new CountDownLatch(2);

    static class Thread1 extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < 10000; i++)
                arrayList.add(String.valueOf(i));
            cdl1.countDown();
        }
    }

    static class Thread2 extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < 10000; i++)
                copyOnWriteArrayList.add(String.valueOf(i));
            cdl2.countDown();
        }
    }

    static class Thread3 extends Thread1 {
        @Override
        public void run() {
            int size = arrayList.size();
            for (int i = 0; i < size; i++)
                arrayList.get(i);
            cdl3.countDown();
        }
    }

    static class Thread4 extends Thread1 {
        @Override
        public void run() {
            int size = copyOnWriteArrayList.size();
            for (int i = 0; i < size; i++)
                copyOnWriteArrayList.get(i);
            cdl4.countDown();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        long start1 = System.currentTimeMillis();
        new Thread1().start();
        new Thread1().start();
        cdl1.await();
        System.out.println("arrayList add: " + (System.currentTimeMillis() - start1));

        long start2 = System.currentTimeMillis();
        new Thread2().start();
        new Thread2().start();
        cdl2.await();
        System.out.println("copyOnWriteArrayList add: " + (System.currentTimeMillis() - start2));

        long start3 = System.currentTimeMillis();
        new Thread3().start();
        new Thread3().start();
        cdl3.await();
        System.out.println("arrayList get: " + (System.currentTimeMillis() - start3));

        long start4 = System.currentTimeMillis();
        new Thread4().start();
        new Thread4().start();
        cdl4.await();
        System.out.println("copyOnWriteArrayList get: " + (System.currentTimeMillis() - start4));
    }
}

复制代码

结果如下:

 

标签: Java并发编程总结

« 上一篇:Java并发编程总结3——AQS、ReentrantLock、ReentrantReadWriteLock
» 下一篇:Java并发编程总结5——ThreadPoolExecutor

 

本文转载自:

共有 人打赏支持
tantexian
粉丝 191
博文 467
码字总数 717645
作品 0
成都
架构师
2018年Java编程学习面试最全知识点总结

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/14 ⋅ 0

[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin ⋅ 05/25 ⋅ 0

Java 多线程编程 — 锁优化2

Java多线程编程-(13)- 关于锁优化的几点建议 一、背景 在《 Java多线程编程-(11)-从volatile和synchronized的底层实现原理看Java虚拟机对锁优化所做的努力》 这一篇文章中,我们大致介绍...

晨猫 ⋅ 04/26 ⋅ 0

ConcurrentHashMap基于JDK1.8源码剖析

前言 声明,本文用的是jdk1.8 前面章节回顾: Collection总览 List集合就这么简单【源码剖析】 Map集合、散列表、红黑树介绍 HashMap就是这么简单【源码剖析】 LinkedHashMap就这么简单【源码...

Java3y ⋅ 04/14 ⋅ 0

Java 使用 happen-before 规则实现共享变量的同步操作

前言 熟悉 Java 并发编程的都知道,JMM(Java 内存模型) 中的 happen-before(简称 hb)规则,该规则定义了 Java 多线程操作的有序性和可见性,防止了编译器重排序对程序结果的影响。按照官方的...

stateIs0 ⋅ 01/20 ⋅ 0

一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb ⋅ 05/08 ⋅ 0

Java面试需要准备哪些多线程并发的技术要点

一、概念 什么是线程 一个线程要执行任务,必须得有线程 一个进程(程序)的所有任务都在线程中执行的 一个线程执行任务是串行的,也就是说一个线程,同一时间内,只能执行一个任务 多线程原理 同一...

码蚁说架构 ⋅ 05/31 ⋅ 0

【Java并发专题】27篇文章详细总结Java并发基础知识

努力的意义,就是,在以后的日子里,放眼望去全是自己喜欢的人和事! github:https://github.com/CL0610/Java-concurrency,欢迎题issue和Pull request。所有的文档都是自己亲自码的,如果觉...

你听___ ⋅ 05/06 ⋅ 0

书单丨5本Java后端技术书指引你快速进阶

一名Java开发工程师 不仅要对Java语言及特性有深层次的理解 而且需要掌握与Java相关的 框架、生态及后端开发知识 本文涉及多种后端开发需要掌握的技能 对于帮助提高开发能力非常有帮助 NO.1...

Java高级架构 ⋅ 05/30 ⋅ 0

Java8——重新认识HashMap

摘要 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩...

木云凌 ⋅ 05/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 20分钟前 ⋅ 0

VS2015配置并运行汇编(一步一步照图做)【vs2017的链接在最后】

前言 我是上学期学的汇编,因为有vs又不想用课上教的麻烦的dosbox以及masm32,但是一直没找到高亮插件和能调试的(难在运行不了而找不到答案上,出现的错误在最后放出,还请先达们不吝指点)...

simpower ⋅ 30分钟前 ⋅ 0

一起读书《深入浅出nodejs》-node模块机制

node 模块机制 前言 说到node,就不免得提到JavaScript。JavaScript自诞生以来,经历了工具类库、组件库、前端框架、前端应用的变迁。通过无数开发人员的努力,JavaScript不断被类聚和抽象,...

小草先森 ⋅ 33分钟前 ⋅ 0

Java桌球小游戏

其实算不上一个游戏,就是两张图片,不停的重画,改变ball图片的位置。一个左右直线碰撞的,一个有角度碰撞的。 左右直线碰撞 package com.bjsxt.test;import javax.swing.*;import j...

森林之下 ⋅ 40分钟前 ⋅ 0

你真的明白RPC 吗?一起来探究 RPC 的实质

你真的明白RPC 吗?一起来探究 RPC 的实质 不论你是科班出身还是半路转行,这么优秀的你一定上过小学语文,那么对扩句和缩句你一定不陌生。缩句就是去除各种修饰提炼出一句话的核心,而不失基...

AI9o後 ⋅ 42分钟前 ⋅ 0

z-index设置失效?

今天碰到了一个问题,就是在给li设置提示框的时候,有用到遮罩效果,本来想把对应的出现在最顶层,可是不管将li设置的z-index值设为多大,li都没有出现在遮罩层之上。 我在网上查了z-index设...

IrisHunag ⋅ 49分钟前 ⋅ 0

CyclicBarrier、CountDownLatch以及Semaphore使用及其原理分析

CyclicBarrier、CountDownLatch以及Semaphore是Java并发包中几个常用的并发组件,这几个组件特点是功能相识很容易混淆。首先我们分别介绍这几个组件的功能然后再通过实例分析和源码分析其中设...

申文波 ⋅ 53分钟前 ⋅ 0

Java对象的序列化与反序列化

Java对象的序列化与反序列化

Cobbage ⋅ 今天 ⋅ 0

Sqoop

1.Sqoop: 《=》 SQL to Hadoop 背景 1)场景:数据在RDBMS中,我们如何使用Hive或者Hadoop来进行数据分析呢? 1) RDBMS ==> Hadoop(广义) 2) Hadoop ==> RDBMS 2)原来可以通过MapReduce I...

GordonNemo ⋅ 今天 ⋅ 0

全量构建和增量构建的区别

1.全量构建每次更新时都需要更新整个数据集,增量构建只对需要更新的时间范围进行更新,所以计算量会较小。 2.全量构建查询时不需要合并不同Segment,增量构建查询时需要合并不同Segment的结...

无精疯 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部