算法与数据结构(3),并发结构

本来已经合上电脑了,躺在床上,翻来覆去睡不着,索性,不睡了,起床,听听歌,更新简书,这可能是这一系列的最后一篇,脚趾的伤也好的差不多了,下个礼拜就要全身心找工作了。

并发List

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

CopyOnWriteArrayList的内部实现与Vector不同,从字面中可以看出Copy-On-Write就是CopyOnWriteArrayList的实现机制。即当对象进行写操作时,复制该对象;若进行的时读操作,则直接返回结果,操作过程中不进行同步。

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

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

get( )方法如下:

/** The array, accessed only via getArray/setArray. */
private volatile transient Object[] array;//内置数组被关键字volatile修饰

/**
 * {@inheritDoc}
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    return get(getArray(), index);
}

/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {
    return array;
}

可以看到,作为一个线程安全的实现,CopyOnWriteArrayList的get( )没有任何锁操作,而对比Vector的get( )实现:

/**
 * Returns the element at the specified position in this Vector.
 *
 * @param index index of the element to return
 * @return object at the specified index
 * @throws ArrayIndexOutOfBoundsException if the index is out of range
 *            ({@code index < 0 || index >= size()})
 * @since 1.2
 */
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

Vector使用了同步关键字synchronized所有的get( )操作都必须先等待对象锁的释放,才能进行。在高并发的情况下,大量的锁竞争会降低系统性能。

虽然CopyOnWriteArrayList的读操作性能优越,但是,基于CopyOnWriteArrayList的写操作却不能尽如人意。

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
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();
    }
}

在每一次add( )方法中,CopyOnWriteArrayList都进行一次自我复制,同时add( )操作也申请了锁,并不像get( )那样。相对的,Vector的add( )方法则要快捷的多。

/**
 * Appends the specified element to the end of this Vector.
 *
 * @param e element to be appended to this Vector
 * @return {@code true} (as specified by {@link Collection#add})
 * @since 1.2
 */
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);     //内置数组是否需要扩容
    elementData[elementCount++] = e;
    return true;
}

因此,在高并发且以读为主的应用场景中,CopyOnWriteArrayList要优于Vector。但是当写操作很频繁时,CopyOnWriteArrayList的效率并不高,可以考虑优先使用Vector。

并发Map 在多线程环境中使用Map,一般也可以使用Collections.synchronizedMap( )进行包装。

但是在高并发情况下,这个Map的性能表示不是最优的。因为被包装后的Map,在进行读写操作时都要等待锁的释放。

在高并发的环境中,可以使用ConcurrentHashMap,写操作的效率比同步HashMap快了将近一倍,ConcurrentHashMap之所以有如此之高的吞吐量,得益于其内部实现了锁桶的锁分离机制,在读写整张Entry数组表的时候,不需要像HashMap那样锁住整张表,而是只锁当前需要用到的桶,原来只能一个线程进入,现在却能同时16(默认16个桶)个写线程进入,并发性的提升是显而易见的。同时,ConcurrentHashMap的get( )操作是无锁的。这些都为ConcurrentHashMap在多线程并发下的高性能提供了保证。

ConcurrentHashMap是专门为线程设计的HashMap。它的get( )操作时无锁的,它的put( )操作的锁粒度又小于同步HashMap。因此它的整体性能优于同步的HashMap。

并发Queue

Queue是一种特殊的线性结构队列,只允许从队列的头部移除元素,或者从队列的尾端添加元素,以一种FIFO(先进先出)的方式管理数据。

add( ),和remove( )方法。

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");      //队列已满,抛出异常
}

public E remove() {
    E x = poll();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();     //队列为空,抛出异常
}

由此可见,应该尽量避免使用add( ),和remove( )方法。而使用offer( )来加入元素,使用poll( )来获取并移出元素。

并发队列,有两种实现,一个是以ConcurrentLinkedQueue为代表的高性能队列,一个是以BlockingQueue为代表的阻塞队列。

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

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

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

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

BlockingQueue的工作模式

BlockingQueue提供了两种主要实现:

  1. ArrayBlockingQueue:它是一种基于数组的阻塞队列实现,在ArrayBlockingQueue内部还维护了一个定长的数组,用于缓存队列中的数据对象。此外,ArrayBlockingQueue内部还存着两个整型变量,分别标识着队列头部和尾部在数组中的位置。
  2. LinkedBlockingQueue:这是一个基于链表的阻塞队列,ArrayBlockingQueue类似,内部也维持着一个数据缓冲队列(该队列由一个链表构成),当生产者往队列中放入一个数据时,队列会从生产者手中获取数据,并缓存在队列内部,而生产者立即返回;只有当队列缓冲区达到最大值缓存容量时,才会阻塞生产者队列,直到消费者从队列中消费掉一个数据,生产者线程才能被唤醒。

