转载

Java集合类总结

前言

之前一直做C++开发，在使用标准集合类的类库时都是使用的STL，觉的这个就是比C语言非常大的进步，很好用；后来玩Java，发现Java中的集合类更是好用，但是由于Java语言的发展原因，在使用的过程中也有很多坑，有很多的细节需要去处理。最近在进行组内代码评审时，就发现开发人员乱用集合类的情况。很多开发人员就不明白各个集合类的特性和使用场景，反正列表就用 ArrayList ，键值就用 HashMap ，仿佛在他们眼中Java的集合类就只有 ArrayList 和 HashMap 这两种。不怕大家笑话，曾经我也是这么使用的，今天就用一点时间，好好的对Java集合类的使用进行一次扫盲。

Java集合概述

Java提供的众多集合类由两大接口衍生而来： Collection 接口和 Map 接口。为了更好的把握Java集合类的整体结构，我这里先贴一个Java集合的整体类图，以便大家对Java集合类有一个整体的印象。

Java集合类总结

乍一看这个图很复杂，其实我们仔细梳理一下，这个图还是非常清晰的。可以这么看，在Java的集合类中，主要分为 List 、 Map 、 Set 和 Queue 这四大类，这四大接口类下面，又根据使用场景分为多个具体的子类。下面就一一进行总结。

Collection接口说明

从类图上可以看到， Collection 接口作为一个非常重要的基础接口，所以我们有必要对 Collection 接口中的常用方法进行一下说明和总结：

add ：向集合中添加单个元素
addAll ：向集合中批量添加元素
clear ：删除集合中所有元素
contains ：判断集合是否包含某个元素
isEmpty ：判断集合是否为空
iterator ：返回一个集合迭代器；关于迭代器可以参考这篇《 Java中的Enumeration、Iterable和Iterator接口详解》
remove ：从集合中删除单个元素
removeAll ：从集合中批量删除元素
retainAll ：保留指定入参集合中的元素，删除其它元素
size ：获取集合中元素个数
toArray ：将集合转换为数组

Map接口说明

同样的， Map 接口作为非常重要的接口，也有必要对其中的一些重要方法进行一些说明：

clear ：删除所有元素
containsKey ：判断是否包含某个键
containsValue ：判断是否包含某个值
entrySet ：将Map键值对以Map.Entry的形式放入Set集合中返回
get ：返回key值所对应的对象
isEmpty ：判断是否为空
keySet ：返回所有键的Set集合，这里有一篇文章《 JAVA中Map使用keySet()和entrySet()进行遍历效率的对比》可以看一看
put ：向Map中添加单个元素
putAll ：向Map中批量添加元素
remove ：删除Key所对应的对象
size ：获取Map中键值对的个数
values ：返回所有值的集合

说完这两大常用接口的常用方法，下面就对这两大接口衍生出来的常用集合类进行说明和总结。

List

List 用于定义以列表形式存储的集合， List 接口为集合中的每个对象分配了一个索引，用来标记该对象在List中的位置，并可以通过索引定位到指定位置的对象。

在我们开发过程中， List 类的集合出镜频率非常高，对于 List 类的集合，我们需要知道常用的有 ArrayList 、 LinkedList 、 Vector 、 CopyOnWriteArrayList ，特别是 ArrayList 和 CopyOnWriteArrayList 这两货，更是频繁出镜。

ArrayList
通过名称基本上就能看出来， ArrayList 基于数组实现的非线程安全的集合，在内部实现上，其维护了一个可变长度的对象数组，集合内所有对象存储于这个数组中，并实现该数组长度的动态伸缩。知道了内部的实现原理，那对于 ArrayList 来说，就有以下几个特性：
- 插入和删除元素性能较差
- 索引元素性能非常高
- 涉及数组长度动态伸缩，影响性能
如果涉及到频繁的插入和删除元素， ArrayList 则不是最好的选择。
LinkedList
LinkedList 基于链表实现的非线程安全的集合，在内部实现上，其实现了静态类Node，集合中的每个对象都由一个Node保存，每个Node都拥有到自己的前一个和后一个Node引用。对于 LinkedList 来说，它具备以下特性：
```
LinkedList
```
Vector
基于数组实现的线程安全的集合。线程同步（方法被 synchronized 修饰），性能比 ArrayList 差。当并发量增多时，锁竞争的问题严重，会导致性能下降。
CopyOnWriteArrayList
与 Vector 一样， CopyOnWriteArrayList 也可以认为是 ArrayList 的线程安全版，不同之处在于 CopyOnWriteArrayList 在写操作时会先复制出一个副本，在新副本上执行写操作，然后再修改引用。这种机制让 CopyOnWriteArrayList 可以对读操作不加锁，这就使 CopyOnWriteArrayList 的读效率远高于Vector。 CopyOnWriteArrayList 的理念比较类似读写分离，适合读多写少的多线程场景。但要注意， CopyOnWriteArrayList 只能保证数据的最终一致性，并不能保证数据的实时一致性，如果一个写操作正在进行中且并未完成，此时的读操作无法保证能读到这个写操作的结果。

