Java多线程之集合类不安全

1. 集合类不安全

1.1 List不安全

集合线程的不安全性，如多线程操作ArrayList时，ArrayList在迭代的时候如果同时对其进行修改就会抛出java.util.ConcurrentModificationException异常，并发修改异常

List<String> list = new ArrayList<>();
for (int i = 0; i < 30; i++) {
    new Thread(() -> {
        list.add(UUID.randomUUID().toString().substring(0,8));
        System.out.println(list);
    }, String.valueOf(i)).start();
}

解决方案
- Vector
  - List<String> list = new Vector<>();
  - 加锁，安全，但性能差
- Collections
  - List<String> list = Collections.synchronizedList(new ArrayList<>());
    Collections提供了方法synchronizedList保证list是同步线程安全的
  - HashSet 与 HashMap 也是非线程安全的，Collections也提供了对应的方法
- 写时复制CopyOnWriteArrayList
  - 类似读写分离的思想

1.2 写时复制

CopyOnWrite理论
- CopyOnWrite容器即写时复制的容器。往一个容器添加元素的时候，不直接往当前容器Object[]添加，而是先将当前容器Object[]进行Copy，复制出一个新的容器Object[] newElements，然后向新的容器Object[] newElements里添加元素。添加元素后，再将原容器的引用指向新的容器setArray(newElements)。这样做的好处是可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

CopyOnWriteArrayList 源码

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

1.3 Set不安全

HashSet线程不安全，底层结构是HashMap，set添加时调用的是map的put方法，值作为key，而value为固定值

public HashSet() {
    map = new HashMap<>();
}
private static final Object PRESENT = new Object(); 
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

Set<String> set = new HashSet<>();//线程不安全
Set<String> set = Collections.synchronizedSet(new HashSet<>());//线程安全
Set<String> set = new CopyOnWriteArraySet<>();//线程安全

1.4 Map不安全

1.4.1 HashMap

初始容器 16 / 0.75
根据键的hashCode值存储数据
允许一个键为null，允许多个值为null
HashMap线程不安全，线程安全Collections.synchronizedMap或ConcurrentHashMap
Java7，数组+单向链表，每个Entry包含4个值:key、value、hash值和用于单向链表的next
扩容：当前的2倍，负载因子：0.75
Java8，数组+链表+红黑树，链表节点数超过8后，链表转为红黑树，减少查找链表数据的时间
map.put(k,v)实现原理
- 第一步首先将k,v封装到Node对象当中（节点）。
- 第二步它的底层会调用K的hashCode()方法得出hash值。
- 第三步通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的表头，next指向之前的表头节点。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
JDK8之后，如果哈希表单向链表中元素超过8个，那么单向链表这种数据结构会变成红黑树数据结构。当红黑树上的节点数量小于6个，会重新把红黑树变成单向链表数据结构。

1.4.2 ConcurrentHashMap

整个 ConcurrentHashMap 由一个个 Segment 组成，ConcurrentHashMap 是一个 Segment 数组
线程安全，Segment 通过继承ReentrantLock 来进行加锁，加锁锁住的是Segment
JDK1.7分段锁，1.8CAS(compare and swap的缩写，即我们所说的比较交换)
JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树