一、简介

Java集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection接口又有3种子类型，List、Set和Queue，再下面是一些抽象类，最后是具体实现类，常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

• 接口：是代表集合的抽象数据类型。例如Collection、List、Set、Map等。之所以定义多个接口，是为了以不同的方式操作集合对象。
• 实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
• 算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。

Java不考虑多线程并发的情况下，容器类一般使用ArrayList、HashMap等线程不安全的类，效率更高。在并发场景下，常会用到ConcurrentHashMap、ArrayBlockingQueue等线程安全的容器类，虽然牺牲了一些效率，但却得到了安全。

二、普通容器

标准集合类汇总于下表：

2.1 List

2.1.1 ArrayList

ArrayList是基于数组实现的List类，它封装了一个动态的、增长的、允许再分配的Object[]数组。它允许对元素进行快速随机访问。

当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

2.1.2 LinkedList

LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。

另外，它还实现了Deque接口，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

2.2 Set

set的数据结构和方法大部分都是基于map实现的。

2.2.1 HashSet

HashSet是Set接口的典型实现，HashSet使用HASH算法来存储集合中的元素，因此具有良好的存取和查找性能。当向HashSet集合中存入一个元素时，HashSet会调用该对象的 hashCode()方法来得到该对象的hashCode值，然后根据该HashCode值决定该对象在HashSet中的存储位置。

2.2.2 LinkedHashSet

LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置，但和HashSet不同的是，它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的。

2.2.3 TreeSet

TreeSet可以确保集合元素处于排序状态。

2.3 Qeque

2.3.1 PriorityQueue

其实它并没有按照插入的顺序来存放元素，而是按照队列中某个属性的大小来排列的。故而叫优先队列。

2.3.2 ArrayDeque

基于数组的双端队列，类似于ArrayList有一个Object[]数组。

2.4 Map

2.4.1 HashMap

和HashSet集合不能保证元素的顺序一样，HashMap也不能保证key-value对的顺序。

2.4.2 LinkedHashMap

