06-线程安全集合

1. Collection体系下线程安全集合

Collection体系集合下，除Vector以外的线程安全集合（蓝色）：

Collections工具类中提供了多个可以获得线程安全集合的方法：
public static <T> Collection<T> synchronizedCollection(Collection<T> c)
public static <T> List<T> synchronizedList(List<T> list)
public static <T> Set<T> synchronizedSet(Set<T> s)
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)
public static <T> SortedSet<T> synchronizedSortSet(SortedSet<T> s)
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
特点：

• 都是返回对应泛型集合类型的方法；
• 都是静态方法，通过Collections直接调用；
• 都是在静态方法中new了一个synchronized同步的静态内部类；
• 实际使用时的成员方法与原集合没有区别；
• JDK1.2提供，接口统一、维护性高，但性能没有提升，均以synchonized实现。

示例其中一个：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TestCollections {
      public static void main(String[] args) {
            // 线程不安全的集合 ArrayList
            List<String> list = new ArrayList<String>(); // 0x1111  A0001
            
            List<String> safeList = Collections.synchronizedList(list);  // 0x3456 7891 Collections$SynchronizedList
            // 用法于线程不安全集合本身没有区别
            safeList.add("A"); // SynchronizedList里的add方法，该方法加了个synchronized(mutex)锁
            safeList.add("B");
            safeList.add("C");
            safeList.remove(1);
            safeList.get(1);
      }
}

2. CopyOnWriteArrayList类（线程安全的List）

public class CopyOnWriteArrayList<E>
extends Object
implements List<E>, RandomAccess, Cloneable, Serializable

说明：

• 符合List特点：有序、有下标、元素可重复
• 线程安全的ArrayList，加强版读写分离；
• 写有锁，读无锁，读写之间不阻塞，优先读写锁；
• 写入时，先copy一个容器副本、再添加新元素，最后替换引用；
• 使用方式与ArrayList无异。

// 创建一个线程安全的高并发List
List<String> safeList = new CopyOnWriteArrayList<String>();

3. CopyOnWriteArraySet类（线程安全的Set）

public class CopyOnWriteArraySet<E>
extends AbstractSet<E>
implements Serializable

说明：

• 符合Set特点：无序、无下标、元素不重复
• 线程安全的Set，底层使用CopyOnWriteArrayList实现；
• 唯一不同在于，使用addIfAbsent()添加元素(查重)，会遍历数组；
• 如存在元素，则不添加（扔掉副本）。

// 创建一个线程安全的高并发Set
Set<String> safeSet = new CopyOnWriteArraySet<String>();

4. ConcurrentHashMap类（线程安全的Map）

public class ConcurrentHashMap<K,V>
extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable

说明：

• 初识容量默认为16段(Segment)，使用分段锁设计；
• 不对整个Map加锁，而是为每个Segment加锁；
• 当多个对象存入同一个Segment时，才需要互斥；
• 最理想状态位16个对象分别存入16个Segment，并行线程数量16个；
• 使用方式与HashMap无异。
  // JDK1.7: 分段锁设计 Segment
  // JDK1.8: CAS交换算法（CAS比较和交换） + 同步锁（锁的是表头）

// 创建一个线程安全的高并发Map
Map<String, Integer> safeMap = new ConcurrentHashMap<String, Integer>();

**CAS交换算法(Compare And Swap)**：
V:要更新的变量
E:预期值
N:新值
当 V == E 时，V=N；
如果在修改过程中，V已经发生了变化，V != E，则取消当前赋值操作，做下一次赋值。

public static void main(String[] args) {
      // 【线程安全的List】
      List<String> alist = new CopyOnWriteArrayList<String>();
      // 写操作 - 有锁
      alist.add("A"); // 都将底层数组做了一次复制，写的是新数组，完成赋值后，再将数组替换掉旧数组
      alist.add("B"); // 每调用一次，底层方法扩容一次。
      // 读操作 - 无锁
      alist.get(1);
      
      // 【线程安全的Set】
      Set<String> aset = new CopyOnWriteArraySet<String>();
      // 写操作 - 有锁
      aset.add("A"); // 表面使用的add实际使用的addIfAbsent元素遍历数组查重
      aset.add("B");
      aset.add("C");
      for (String string : aset) {
            System.out.print(string + " ");
      }
      System.out.println();
      
      // 【线程安全的Map】
      Map<String, Integer> chmap = new ConcurrentHashMap<String,  Integer>();
      // JDK1.7: 分段锁设计 Segment
      // JDK1.8: CAS交换算法（CAS比较和交换） + 同步锁（锁的是表头）
      chmap.put("A", 1);
      chmap.put("B", 2);
      chmap.put("C", 3);
}

补充：对ConcurrentHashMap的线程安全算法理解

源码分析：
JDK1.7中ConcurrentHashMap中的putVal()实现方式：分段锁 Segment（16把锁）

JDK1.8中ConcurrentHashMap中的putVal()实现方式：【CAS交换算法 + 同步锁】锁链表表头对象

JDK1.8源码分析 - 当我们调用put方法时，CAS交换算法+同步锁是如何保证线程安全的：

public V put(K key, V value) {
    return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    // 遍历Map中的table
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // f 计算了Node对象，Map中链表的头部对象 - 为了遍历该链表
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 【CAS交换算法】V==E时V=N；V!=E则取消赋值,进入下一次赋值
            // @tab        代表是否存在该对象
            // @i         一个hash的运算找到下标
            // @null     原始值为null（即预期值E）
            // @Node    传进来的key,value要存入的值
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 【同步锁】锁的是表头对象
            // 拿到锁的对象做Map中链表的遍历,key相同则覆盖,不同则挂链表上
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        // 遍历找到key相等就值覆盖
                        // key不相等pred.next==null就把自己存上
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}