Java-容器List、Map、Set 和 Queue

梦里梦外; 2024-05-24 01:40 54阅读 0赞

> 本文介绍Java中的容器，包括：并发容器、同步容器。Java中容器List、Map、Set 和 Queue，但并不是所有的容器都是线程安全的。

#### 文章目录 ####

*  前言
 *  同步容器
 *  并发容器
 *   *  List
     *  Map
     *   *  ConcurrentHashMap和ConcurrentSkipListMap
         *  ConcurrentHashMap和HashTable
         *  底层数据结构
         *  线程安全
     *  Set
     *  Queue
     *   *  单端阻塞队列
         *  双端阻塞队列
         *  单端非阻塞队列
         *  双端非阻塞队列

## 前言 ##

Java 中的容器主要可以分为四个大类，分别是 List、Map、Set 和 Queue，但并不是所有的 Java 容器都是线程安全的，比如：ArrayList、HashMap。

## 同步容器 ##

在 Collections 这个类中还提供了一套完备的包装类，比如下面的示例代码中，分别把 ArrayList、HashSet 和 HashMap 包装成了线程安全的 List、Set 和 Map。

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

进行迭代遍历操作时，注意锁住容器再进行遍历操作，比如synchronized (list)

Collections 内部的包装类源码，包装类的公共方法锁的是对象的 this，其实就是我们这里的 list，所以锁住 list 绝对是线程安全的。

## 并发容器 ##

同步容器所有的方法加上synchronized来保证互斥，但也带来了性能问题，操作需要串行化。

Java中的并发容器分类：

1.  List: CopyOnWriteArrayList
2.  Map: ConcurrentHashMap，ConcurrentSkipListMap
3.  Set: CopyOnWriteArraySet，ConcurrentSkipListSet
4.  Queue：

*  单端阻塞队列： ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、LinkedTransferQueue、PriorityBlockingQueue 和 DelayQueue
 *  双端阻塞队列：LinkedBlockingDeque
 *  单端非阻塞队列：ConcurrentLinkedQueue
 *  双端非阻塞队列：ConcurrentLinkedDeque

### List ###

**写时复制**，**在往集合中添加数据的时候，先拷贝存储的数组，然后添加元素到拷贝好的数组中，然后用现在的数组去替换成员变量的数组**（就是get等读取操作读取的数组）。

这个机制和读写锁是一样的，但是比读写锁有改进的地方，那就是读取的时候可以写入的 ，这样省去了读写之间的竞争，同时写入的时候怎么办呢?当然果断还是加锁。

copyonwrite的机制虽然是**线程安全**的，但是在add操作的时候不停的拷贝是一件很费时的操作，所以使用到这个集合的时候尽量不要出现频繁的添加操作，而且在迭代的时候数据也是不及时的，数据量少还好说，数据太多的时候，实时性可能就差距很大了。

CopyOnWriteArrayList的get方法：get的方法就是普通集合的get没有什么特殊的地方，但是成员变量的声明还是有讲究的，是个用**volatile声明的数组**，这样就保证了读取的那一刻读取的是最新的数据。

CopyOnWriteArrayList的add方法: add方法了，**reentrantlock加锁**，接下来就是复制数据和添加数据的过程，在setArray的过程中，把新的数组赋值给成员变量array（这里是引用的指向，java保证赋值的过程是一个原子操作）。

### Map ###

<table> 
 <thead> 
  <tr> 
   <th>集合类</th> 
   <th>key</th> 
   <th>value</th> 
   <th>是否线程安全</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashMap</td> 
   <td>允许null</td> 
   <td>允许null</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td>TreeMap</td> 
   <td>不允许null</td> 
   <td>允许null</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td>HashTable</td> 
   <td>不允许null</td> 
   <td>不允许null</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>ConcurrentHashMap</td> 
   <td>不允许null</td> 
   <td>不允许null</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>ConcurrentSkipListMap</td> 
   <td>不允许null</td> 
   <td>不允许null</td> 
   <td>是</td> 
  </tr> 
 </tbody> 
</table>

#### ConcurrentHashMap和ConcurrentSkipListMap ####

ConcurrentHashMap 的 key 是无序的，而 ConcurrentSkipListMap 的 key 是有序的。所以如果你需要保证 key 的顺序，就只能使用 ConcurrentSkipListMap。

使用 ConcurrentHashMap 和 ConcurrentSkipListMap 需要注意的地方是，它们的 **key 和 value 都不能为空**，否则会抛出NullPointerException这个运行时异常。

ConcurrentSkipListMap 里面的 **SkipList 为“跳表”**。跳表插入、删除、查询操作平均的时间复杂度是 O(log n)，理论上和并发线程数没有关系，所以在并发度非常高的情况下，若你对 ConcurrentHashMap 的性能还不满意，可以尝试一下 ConcurrentSkipListMap。

#### ConcurrentHashMap和HashTable ####

#### 底层数据结构 ####

JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。

Hashtable和JDK1.8之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。

#### 线程安全 ####

**ConcurrentHashMap：**  
在 JDK1.7 的时候，ConcurrentHashMap（**分段锁**） 对整个桶数组进行了**分割分段(Segment)**，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率，在读的过程中，是不会进行加锁的。

JDK1.8的时候已经摒弃了Segment的概念，而是直接用**Node数组+链表+红黑树**的数据结构来实现，并发控制使用 **synchronized 和 CAS** 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。

**Hashtable：**  
Hashtable(同一把锁) ：使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

### Set ###

Set 接口的两个实现是 CopyOnWriteArraySet 和 ConcurrentSkipListSet，使用场景可以参考前面讲述的 CopyOnWriteArrayList 和 ConcurrentSkipListMap，它们的原理都是一样的。

### Queue ###

#### 单端阻塞队列 ####

ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、LinkedTransferQueue、PriorityBlockingQueue 和 DelayQueue

内部一般会持有一个队列，这个队列可以是数组（其实现是 ArrayBlockingQueue）也可以是链表（其实现是 LinkedBlockingQueue）；甚至还可以不持有队列（其实现是 SynchronousQueue），此时生产者线程的入队操作必须等待消费者线程的出队操作。而 LinkedTransferQueue 融合 LinkedBlockingQueue 和 SynchronousQueue 的功能，性能比 LinkedBlockingQueue 更好；PriorityBlockingQueue 支持按照优先级出队；DelayQueue 支持延时出队。

#### 双端阻塞队列 ####

其实现是 LinkedBlockingDeque。

#### 单端非阻塞队列 ####

其实现是 ConcurrentLinkedQueue。  
高效的并发队列，使用链表实现。可以看做一个线程安全的 LinkedList，这是一个非阻塞队列。

#### 双端非阻塞队列 ####

其实现是 ConcurrentLinkedDeque。