多线程与并发编程 (3/3)

1 常用线程安全类型*

1.1 JDK 基础数据类型与集合类

1.2 ArrayList

基本特点：基于数组，便于使用 index 随机访问，超过数组容量时需要扩容，扩容成本较高。
用途：大部分情况下操作一组数据都可以用 ArrayList。
原理：使用数组模拟列表，默认大小10，扩容x1.5，newCapacity = oldCapacity + (oldCapacity >> 1)。

安全问题：写冲突、读写冲突。

写冲突：两个写，相互操作冲突；
读写冲突：

• 读，特别是使用迭代器 Iterator 的时候，数据个数变了，拿到了非预期数据或者报错；（类比数据库的幻读）
• 产生 ConcurrentModificationException。

1.3 LinkedList

基本特点：使用链表实现，无需扩容。
用途：不知道容量，插入变动多的情况。
原理：使用双向链表将所有节点连起来。
安全问题：写冲突、读写冲突。
写冲突：两个写，相互操作冲突；
读写冲突：

• 读，特别是使用迭代器 Iterator 的时候，数据个数变了，拿到了非预期数据或者报错；
• 产生 ConcurrentModificationException。

1.4 使 List 线程安全的简单办法

既然线程安全是写冲突和读写冲突导致的，最简单办法就是，读写都加锁。
例如：

• 1. ArrayList 的方法都加上 synchronized > Vector；
• 2. Collections.synchronizedList，强制将 List 的操作加上同步；
• 3. Arrays.asList，不允许添加删除，但是可以用 set() 方法替换元素；
• 4. Collections.unmodifiableList，不允许修改内容，包括添加删除和 set() 方法。

1.5 CopyOnWriteArrayList

核心改进原理：

1. 写加锁，保证不会写混乱；

2. 写在一个Copy 副本上，而不是原始数据上（GC young 区用复制，old 区用本区内的移动）。

读写分离，最终一致。

在插入元素时，在新副本上操作，不影响旧的引用，不会阻塞读操作。

在删除元素时，如果删除末尾元素，直接使用前N-1个元素创建一个新数组；如果删除其他位置元素，创建新数组，将剩余元素复制到新数组。

使用迭代器遍历 CopyOnWriteArrayList 时，会先创建一个快照(把底层 array 的引用赋值给 snapshot)，之后读的都是这个快照，若后续发生了写操作（影响的是 array 指向的内存地址），修改不会影响 snapshot。（淘宝商品 item 的快照。商品价格会变，每次下单都会生成一个当时商品信息的快照, 也可以在修改商品时创建快照，这样没有做新的修改时都使用这个快照）

1.6 HashMap

基本特点：空间换时间，哈希冲突不大的情况下查找数据性能很高。
用途：存放指定 key 的对象，缓存对象。
原理：使用hash 原理，存k-v 数据，初始容量16，扩容x2，负载因子0.75。JDK8 以后，在链表长度到 8 && 数组长度到 64 时，使用红黑树。
安全问题：

1. 写冲突；
2. 读写问题，可能会死循环(两个线程并发进行 HashMap 的扩容，复制元素时并发执行可能会出现环)；
3. keys()无序问题。

1.7 LinkedHashMap

基本特点：继承自 HashMap，对 Entry 集合添加了一个双向链表。
用途：保证有序，特别是 Java8 stream 操作的 toMap 时使用。
原理：同 LinkedList，包括插入顺序和访问顺序。
安全问题：解决了 HashMap keys() 无序的问题，但是仍然存在写冲突和读写冲突的问题。

1.8 ConcurrentHashMap

JDK 7 为了实现并行访问，引入了 Segment 这一结构，实现了分段锁，理论上最大并发数与 Segment 个数相等。默认为 16 个 Segment，降低了锁的粒度。
想想：
Segment[] ~ 分库
HashEntry[] ~ 分表

JDK 8 为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组。对链表的头节点进行加锁。

1.9 并发集合类总结

2 并发编程相关内容*

2.1 线程安全操作利器 —— ThreadLocal

• 线程本地变量
• 场景: 每个线程一个副本
• 不改方法签名静默传参
• 及时进行清理

可以看做是Context 模式，减少显式传递参数。举一个例子，在一个线程中，有一个 10 个方法的调用链，其中，第 10 个方法需要传入一个参数，这个参数在中间 8 个方法中都没有使用，只存在于第 1 个方法中，这时我们只能给中间的 8 个方法都加上这个参数，但是这种方法并不优雅。在一些场景下，比如使用第三方包的情况下，中间这 8 个方法不能修改，无法为他们添加参数，这时，我们可以让第一个方法在 ThreadLocal 中设置一个值，然后第 10 个方法读取这个值，从而实现了隐式传参。（另一种隐式传参的方法是使用系统变量）

2.2 四两拨千斤 —— 并行Stream

JDK 8 中增加了 Stream API，对于一些需要多线程执行的场景，只需要加一个 parallel 即可。

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        IntStream.range(1, 10000).forEach(i -> list.add(i));
        BlockingQueue<Long> blockingQueue = new LinkedBlockingQueue(10000);
        List<Long> longList = list.stream()
                                    .parallel()
                                    .map(i -> i.longValue())
                                    .sorted()
                                    .collect(Collectors.toList());
        // 并行
        longList.stream()
                .parallel()
                .forEach(i -> {
                                try {
                                    blockingQueue.put(i);
                                } catch (InterruptedException e) {
                                    e.printStackTrace();
                                }
                            });
        System.out.println("blockingQueue" + blockingQueue.toString());
}

2.3 伪并发问题

• 跟并发冲突问题类似的场景很多
• 比如浏览器端，表单的重复提交问题
  — 1、客户端控制（调用方），点击后按钮不可用，跳转到其他页。
  — 2、服务器端控制（处理端），给每个表单生成一个编号保存在本地，表单第一次被提交后删除本地的编号，在多次提交时找不到本地的编号，从而判断出现重复。

2.4 分布式下的锁和计数器

• 分布式环境下，是多个机器在操作，超出了线程的协作机制，一定是并行的；
• 例如某个任务只能由一个应用处理，部署了多个机器，应该怎么控制？
• 例如针对某个用户的限流是每分钟 60 次计数，API 服务器有 3 台，用户可能随机访问到任何一台，怎
  么控制？（是不是很像秒杀场景？库存固定且有限。）

3 并发编程经验总结*

3.1 加锁需要考虑的问题

1. 粒度
2. 性能
3. 重入
4. 公平
5. 自旋锁（spinlock）
6. 场景: 脱离业务场景谈性能都是耍流氓

3.2 线程间协作与通信

线程之间进行通信的方式一般来说有两种：传递消息和共享内存。

1. 线程间共享:
   • static/实例变量（堆内存）
   • Lock
   • synchronized
2. 线程间协作:
   • Thread#join()
   • Object#wait/notify/notifyAll
   • Future/Callable
   • CountdownLatch
   • CyclicBarrier