关于java:高并发-集合

$1. 背景

在多线程高并发场景下，罕用的汇合类ArrayList、HashSet以及HashMap都常常被扣上一顶“不平安”的帽子，为什么呢？实际上，这三种罕用汇合类的读写办法中并没有加任何同步机制，从而会导致在同一时间有多个线程对汇合进行写操作(如add，remove)和读操作(如get)。多个线程同时读还尚且可能承受，但同时写或者一边读一边写呢？上述汇合都会基于add进行主动扩容，如果一条线程执行add操作触发容器扩容后还未进行理论写入，另一条线程就来读数据，可能读到的就是null值，在理论生产中将会导致重大的数据谬误！

// 如下代码会产生数据同步谬误
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Test {
    public static void main(String[] args) throws InterruptedException {
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<20; i++){
            new Thread(()->{
                list.add(new Random().nextInt());  // 写
                System.out.println(list);          // 读
            },String.valueOf(i)).start();
        }
        Thread.sleep(1000);
        System.out.println(list);
    }
}

在Java中，对于高并发的场景，下面的这三种罕用汇合类必定不能再应用了，因而须要抉择线程更加平安的汇合类来代替它们

$2. List

对于List而言，可用于代替ArrayList的线程平安汇合类次要有如下三种：

vector
Collections.syncronizedList
CopyOnWriteArrayList

2.1 Vector

古老的汇合类，之所以线程平安是其中所有读写办法都加上了Syncronized同步锁机制，尽管可能保证数据的同步性，但实际上也变相地将并发变成了串行，即同一时间只能有一条线程进行汇合的读或者写操作，性能因而十分的差

// Vector源码 -- 读写操作
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E get(int index) {
    if (index >= elementCount)
      throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}

2.2 Collections.syncronized()

借助Collections工具类的静态方法创立并返回一个阻塞的List对象，本质上是在Collection外部创立了一个动态外部类SyncronizedList，该动态外部类中所有读写操作应用了syncronized同步代码块，本质上和Vector相似，同一时间只反对单线程读 or 写，性能较低**

// Collections源码
public class Collections {
    ......
    
    static class SynchronizedList<E>
        extends SynchronizedCollection<E>
        implements List<E> {
        
        ......
        
        public void add(int index, E element) {
            synchronized (mutex) {
            list.add(index, element);
            }
        }
        public E remove(int index) {
            synchronized (mutex) {
            return list.remove(index);
            }
        }
        
        ......

    
    }

}

// 取得Collections.syncronizedList对象
List<Integer> list3 = Collections.synchronizedList(new ArrayList<>());

2.3 CopyOnWriteArrayList

CopyOnWriteArrayList实现的是写时复制的思维：往容器中增加元素时，并不是间接往以后容器数组中增加，而是先将以后容器数据在底层复制一份，而后进行扩容+1并将元素增加到新的容器中，增加完元素后，将原容器的援用指向新的容器，原容器对象会被GC。这样做的益处是能够对CopyOnWrite容器进行并发的读操作而不须要加锁，因为以后容器不会增加任何元素。CopyOnWrite容器是一种读写拆散的思维。

留神：CopyOnWriteArrayList容许多线程并发读，但同一时间只容许被一个线程批改，起因是每个批改办法都加了lock锁

// CopyOnWriteArrayList源码 - 读写操作
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 E get(int index) {  // 无锁
        return get(getArray(), index);
    }

CopyOnWriteArrayList在高并发场景下性能个别最优，因为其反对并发的读操作，不会产生大量线程阻塞的状况

$3. Set

对于Set而言，可用于代替HashSet的线程平安汇合类次要有如下三种：

Collections.syncronizedSet
CopyOnWriteArraySet

3.1 Collections.syncronizedSet()

原理和实现机制与Collections.syncronizedSet统一

3.1 CopyOnWriteArraySet

这里很容易因为先入为主而产生一个误区：HashSet的底层是实现的HashMap，然而 CopyOnWriteArraySet底层实现的是CopyOnWriteArrayList！！！和Map毫无关系！！！

看代码 —>

// CopyOnWriteArraySet 源码
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
                                    implements java.io.Serializable  {
    
    private final CopyOnWriteArrayList<E> al;
    
    public CopyOnWriteArraySet() {   // 构造方法1
        al = new CopyOnWriteArrayList<E>();
    }
    
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
                (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            al = new CopyOnWriteArrayList<E>();
            al.addAllAbsent(c);  
            // 调用CopyOnWriteArrayList的addAllAbsent办法，将c的非反复元素退出al
        }
    }
    
    public boolean add(E e) {
        return al.addIfAbsent(e);  // CopyOnWriteArrayList的 add + 去重性能
    }
    
}

// CopyOnWriteArrayList源码之实现去重插入 ---> 为CopyOnWriteArraySet筹备的

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();  // 备份add前的数组
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray(); 
        int len = current.length;
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0) // 即元素已存在，放弃
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

$4. Map

对于Map而言，可用于代替HashMap的线程平安汇合类次要有如下三种：

HashTable
Collections.syncronizedMap
ConcurrentHashMap

4.1 HashTable

古老的Map汇合，和Vector相似，所有的读写办法都退出了Syncronized同步锁，多线程下性能很低

4.2 Collections.syncronizedMap

同Collections.syncronizedList、Collections.syncronizedSet

4.3 ConcurrentHashMap

思维：锁机制更加颗粒化 — 本质上这是高并发场景下保持数据同步性和并发性能均衡的外围诉求

JDK1.7

ConcurrentHashMap的底层数据结构如下图：

该版本的ConcurrentHashMap应用的是ReentrantLock锁，但锁的对象并不是整个Map，而是底层数组的每一个segment，其中每一个segment本质上就相当于一个HashTable，以绝对臃肿的构造变相地实现了锁的细化

JDK1.8

底层数据结构产生了扭转：

在jdk1.8中，ConcurrentHashMap放弃了segment数组的臃肿设计，采纳Node数组 + CAS + syncronized锁的机制实现并发同步，并且也引进了红黑树结构，当一个数组索引地位的链表长度达到8后就会转化为红黑树结构，优化了后续查问速度

关于java:高并发-集合

$1. 背景

$2. List

2.1 Vector

2.2 Collections.syncronized()

2.3 CopyOnWriteArrayList

$3. Set

3.1 Collections.syncronizedSet()

3.1 CopyOnWriteArraySet

$4. Map

4.1 HashTable

4.2 Collections.syncronizedMap

4.3 ConcurrentHashMap

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于java:高并发-集合

$1. 背景

$2. List

2.1 Vector

2.2 Collections.syncronized()

2.3 CopyOnWriteArrayList

$3. Set

3.1 Collections.syncronizedSet()

3.1 CopyOnWriteArraySet

$4. Map

4.1 HashTable

4.2 Collections.syncronizedMap

4.3 ConcurrentHashMap

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复