高并发下的Java数据结构(List,Set,Map,Queue)

由于并行程序与串行程序的不同特点,适用于串行程序的一些数据结构可能无法直接在并发环境下正常工作,这是因为这些数据结构不是线程安全的。本节将着重介绍一些可以用于多线程环境的数据结构,如并发List、并发Set、并发Map等。

1.并发List

Vector 或者 CopyOnWriteArrayList 是两个线程安全的List实现,ArrayList 不是线程安全的。因此,应该尽量避免在多线程环境中使用ArrayList。如果因为某些原因必须使用的,则需要使用Collections.synchronizedList(List list)进行包装。

示例代码:

        List list = Collections.synchronizedList(new ArrayList());
            ...
        synchronized (list) {
            Iterator i = list.iterator(); // 必须在同步块中
            while (i.hasNext())
                foo(i.next());
        }

CopyOnWriteArrayList 的内部实现与Vector又有所不同。顾名思义,Copy-On-Write 就是 CopyOnWriteArrayList 的实现机制。即当对象进行写操作时,复制该对象;若进行的读操作,则直接返回结果,操作过程中不需要进行同步。

CopyOnWriteArrayList 很好地利用了对象的不变性,在没有对对象进行写操作前,由于对象未发生改变,因此不需要加锁。而在试图改变对象时,总是先获取对象的一个副本,然后对副本进行修改,最后将副本写回。

这种实现方式的核心思想是减少锁竞争,从而提高在高并发时的读取性能,但是它却在一定程度上牺牲了写的性能。

在 get() 操作上,Vector 使用了同步关键字,所有的 get() 操作都必须先取得对象锁才能进行。在高并发的情况下,大量的锁竞争会拖累系统性能。反观CopyOnWriteArrayList 的get() 实现,并没有任何的锁操作。

在 add() 操作上,CopyOnWriteArrayList 的写操作性能不如Vector,原因也在于Copy-On-Write。

在读多写少的高并发环境中,使用 CopyOnWriteArrayList 可以提高系统的性能,但是,在写多读少的场合,CopyOnWriteArrayList 的性能可能不如 Vector。

2.并发Set

和List相似,并发Set也有一个 CopyOnWriteArraySet ,它实现了 Set 接口,并且是线程安全的。它的内部实现完全依赖于 CopyOnWriteArrayList ,因此,它的特性和 CopyOnWriteArrayList 完全一致,适用于 读多写少的高并发场合,在需要并发写的场合,则可以使用 Set s = Collections.synchronizedSet(Set<T> s)得到一个线程安全的Set。

示例代码:

    Set s = Collections.synchronizedSet(new HashSet());
        ...
    synchronized (s) {
        Iterator i = s.iterator(); // 必须在同步块中
        while (i.hasNext())
            foo(i.next());
    }

3.并发Map

在多线程环境下使用Map,一般也可以使用 Collections.synchronizedMap()方法得到一个线程安全的 Map(详见示例代码1)。但是在高并发的情况下,这个Map的性能表现不是最优的。由于 Map 是使用相当频繁的一个数据结构,因此 JDK 中便提供了一个专用于高并发的 Map 实现 ConcurrentHashMap。

Collections的示例代码1:

        Map m = Collections.synchronizedMap(new HashMap());
            ...
        Set s = m.keySet();  // 不需要同步块
            ...
        synchronized (m) {  // 同步在m上,而不是s上!!
            Iterator i = s.iterator(); // 必须在同步块中
            while (i.hasNext())
                foo(i.next());
        }

1.为什么不能在高并发下使用HashMap?

因为多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。

2.为什么不使用线程安全的HashTable?

HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时,其他线程访问HashTable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。

3.ConcurrentHashMap的优势

ConcurrentHashMap的内部实现进行了锁分离(或锁分段),所以它的锁粒度小于同步的 HashMap;同时,ConcurrentHashMap的 get() 操作也是无锁的。

锁分离:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁。

上述文字部分参考自文章:Java集合---ConcurrentHashMap原理分析

4.并发Queue

在并发队列上,JDK提供了两套实现,一个是以 ConcurrentLinkedQueue 为代表的高性能队列,一个是以 BlockingQueue 接口为代表的阻塞队列。不论哪种实现,都继承自 Queue 接口。

ConcurrentLinkedQueue 是一个适用于高并发场景下的队列。它通过无锁的方式,实现了高并发状态下的高性能。通常,ConcurrentLinkedQueue 的性能要好于 BlockingQueue 。

与 ConcurrentLinkedQueue 的使用场景不同,BlockingQueue 的主要功能并不是在于提升高并发时的队列性能,而在于简化多线程间的数据共享。

BlockingQueue 典型的使用场景是生产者-消费者模式,生产者总是将产品放入 BlockingQueue 队列,而消费者从队列中取出产品消费,从而实现数据共享。

