关于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

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

1. JDK1.7

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

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

1. JDK1.8

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

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