Java集合框架之Collection

2019独角兽企业重金招聘Python工程师标准>>>

1.Collection的类结构

Collection接口定义了增加元素、删除元素、包含判断、获取元素个数、交集、获取元素分离器、转成流、转成数组等操作。但是注意它没有包含获取元素的方法，这是因为有的实现类可以随机访问，有的不可以随机访问（只能靠逐个遍历获取）。记住Collection的接口定义，就基本掌握了集合的大部分能力。下图是Collection接口中定义的方法：

在Java 8之前，Collection提供了获取外部迭代器方法（iterator），利用外部迭代器，就可以遍历集合里面的元素，然后对每个元素进行操作。到了Java 8，Collection又提供了内部迭代方法（forEach），利用内部迭代器，我们只要告诉内部迭代器要对每个元素做什么操作，怎么遍历就完全交给集合自己了，此时遍历对于使用者是透明的。这两个方法都是定义在Collection的父接口——Iterable。利用外部迭代器Iterator遍历集合有两个问题，一是使用者要写一堆业务无关的遍历代码，二是只能单线程处理任务。而内部迭代只要写业务代码，还可以充分利用多线程并行处理任务，最大限度利用现代的多核处理器。下面是两段对比代码（提供一个点的集合，让每个点都向右向上各平移1个单位的距离）：

外部迭代（for-each语法糖，取代先获取Iterator再遍历的写法）：

List<Point> pointList = Arrays.asList(new Point(1,2),new Point(2,3));
for(Point p:pointList) {
	p.translate(1,1);
}

内部迭代（只要写业务代码，不需要写迭代代码）：

List<Point> pointList = Arrays.asList(new Point(1,2),new Point(2,3));
pointList.forEach(p -> p.translate(1,1));

看上面的类结构图，可以看到Collection分为三大类：

• List：有序集合，元素可重复。可以随机访问（增删改查都叫访问）。
• Set：无序集合，元素不可重复。更像数学概念中的集合，可以进行复杂的集合运算，比如交集、并集、差集……但是不能随机访问。
• Queue：队列，满足广泛存在的生产者-消费者业务模型。子接口Deque是双向队列，除了可以实现队列模型，还可以实现栈模型。

下面我们再逐一分析常用的实现类。

---

2.List实现类

List是有序集合，元素可重复。可以随机访问（增删改查都叫访问）。应用场景非常广泛。

List较常用的实现类有ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList……

ArrayList是基于数组实现的。基于数组实现的容器一定会涉及到容量（capacity）问题。ArrayList有确定的容量，它的默认初始容量是10，实例化的时候也可以自己指定。等到需要扩容的时候，容量变为原来两倍。所以在初始化的时候，要充分考虑扩容带来的性能问题。ArrayList基于数组实现，可以通过索引访问数据，所以随机访问效率很高。但是如果要往中间增加或删除一个元素，后面的元素下标全部要改变（本质上是重建索引），这时效率很低。所以它非常适合处理那种只顺序添加数据的场景。ArrayList没有进行同步，是线程不安全的。

LinkedList是基于双向链表实现的。因此它的容量不会受到限制。因为缺少索引，必须逐个遍历比对，所以它的随机访问性能比较差。但是如果往中间插一个元素或删一个元素，只要更改前后两个元素的指针即可，此时性能比ArrayList高。LinkedList也没有进行同步，是线程不安全的。

Vector也是基于数组实现的，提供的接口能力和ArrayList差不多。默认初始容量是10，扩容之后变为原来容量的1.5倍。Vector有个扩展类Stack，Stack提供了实现栈模型的方法。这两个类都是同步的，也就是线程安全的。具有很大的同步开销，一般很少用。

CopyOnWriteArrayList是Java并发包下的一个实现类，是支持高并发的线程安全实现类。看名称就知道，它也是基于数组实现的。但是它进行了读写分离，当要修改集合中的数据时，先copy一份数据出来，然后在备份数据中修改，修改好了再合并。读数据的时候没有同步，所以有可能读到的是老数据，但是最终能读到最新数据。这个类适合要求高性能，但是不要求严格一致性的场景。

再介绍两个知识点：

1. 利用Collections这个工具类可以实现基本的线程安全集合：

List list = Collections.synchronizedList(new ArrayList());

2. 在 Java 9 中，Java 标准类库提供了一系列的静态工厂方法，比如，List.of()、Set.of()，大大简化了构建小的容器实例的代码量。

List<String> simpleList = List.of("Hello","world");

---

3.Set实现类

Set是无序集合，元素不可重复。主要实现类有HashSet、TreeSet、LinkedHashSet……

学习Set只要记住一点，HashSet是由HashMap实现的，TreeSet是由TreeMap实现的，LinkedHashSet是由LinkedHashMap实现的。也就是说，Set是基于Map这种封装了一次的数据结构实现的，Map的Key就是Set里的元素，Map的Value是一个虚拟对象“PRESENT”。要理解Set各种不同实现的特性，就要先了解Map的各种不同实现的特性。可以参考：Java集合框架之Map 。

另外，Java 并发包中也有适合高并发场景的线程安全的实现类CopyOnWriteArraySet。原理和CopyOnWriteArrayList差不多。

---

4.Queue实现类

Queue 队列，满足广泛存在的生产者-消费者业务模型。子接口Deque是双向队列，除了可以实现队列模型，还可以实现栈模型。在Java并发包里面还定义了BlockingQueue，也就是线程安全的阻塞队列。下面两个表分别是Queue和BlockingQueue的主要方法（插入、移除、检查）：

Queue接口主要方法（两组方法，不同步）：

| -- | Throws exception | Returns special value | | :---- | :---- | : ---- | | Insert | add(e) | offer(e) | | Remove | remove() | poll() | | Examine | element() | peek() |

BlockingQueue接口主要方法（增加了一组会等待超时的方法，三组方法都是同步的）：

| -- | Throws exception |Special value Blocks | Times out | | :---- | :---- | : ---- | :------- | | Insert | add(e) | offer(e) | put(e) | |offer(e, time, unit) | | Remove | remove() | poll() | take() | |poll(time, unit) | | Examine | element() | peek() | not applicable | not applicable |

比较常用的实现类有PriorityQueue、PriorityBlockingQueue、ArrayBlockingQueue、ConcurrentLinkedQueue……

PriorityQueue优先队列跟普通队列比起来，多了一个比较器，如果实例化的时候没有指定比较器，就会使用自然排序。PriorityQueue的存储结构是个数组，但是逻辑结构是一颗完全二叉树。优先级最高的元素（用比较器比出来最大的元素）会成为根节点，每次消费的都是根节点，根节点被消费后，会根据比较器选出新的根节点。这里不展开论述，可以参考：Java堆结构PriorityQueue完全解析。

阻塞队列都是用ReentrantLock实现同步，所以性能方面不会好，主要在并发环境下使用。

ConcurrentLinkedQueue的实现原理可以类比ConcurrentHashMap，在Java 8以前是分段，之后用CAS等手段实现。具体可以参考：Java集合框架之Map 。

转载于:https://my.oschina.net/leaforbook/blog/1821461