BlockingQueue 提供一种读写阻塞等待的机制,即如果消费者速度较快,则 BlockingQueue 则可能被清空,此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞。反之,如果生产线程较快,则 BlockingQueue 可能会被装满,此时,生产线程再试图向 BlockingQueue 队列装入数据时,便会被阻塞等待,其工作模式如图所示。

5.并发Deque

在JDK1.6中,还提供了一种双端队列(Double-Ended Queue),简称Deque。Deque允许在队列的头部或尾部进行出队和入队操作。与Queue相比,具有更加复杂的功能。

Deque 接口的实现类:LinkedList、ArrayDeque和LinkedBlockingDeque。

它们都实现了双端队列Deque接口。其中LinkedList使用链表实现了双端队列,ArrayDeque使用数组实现双端队列。通常情况下,由于ArrayDeque基于数组实现,拥有高效的随机访问性能,因此ArrayDeque具有更好的遍性能。但是当队列的大小发生变化较大时,ArrayDeque需要重新分配内存,并进行数组复制,在这种环境下,基于链表的 LinkedList 没有内存调整和数组复制的负担,性能表现会比较好。但无论是LinkedList或是ArrayDeque,它们都不是线程安全的。

LinkedBlockingDeque 是一个线程安全的双端队列实现。可以说,它已经是最为复杂的一个队列实现。在内部实现中,LinkedBlockingDeque 使用链表结构。每一个队列节点都维护了一个前驱节点和一个后驱节点。LinkedBlockingDeque 没有进行读写锁的分离,因此同一时间只能有一个线程对其进行操作。因此,在高并发应用中,它的性能表现要远远低于 LinkedBlockingQueue,更要低于 ConcurrentLinkedQueue 。

参考

《Java程序性能优化》葛一鸣著

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MasiMaro 的技术博文

Vista 及后续版本的新线程池

在上一篇的博文中,说了下老版本的线程池,在Vista之后,微软重新设计了一套线程池机制,并引入一组新的线程池API,新版线程池相对于老版本的来说,它的可控性更高...

1623
来自专栏java一日一条

2017年高频率的互联网校园招聘面试题

参加了2017年校招,面试了阿里、百度、腾讯、滴滴、美团、网易、去哪儿等公司,个人是客户端 Android 方向,总结了面试过程中频率出现较高的题目,希望对大家...

1802
来自专栏微信公众号:Java团长

从并发编程到分布式系统——如何处理海量数据(上)

在这里想写写自己在学习并发处理的学习思路,也会聊聊自己遇到的那些坑,以此为记,希望鞭策自己不断学习、永不放弃!

921
来自专栏开发技术

shiro源码篇 - shiro的session的查询、刷新、过期与删除,你值得拥有

    老公酷爱网络游戏,老婆无奈,只得告诫他:你玩就玩了,但是千万不可以在游戏里找老婆,不然,哼哼。。。     老公嘴角露出了微笑:放心吧亲爱的,我绝对不会...

3512
来自专栏JavaEdge

高性能队列——Disruptor总论1 背景2 Java内置队列3 ArrayBlockingQueue的问题4 Disruptor的设计方案代码样例性能等待策略Log4j 2应用场景

这里所说的队列是系统内部的内存队列,而不是Kafka这样的分布式队列 Disruptor特性限于3.3.4

2513
来自专栏阿杜的世界

《七周七并发模型》阅读笔记(一)一、线程与锁——第一天二、线程与锁——第二天三、线程与锁——第三天

线程与锁模型其实是对底层硬件运行过程的形式化,这种形式化既是该模型最大的优点,也是它最大的缺点。我们借助Java语言来学习线程与锁模型,不过内容也适用于其他语言...

1342
来自专栏SDNLAB

ODL应用开发之MD-SAL中级教程

1. 简介 本次我们从开始设计到最终完成一个应用的开发,主要设计datastore和RPC定义和实现。Opendaylight 开发使用了OSGi框架,OSGi...

7508
来自专栏IT技术精选文摘

Java多线程知识小抄集(二)

27. ConcurrentHashMap ConcurrentHashMap是线程安全的HashMap,内部采用分段锁来实现,默认初始容量为16,装载因子为0...

2036
来自专栏有趣的django

面试题目及答案

1 Python的函数参数传递 看两个例子: a = 1 def fun(a): a = 2 fun(a) print a # 1 a = [] de...

1.2K9
来自专栏微服务生态

淘宝Tedis组件究竟是个啥(一)

淘宝的Tedis组件究竟是个啥呢?可能有一些朋友没有听过这个名字,有一些朋友会经常使用,那么今天我就来和大家深入分析一下,它的使用和原理。

1172

扫码关注云+社区

领取腾讯云代金券