# Thread-safe Collection

在 [Collection](https://yunzhao.gitbook.io/notes/java/class-libraries/collection) 一节中提到，Java 容器有四大类：List、Set、Queue、Map。

## Synchronized Collection

把非线程安全的容器类变成线程安全的容器类最简单的方法是给每个方法添加 synchronized 关键字。例如工具类 Collections 就提供了一套静态方法：

```java
List list = Collections.synchronizedList(new ArrayList());
Set set = Collections.synchronizedSet(new HashSet());
Map map = Collections.synchronizedMap(new HashMap());
```

但是要注意的是，包装后的类虽然每个方法都是线程安全的，但是组合操作或者迭代器操作就不是线程安全的。比如正确的迭代操作需要给链表加锁：

```java
List list = Collections.synchronizedList(new ArrayList()); 
synchronized (list) { 
    Iterator i = list.iterator(); 
    while (i.hasNext()) 
        foo(i.next());
}
```

基于synchronized 的容器叫做**同步容器**，Java 还提供以下同步容器：

* Vector
* Stack
* HashTable

## Concurrency Collection

同步容器性能较差，因此 Java 1.5提供了**并发容器**。

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-Ld43t750LfxZRJoXQzP%2F-Ld45_iLd8WJARE4BIgV%2Fimage.png?alt=media\&token=4cf62c33-7597-467c-8570-f11ad275489b)

### List

List 里面只有一个实现类就是 `CopyOnWriteArrayList`。

**`CopyOnWrite`**：如果在遍历 Array 的同时，有一个写操作，那么会先将数据复制一份，然后在新的数组里面写入数据，完成之后指向这个新的数组。所以**读写是可以并行**的。

适用场景：

1. 写操作非常少；
2. 容忍短暂的读写不一致。

注意：迭代器是只读的，因为迭代器遍历的仅仅是一个快照。

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-Ld43t750LfxZRJoXQzP%2F-Ld479e5e6DJ1uabfOVv%2Fimage.png?alt=media\&token=639e1242-ffd5-47dc-8ddb-157596ea12b1)

### Map

#### ConcurrentHashMap

key 是无序的。

#### ConcurrentSkipListMap

key 是有序的。基于跳表实现，插入、删除、查询的平均时间复杂度为 O(logn)。

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-Ld43t750LfxZRJoXQzP%2F-Ld47bgj1bs8wyqsY6Ns%2Fimage.png?alt=media\&token=3aaefcaf-c930-4ccb-ab41-e67e5583185a)

### Set

* CopyOnWriteArraySet
* ConcurrentSkipListSet

### Queue

#### 阻塞与非阻塞

* **阻塞**：队列已满时，入队阻塞；队列以空时，出队阻塞；用 Blocking 标识。
* **非阻塞**：

#### 单端与双端

* **单端**：只能队尾入队，队首出队；用 Queue 标识。
* **双端**：队首队尾兼可入队出队；用 Deque 标识。

#### 单端阻塞队列

* **`ArrayBlockingQueue`**：数组实现；
* **`LinkedBlockingQueue`**：链表实现；
* **`SynchronousQueue`**：里面没有队列，生产者入队操作必须等待消费者出队操作；
* **`LinkedTransferQueue`**：融合 LinkedBlockingQueue 和 SynchronousQueue 的功能，性能比 LinkedBlockingQueue 好；
* **`PriorityBlockingQueue`**：支持按照优先级出队；
* **`DelayQueue`**：支持延时出队。

#### 双端阻塞队列

`LinkedBlockingDeque`

#### 单端非阻塞队列

`ConcurrentLinkedQueue`

#### 双端非阻塞队列

`ConcurrentLinkedDeque`

{% hint style="warning" %}
注意队列**是否有界**，仅 `ArrayBlockingQueue` 和 `LinkedBlockingQueue` 支持有界。
{% endhint %}