CopyOnWriteArrayList 写时复制的集合，在执行写操作（如：add，set，remove等）时，都会将原数组拷贝一份，然后在新数组上做修改操作。最后集合的引用指向新数组。 CopyOnWriteArrayList 和 Vector 都是线程安全的，不同的是：前者使用 ReentrantLock 类，后者使用 synchronized 关键字。 ReentrantLock 提供了更多的锁投票机制，在锁竞争的情况下能表现更佳的性能。就是它让JVM能更快的调度线程，才有更多的时间去执行线程。这就是为什么 CopyOnWriteArrayList 的性能在大并发量的情况下优于 Vector 的原因。

对于 CopyOnWriteArrayList 来说，非常适合高并发的读操作（读多写少）的场景下使用。若写的操作非常多，会频繁复制容器，从而影响性能。

Map

Map 存储的是键值对，它将key和value封装至一个叫做Entry的对象中。每一个Map根据其自身的特点，都有不同的Entry实现，以对应Map的内部类形式出现。

根据我现在的开发情况来看， Map 比 List 类的集合更常用。对于 Map 类的集合有 HashMap 、 HashTable 、 SortedMap 、 TreeMap 、 WeakHashMap 和 ConcurrentSkipListMap 。

HashMap
HashMap 的底层是基于 数组+链表+红黑树 (JDK1.8+)的方式实现的。 HashMap 将 Entry 对象存储在一个数组中，并通过哈希表来实现对 Entry 的快速访问。感觉这里不放一张图，就不能更好的理解 HashMap 的实现方式了：

通过上图大家应该有一个整体的理解，我这里也不会对 HashMap 的实现原理进行更进一步的剖析。如果对 HashMap 的实现源码感兴趣，可以阅读《一文让你彻底理解 Java HashMap 和 ConcurrentHashMap 》和《 Java集合，HashMap底层实现和原理（1.7数组+链表与1.8+的数组+链表+红黑树）》这两篇文章。对于 HashMap 的一些特性这里进行列举：
- 当储存对象时，我们将键值对传递给put(key,value)方法时，它调用键对象key的hashCode()方法来计算hashcode，然后找到bucket位置，来储存值对象value
- hash表里可以存储元素的位置称为桶（bucket），如果通过key计算hash值发生冲突时，那么将采用链表的形式，来存储元素
- HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容；当数量达到了16 * 0.75 = 12就需要将当前16的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能
- 允许使用 null 建和 null 值
- 非线程安全
HashTable
HashTable 是 HashMap 的线程安全版， Hashtable 的实现方法里面都添加了 synchronized 关键字来确保线程同步。对于 HashTable 这种上古的东西，在开发中不建议使用了，因为现在已经提供了 ConcurrentHashMap 来使用。
ConcurrentHashMap

ConcurrentHashMap 是 HashMap 的线程安全版（自JDK1.5引入），提供比 Hashtable 更高效的并发性能。

HashTable 在进行读写操作时会锁住整个Entry数组，这就导致数据越多性能越差。而 ConcurrentHashMap 使用分离锁的思路解决并发性能，其将Entry数组拆分至16个Segment中，以哈希算法决定Entry应该存储在哪个Segment。这样就可以实现在写操作时只对一个Segment加锁，大幅提升了并发写的性能。在进行读操作时， ConcurrentHashMap 在绝大部分情况下都不需要加锁，其Entry中的value是volatile的，这保证了value被修改时的线程可见性，无需加锁便能实现线程安全的读操作。

ConcurrentHashMap 采用了分段锁技术，其中Segment继承于ReentrantLock。不会像 HashTable 那样不管是put还是get操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment数组数量)的线程并发。每当一个线程占用锁访问一个Segment时，不会影响到其他的Segment。

Set

