`
uule
  • 浏览: 6351563 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

高并发下的数据结构List/Set/Map

 
阅读更多

高并发下的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 很好地利用了对象的不变性,在没有对对象进行写操作前,由于对象未发生改变,因此不需要加锁。而【在试图改变对象时,总是先获取对象的一个副本(即复制List里的数组),然后对副本进行修改,最后将副本写回】

 

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

 

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

反观【CopyOnWriteArrayList 的get() 实现,并没有任何的锁操作】

 

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

 

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

 

核心实现:

public boolean add(E e) {

        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
	

public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);

            Object[] newElements;
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }

            newElements[index] = element;
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }	


public E get(int index) {
        return get(getArray(), index);
    }	


    private E get(Object[] a, int index) {
        return (E) a[index];
    }

   	/**
     * Append the element if not present.
     * @param e element to be added to this list, if absent
     * @return <tt>true</tt> if the element was added
     */

    public boolean addIfAbsent(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            // Copy while checking if already present.
            // This wins in the most common case where it is not present

            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = new Object[len + 1];
            for (int i = 0; i < len; ++i) {
                if (eq(e, elements[i]))
                    return false; // exit, throwing away copy
                else
                    newElements[i] = elements[i];
            }

            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

 

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

 

其内部是基于CopyOnWriteArrayList实现的。

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    
    private final CopyOnWriteArrayList<E> al;

    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
	
public int size() {
        return al.size();
    }
	
	public boolean add(E e) {
        return al.addIfAbsent(e);
    }
}

 

3.并发Map

在多线程环境下使用Map,一般也可以使用 Collections.synchronizedMap()方法得到一个线程安全的 Map。但是在高并发的情况下,这个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(),它们可能需要锁定整个表而而不仅仅是某个段】,这需要【按顺序锁定所有段】,操作完毕后,又【按顺序释放所有段的锁】

 

 

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 。

 

分享到:
评论

相关推荐

    09、并发容器(Map、List、Set)实战及其原理

    本课程"09、并发容器(Map、List、Set)实战及其原理"深入探讨了如何在多线程环境下有效使用Map、List和Set这三种核心数据结构。下面我们将详细讲解这些并发容器的关键知识点。 1. **并发容器概述**: 在并发编程...

    9、并发容器(Map、List、Set)实战及其原理.pdf

    根据提供的文档信息,本文将详细解析并发容器(Map、List、Set)的实战应用及其原理。并发容器在Java多线程环境下发挥着至关重要的作用,它们的设计旨在解决非线程安全容器在高并发场景下的性能瓶颈问题。接下来,...

    Java集合框架深度解析:Map, List, Set

    深入的洞察到Java集合框架的核心组件:Map, List, 和 Set。首先,深入分析了HashMap的内部结构,包括它的数组+链表+红黑树的数据结构。重要的是理解如何处理并发问题,特别是在Java 8中对HashMap的优化,如高低位...

    Java集合知识图谱 ,包含map,list,set

    TreeSet则基于红黑树数据结构,提供了排序功能。 “2.6 Java Map类图.jpg”主要关注Map接口及其实现。Map接口存储键值对,不继承Collection接口。HashMap是最常见的实现,提供快速的查找,而TreeMap则保持键的自然...

    数据结构(c/c++实现)

    2. **STL(标准模板库)**:包括容器(如vector、list、set、map等)、迭代器、算法等,提供现成的数据结构和操作。 3. **智能指针**:如auto_ptr、shared_ptr、unique_ptr,用于更安全地管理内存。 4. **模板**:...

    Java中List、ArrayList、Vector及map、HashTable、HashMap分别的区别.

    HashMap是非同步的,适合于高并发环境下,但如果不考虑线程安全,HashMap的性能优于同步的HashTable。 4. HashTable类 HashTable是早期的同步Map实现,它不允许键和值为null。与HashMap相比,HashTable的同步特性...

    java描述下的数据结构

    此外,熟悉这些数据结构还有助于理解和使用Java的内置容器类库,如List、Set、Map等,以及并发工具类如ConcurrentHashMap等。 总之,“_数据结构(Java语言版)”这份资料详细讲解了Java编程中的数据结构,对于提升...

    高并发场景杂谈.zip

    Redisson是基于Redis的Java客户端,它提供了一整套高级特性和功能,如分布式的Map、Set、List等数据结构。通过Redisson,我们可以将传统的Web项目分布式化,实现数据的高可用性和高性能。例如,利用Redis进行会话...

    数据结构面试题及正确答案

    在高并发场景下,选择合适的数据结构和并发工具至关重要。例如,对于读多写少的情况,可以使用`CopyOnWriteArrayList`或`CopyOnWriteArraySet`;对于需要高效并发读写操作的Map,`ConcurrentHashMap`是个好选择。而...

    数据结构和Java集合框架源代码

    Java集合框架是Java标准库中的一部分,它提供了一系列接口和类,如List、Set、Map,以及ArrayList、LinkedList、HashSet、HashMap等实现类。这些接口和类为开发者提供了处理各种数据结构的统一方式。例如,ArrayList...

    数据结构与算法(JAVA语言版)

    - **集合框架**:Java提供了丰富的接口(如List、Set、Map)和实现类(如ArrayList、LinkedList、HashSet、HashMap等),方便实现各种数据结构。 - **泛型**:使数据结构可以处理任何类型的数据,增强了代码的复用...

    Scala数据结构和算法.docx

    包括Array、List、Set、Map等传统数据结构,以及Seq、Buffer、Stack等接口。这些集合都实现了丰富的操作,支持函数式编程的惰性求值和不可变性特性。 3. **Option类型**:Option是Scala处理null安全的一种方式,它...

    数据结构与算法分析(Java版英文

    1. Java集合框架:包括List、Set、Queue、Map接口以及其实现类,如ArrayList、LinkedList、HashSet、HashMap等。 2. 异常处理:Java中的try-catch-finally语句块用于捕获和处理运行时异常。 3. 多线程:Java提供...

    第三方可扩展的Go语言中高性能数据结构和数据类型合集.zip

    在Go语言中,高效的数据结构和数据类型是构建高性能应用程序的关键。"第三方可扩展的Go语言中高性能数据结构和数据类型合集.zip"这个压缩包很可能是包含了一系列为Go编程语言设计的优化过的数据结构和类型实现。这些...

    Java软件结构 设计和使用数据结构

    这些接口包括List、Set、Queue和Map,而ArrayList、HashSet、LinkedList、PriorityQueue和HashMap等则是它们的常见实现。在"ch03 Code"中,你可能会看到对这些基本接口和类的实现和使用的示例。 其次,`ch05 Code`...

    [数据结构和Java集合框架]源代码

    在Java集合框架中,`java.util`包提供了各种接口和实现,如List、Set、Queue和Map,它们分别对应于不同的数据结构。List接口(如ArrayList和LinkedList)支持有序的元素集合,允许重复元素;Set接口(如HashSet和...

    基于Java的数据结构提取器.zip

    3. **集合框架**:Java集合框架是Java.util包下的核心部分,包括List、Set和Map接口以及它们的实现类,如ArrayList、LinkedList、HashSet、HashMap等。这些数据结构提供了灵活的数据存储和操作方式,适应不同场景...

    Java 集合与数据结构详解1

    在高并发场景下,了解HashMap的工作原理有助于优化代码性能。 总的来说,Java集合框架和数据结构是Java程序员必须掌握的基础知识,它们在实际开发中起着至关重要的作用。无论是面试还是项目开发,对这些概念的理解...

    详解Java中list,set,map的遍历与增强for循环

    总的来说,Java集合框架提供了丰富的数据结构供开发者选择,遍历这些集合也有多种方式,包括传统的迭代器和简洁的增强for循环。理解这些概念和方法,能帮助开发者更高效地处理Java程序中的数据存储和操作。

    Java数据结构源码

    - **集合框架**:包括List(ArrayList、LinkedList)、Set(HashSet、TreeSet)和Map(HashMap、TreeMap),提供了丰富的操作接口。 - **树结构**:如二叉树、AVL树、红黑树等,Java中TreeSet和TreeMap基于红黑树...

Global site tag (gtag.js) - Google Analytics