并发Deque

Deque是一种双端队列,允许在队列的头部或者尾部进行出队和入队操作。

由于Deque这个接口日常工作中很少用到,这里只做简单介绍。

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

在AsyncTask的源代码中

private static class SerialExecutor implements Executor {

    final ArrayDeque<Runnable> mTasks = new ArrayDeque<Runnable>();
    Runnable mActive;
    
    /*ArrayDeque不是线程安全的,execute需要用关键字synchronized 修饰*/
    public synchronized void execute(final Runnable r) {
        mTasks.offer(new Runnable() {
            public void run() {
                try {
                    r.run();
                } finally {
                    scheduleNext();
                }
            }
        });
        if (mActive == null) {
            scheduleNext();
        }
    }
    protected synchronized void scheduleNext() {
        if ((mActive = mTasks.poll()) != null) {
            THREAD_POOL_EXECUTOR.execute(mActive);
        }
    }
}

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

片尾TIP:

private SparseArray<String> sparseArray = new SparseArray<String>();
private SparseIntArray sparseIntArray = new SparseIntArray();
private SparseBooleanArray sparseBooleanArray = new SparseBooleanArray();
private LongSparseArray<String> longSparseArray = new LongSparseArray<String>();

public void Test() {

    sparseArray.put(1, "1");
    sparseIntArray.put(2, 2);
    sparseBooleanArray.put(3, true);
    longSparseArray.put(4, "4");
}

使用优化后的数据集合,可以避免掉基本数据类型转换成对象数据类型时浪费的时间。

数据结构这个系列,暂且告一段落,最后,我想把这段话送给大家。

送给大家的话

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏非典型技术宅

Swift多线程之Operation:异步加载CollectionView图片1. Operation 设置依赖关系2. 前置知识点内容3. CollectionView中图片进行异步加载

22570
来自专栏有趣的django

python开发面试问题

python语法以及其他基础部分 可变与不可变类型;  浅拷贝与深拷贝的实现方式、区别;deepcopy如果你来设计,如何实现;  __new__() 与 __...

52080
来自专栏Python爬虫与算法进阶

学点算法之队列的学习及应用

约瑟夫问题 约瑟夫问题 有 n 个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过 k-1个...

38970
来自专栏.NET后端开发

ADO.NET入门教程(六) 谈谈Command对象与数据检索

摘要 到目前为止,我相信大家对于ADO.NET如何与外部数据源建立连接以及如何提高连接性能等相关知识已经牢固于心了。连接对象作为ADO.NET的主力先锋,为用户...

44470
来自专栏大内老A

WCF技术剖析之十四:泛型数据契约和集合数据契约(上篇)

在.NET Framework 2.0中,泛型第一次被引入。我们可以定义泛型接口、泛型类型、泛型委托和泛型方法。序列化依赖于真实具体的类型,而泛型则刻意模糊了具...

25380
来自专栏乐百川的学习频道

设计模式(二十四) 访问者模式

访问者模式提供了一种方法,将算法和数据结构分离。假设我们需要对一个数据结构进行不同的操作,就可以考虑使用访问者模式。访问者模式的要点在于,需要一个访问者接口,提...

24860
来自专栏calmound

缺省参数是编译期间绑定的,而不是动态绑定

看一个程序 #include <iostream> using namespace std; class A { public: virtual void ...

33560
来自专栏贾老师の博客

Lock-Free 学习总结

在通常使用 Mutex 互斥锁的场景, 有的线程抢占了锁, 其他线程则会被阻塞, 当获得锁的进程挂掉之后, 整个程序就 block 住了. 但在 Lock-Fr...

84640
来自专栏有趣的django

PYTHON面试

大部分的面试问题,有最近要找事的老铁吗?  python语法以及其他基础部分 可变与不可变类型;  浅拷贝与深拷贝的实现方式、区别;deepcopy如果你来...

77870
来自专栏精讲JAVA

用 Maven 实现一个 protobuf 的 Java 例子

Protocal Buffers(简称protobuf)是谷歌的一项技术,用于结构化的数据序列化、反序列化,常用于RPC 系统(Remote Procedure...

18920

扫码关注云+社区

领取腾讯云代金券