Java 并发 - 线程安全集合类
一、ArrayList
1.1 不安全用例
class ArrayListDemo {
public static void main(String[] args) {
List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 20; i++) {
new Thread(()->{
arrayList.add(UUID.randomUUID().toString().substring(0,8));
System.out.println(arrayList);
},String.valueOf(i)).start();
}
}
}
运行抛出 java.util.ConcurrentModificationException
1.2 导致原因
多线程并发对 arrayList 争夺写的权力，发生错误
1.3 解决方案
- 使用 vector<>()
- 使用 Collections.synchronizedList(new ArrayList<>());
- 使用 CopyOnWriteArrayList<>()
1.4 CopyOnWriteArrayList
1.4.1 读写分离
-
读不加锁，在原数组进行
-
写要加锁，使用 ReentrantLock ，加锁后复制一份数组，添加完后，将新数组引用赋给旧的数组
1.4.2 写时复制
写时复制指的是该类型数组在写的时候会复制一份新的数组
源代码如下：
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.4.3 比较
对比 ArrayList，在看源代码的时候，发现每次赋值都是以旧长度加一作为新数组的长度，分析源代码可知：
-
初始化容量
- ArrayList 初始化一个空数组，写的时候会再扩容为 10 大小的数组，相当于默认大小 10
- CopyOnWriteArrayList 初始化一个空数组，写的时候扩容为原数组容量加一大小的数组，默认大小为 0
-
扩容
- ArrayList 扩容时，扩容为原大小的 1.5 倍，写的时候只有容量不够才扩容
- CopyOnWriteArrayList 扩容时，扩容为原大小加一，写的时候每次都扩容，容量每次加一
-
删除
- ArrayList 删除时，将 index + 1后面的元素都往前移动一个位置，覆盖到 index 位置上
- CopyOnWriteArrayList 删除时，分别复制 index 前一截和后一截的元素，并将数组新引用赋值给旧的
发现，删除都很耗费时间，都是花费了 O(n)
-
适用场景
- ArrayList 适合单线程的场景，性能比较高
- CopyOnWriteArrayList 适合多线程条件，也适合读多写少的场景，但注意读的时候不一定是最新数据，也就是说它保证的是数据最终一致性而不是数据实时一致性；内存占用是 ArrayList 两倍，内存比较敏感的场景不适用
二、HashSet
2.1 不安全用例
class HashSetDemo {
private static Set<String> hashSet = new HashSet<>();
public static void main(String[] args) {
for (int i = 0; i < 30; i++) {
new Thread(() -> {
hashSet.add(UUID.randomUUID().toString().substring(0, 8));
System.out.println(hashSet);
}, String.valueOf(i)).start();
}
}
}
运行抛出 java.util.ConcurrentModificationException
2.2 导致原因
多线程并发对 hashSet 争夺写的权力，发生错误
HashSet 底层是 HashMap 实现的，每次 add ，调用 hashmap 的 put ，将值作为 hashmap 键，但 hashmap 的值是一个常量，当前 new 出来的常量，所以 HashMap 不安全，直接调用 hashmap 的方法也直接报错
2.3 解决方案
- 使用 Collections.synchronizedSet(new ArrayList<>());
- 使用 CopyOnWriteSet
2.4 CopyOnWriteSet
底层使用 CopyOnWriteArrayList 实现，因此保证了线程安全
三、HashMap
3.1 不安全用例
class HashMapDemo {
private static Map<String, String> hashMap = new HashMap<>();
public static void main(String[] args) {
for (int i = 1; i <= 30; i++) {
new Thread(() -> {
String name = Thread.currentThread().getName();
String val = UUID.randomUUID().toString().substring(0, 8);
hashMap.put(name, val);
System.out.println(hashMap);
}, String.valueOf(i)).start();
}
}
}
3.2 导致原因
多线程并发对 hashMap 争夺写的权力，发生错误
3.3 解决方案
- 使用 Collections.synchronizedMap(new HashMap<>());
- 使用 ConcurrentHashMap
3.4 ConcurrentHashMap
底层实现和 HashMap 类似，这里主要分析该容器并发原理
3.4.1 并发结构
1. JDK 1.7
-
Segment，分段锁，同时它继承 ReentrantLock，是一种可重入锁，基于数组和链表实现
-
HashEntry，桶，基于链表实现
2. JDK 1.8
- Node，值的节点，基于链表实现的节点
- TreeBin，值的节点，基于红黑树实现的节点
3.4.2 并发控制
1. JDK 1.7
ConcurrentHashMap = Segment 数组 + HashEntry 数组
一个 ConcurrentHashMap 里有一个 Segment 数组
Segment 数组里的每一个 Segment 包含一个 HashEntry 数组
HashEntry 数组里的每一个 HashEntry 都是一条链表
并发实现：
每一个 Segment 元素维护一个 HashEntry 数组，每次要对 HashEntry 数组某个元素修改，必须首先获得对应的 Segment 的锁
2. JDK 1.8
ConcurrentHashMap = Node 数组
一个 CocurrenHashMap 里有一个 Node 数组
Node 数组里的每一个 Node 都是一条链表
一条链表长度大于 8 的时候将 Node 转换为 TreeBin，即链表转为红黑树
并发实现：
首先采用 CAS 机制自旋操作，如果 CAS 操作失败的时，就使用 synchronized 加锁
synchronized 只锁定当前链表或红黑树的首节点，所以只要 hash 不冲突，就通过 CAS 方式写进去，就不会加锁