Set 用于存储不含重复元素的集合，几乎所有的Set实现都是基于同类型Map的。简单地说，Set是阉割版的Map。每一个Set内都有一个同类型的Map实例（ CopyOnWriteArraySet 除外，它内置的是 CopyOnWriteArrayList 实例），Set把元素作为key存储在自己的Map实例中，value则是一个空的Object。 Set 的常用实现包括 HashSet 、 TreeSet 和 ConcurrentSkipListSet ，由于实现原理和对应的Map是完全一致的，所以这里就不再赘述。

在实际评审代码中，发现开发人员很少用 Set 类型的集合，即使有存储不含重复元素的场景，也都是使用 ArrayList 集合，然后结合着 contains 这种奇葩方式来实现。也就是说，一些基本功不扎实的开发人员，在脑海中就没有 Set 集合的概念。抱着实现功能就OK的心态，管他代码质量好不好，全凭 ArrayList 和 HashMap 闯天下。

Queue

Queue 用于模拟“队列”这种数据结构（先进先出FIFO）。队列的头部保存着队列中存放时间最长的元素，队列的尾部保存着队列中存放时间最短的元素。新元素插入到队列的尾部。这种队列基本都只是在小数据量的情况下使用，对于互联网应用来说，基本都是在使用分布式消息队列中间件。从文章开头的类图中可以看出， Deque 接口继承了 Queue 接口， Deque 接口代表一个“双端队列”，双端队列可以同时从两端来添加、删除元素，因此 Deque 的实现类既可以当成队列使用、也可以当成栈使用。对于我们来说，常用的 Queue 实现类有 ArrayDeque 、 ConcurrentLinkedQueue 、 LinkedBlockingQueue 、 ArrayBlockingQueue 、 SynchronousQueue 、 PriorityQueue 和 PriorityBlockingQueue 。

ArrayDeque
是一个基于数组的双端队列，和 ArrayList 类似，它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素，当集合元素超出该数组的容量时，系统会在底层重新分配一个Object[]数组来存储集合元素。
ConcurrentLinkedQueue
ConcurrentLinkedQueue 是基于链表实现的线程安全、无界非阻塞队列，队列中每个Node拥有到下一个Node的引用。它能够保证入队和出队操作的原子性和一致性，但在遍历和size()操作时只能保证数据的弱一致性。
LinkedBlockingQueue
与 ConcurrentLinkedQueue 不同， LinkedBlocklingQueue 是一种无界的阻塞队列。所谓阻塞队列，就是在入队时如果队列已满，线程会被阻塞，直到队列有空间供入队再返回；同时在出队时，如果队列已空，线程也会被阻塞，直到队列中有元素供出队时再返回。 LinkedBlocklingQueue 同样基于链表实现，其出队和入队操作都会使用ReentrantLock进行加锁。所以本身是线程安全的，但同样的，只能保证入队和出队操作的原子性和一致性，在遍历时只能保证数据的弱一致性。
ArrayBlockingQueue
ArrayBlockingQueue 是一种有界的阻塞队列，基于数组实现。其同步阻塞机制的实现与 LinkedBlocklingQueue 基本一致，区别仅在于前者的生产和消费使用同一个锁，后者的生产和消费使用分离的两个锁。
SynchronousQueue
SynchronousQueue 算是JDK实现的队列中比较奇葩的一个，它不能保存任何元素，size永远是0，peek()永远返回null。向其中插入元素的线程会阻塞，直到有另一个线程将这个元素取走，反之从其中取元素的线程也会阻塞，直到有另一个线程插入元素。这种实现机制非常适合传递性的场景。也就是说如果生产者线程需要及时确认到自己生产的任务已经被消费者线程取走后才能执行后续逻辑的场景下，适合使用 SynchronousQueue 。
PriorityQueue
PriorityQueue 是基于最小堆数据结构，可以在构造时指定 Comparator 或者按照自然顺序排序。优先队列有最大优先队列和最小优先队列，分别由最大堆和最小堆实现。 PriorityQueue 是非阻塞队列，也不是线程安全的。
PriorityBlockingQueue
PriorityBlockingQueue 实现原理同 PriorityQueue 一样，但是 PriorityBlockingQueue 是阻塞队列，同时也是线程安全的。

Deque 的实现类包括 LinkedList （前文已经总结过）、 ConcurrentLinkedDeque 和 LinkedBlockingDeque ，其实现机制与上面所述的 ConcurrentLinkedQueue 和 LinkedBlockingQueue 非常类似，此处不再赘述。