LinkedHashMap也使用双向链表来维护key-value对的次序，该链表负责维护Map的迭代顺序，与key-value对的插入顺序一致(注意和TreeMap对所有的key-value进行排序区分）。

2.4.3 TreeMap

TreeMap是一个红黑树结构，每个键值对都作为红黑树的一个节点。TreeMap存储键值对时，需要根据key对节点进行排序，TreeMap可以保证所有的key-value对处于有序状态。 同时，TreeMap也有两种排序方式：自然排序、定制排序（类似于上面List的重写CompareTo()方法）。

2.4.4 WeakHashMap

看名字就能发现，这是Weak后的HashMap。但是二者大体差别不大。

区别在于，HashMap的key保留了对实际对象的强引用，这意味着只要该HashMap对象不被销毁，该HashMap所引用的对象就不会被垃圾回收。

但WeakHashMap的key只保留了对实际对象的弱引用，这意味着如果WeakHashMap对象的key所引用的对象没有被其他强引用变量所引用，则这些key所引用的对象可能被垃圾回收，当垃圾回收了该key所对应的实际对象之后，WeakHashMap也可能自动删除这些key所对应的key-value对。

2.4.5 IdentityHashMap

这个类也和HashMap类似，区别在于，在IdentityHashMap中，当且仅当两个key严格相等(key1==key2)时，IdentityHashMap才认为两个key相等。

三、同步容器

为了方便编写出线程安全的程序，Java里面提供了一些线程安全类和并发工具，比如：同步容器、并发容器、阻塞队列、Synchronizer（比如CountDownLatch）。

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

上面提到的这些经过包装后线程安全容器，都是基于synchronized这个同步关键字实现，所以也被称为同步容器，Java提供的同步容器还有Vector、Stack和Hashtable，这三个容器并不是基于包装类实现，但同样是基于synchronized实现的，对这三个容器的遍历，同样要加锁保证互斥。

3.1 List

3.1.1 Vector

Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。所以现在已经不太常用了。

3.1.2 Stack

Stack是Vector提供的一个子类，用于模拟"栈"这种数据结构(LIFO后进先出)

3.2 Map

3.2.1 Hashtable

和HashMap类很相似，但是它支持同步。

3.2.2 Properties

Properties对象在处理属性文件时特别方便（windows平台的.ini文件）。Properties类可以把Map对象和属性文件关联，从而把Map对象的key - value对写入到属性文件中，也可把属性文件中的“属性名-属性值”加载进Map对象中。

四、并发容器

Java在1.5版本之前所谓的线程安全的容器，主要指的就是同步容器。不过同步容器有个最大的问题，那就是性能差，所有方法都用synchronized来保证互斥，串行度太高了。因此Java在1.5及之后版本提供了性能更高的容器，我们一般称为并发容器。

4.1 List

4.1.1 CopyOnWriteArrayList

并发版ArrayList，底层结构也是数组，和ArrayList不同之处在于：当新增和删除元素时会创建一个新的数组，在新的数组中增加或者排除指定对象，最后用新增数组替换原来的数组。

适用场景：由于读操作不加锁，写（增、删、改）操作加锁，因此适用于读多写少的场景。

局限：由于读的时候不会加锁（读的效率高，就和普通ArrayList一样），读取的当前副本，因此可能读取到脏数据。如果介意，建议不用。

4.2 Map

4.2.1 ConcurrentHashMap

最常见的并发容器之一，可以用作并发场景下的缓存。底层依然是哈希表，但在JAVA 8中有了不小的改变，而JAVA 7和JAVA 8都是用的比较多的版本，因此经常会将这两个版本的实现方式做一些比较（比如面试中）。

一个比较大的差异就是，JAVA 7中采用分段锁来减少锁的竞争，JAVA 8中放弃了分段锁，采用CAS（一种乐观锁），同时为了防止哈希冲突严重时退化成链表（冲突时会在该位置生成一个链表，哈希值相同的对象就链在一起），会在链表长度达到阈值8后转换成红黑树（比起链表，树的查询效率更稳定）。

4.2.2 ConcurrentSkipListMap

SkipList即跳表，跳表是一种空间换时间的数据结构，通过冗余数据，将链表一层一层索引，达到类似二分查找的效果

4.3 Set

4.3.1 CopyOnWriteArraySet

基于CopyOnWriteArrayList实现（内含一个CopyOnWriteArrayList成员变量），也就是说底层是一个数组，意味着每次add都要遍历整个集合才能知道是否存在，不存在时需要插入（加锁）。

适用场景：在CopyOnWriteArrayList适用场景下加一个，集合别太大（全部遍历伤不起）。

4.3.2 ConcurrentSkipListSet

类似HashSet和HashMap的关系，ConcurrentSkipListSet里面就是一个ConcurrentSkipListMap，就不细说了。

4.4 Queue

4.4.1 BlockingQueue

4.4.1.1 ArrayBlockingQueue

基于数组实现的可阻塞队列，构造时必须制定数组大小，往里面放东西时如果数组满了便会阻塞直到有位置（也支持直接返回和超时等待），通过一个锁ReentrantLock保证线程安全。

用offer操作举个例子：

乍一看会有点疑惑，读和写都是同一个锁，那要是空的时候正好一个读线程来了不会一直阻塞吗？

答案就在notEmpty、notFull里，这两个出自lock的小东西让锁有了类似synchronized + wait + notify的功能。

4.4.1.2 LinkedBlockingQueue

基于链表实现的阻塞队列，想比与不阻塞的ConcurrentLinkedQueue，它多了一个容量限制，如果不设置默认为int最大值。

4.4.1.3 SynchronousQueue

一个虚假的队列，因为它实际上没有真正用于存储元素的空间，每个插入操作都必须有对应的取出操作，没取出时无法继续放入。

一个简单的例子感受一下：

可以看到，写入的线程没有任何sleep，可以说是全力往队列放东西，而读取的线程又很不积极，读一个又sleep一会。输出的结果却是读写操作成对出现。

JAVA中一个使用场景就是

Executors.newCachedThreadPool()，创建一个缓存线程池。

4.4.1.4 LinkedTransferQueue

实现了接口TransferQueue，通过transfer方法放入元素时，如果发现有线程在阻塞在取元素，会直接把这个元素给等待线程。如果没有人等着消费，那么会把这个元素放到队列尾部，并且此方法阻塞直到有人读取这个元素。和SynchronousQueue有点像，但比它更强大。

4.4.1.5 PriorityBlockingQueue

构造时可以传入一个比较器，可以看做放进去的元素会被排序，然后读取的时候按顺序消费。某些低优先级的元素可能长期无法被消费，因为不断有更高优先级的元素进来。

4.4.1.6 DelayQueue

可以使放入队列的元素在指定的延时后才被消费者取出，元素需要实现Delayed接口。

4.4.2 BlockingDeque

4.4.2.1 LinkedBlockingDeque

类似LinkedBlockingQueue，但提供了双向链表特有的操作。

4.4.3 ConcurrentLinkedQueue

基于链表实现的并发队列，使用乐观锁(CAS)保证线程安全。因为数据结构是链表，所以理论上是没有队列大小限制的，也就是说添加数据一定能成功。

4.4.4 ConcurrentLinkedDeque

基于双向链表实现的并发队列，可以分别对头尾进行操作，因此除了先进先出(FIFO)，也可以先进后出(FILO)，当然先进后出的话应该叫它栈了。

五、总结

上面简单介绍了JAVA并发包下的一些容器类，知道有这些东西，遇到合适的场景时就能想起有个现成的东西可以用了。想要知其所以然，后续还得再深入探索一番。