Java集合系列[1]-Collection框架

发表于

概述

下图是Collection框架的类关系图：
Collection架构图

Collection是一个接口，主要有2个分支，分别是List和Set。List和Set都是接口，他们都继承自Collection接口。List是有序队列，可以有重复元素；Set是数学概念中的集合，无序的，也是没有重复元素的（数学上的集合有三个特征：无序性、互异性、确定性）。

为了方便，JDK抽象出了AbstractCollection抽象类，它实现了Collection接口中大部分方法。这样在Collection的实现类中，就可以通过集成AbstractCollection省去了很多重复的编码工作。AbstractList和AbstractSet都继承自AbstractCollection，具体的List实现类继承自AbstractList（例如ArrayList、LinkedList、Vector、Stack等），而具体的Set实现类继承自AbstractSet（例如HashSet、TreeSet等）。

另外，Collection还继承Iterable接口，里面有一个iterator()方法，它返回Iterator接口。通常，我们可以通过Iterator迭代器来遍历集合。ListLiterator接口是List接口特有的，在List接口中，通过调用listIterator()返回一个ListIterator迭代器对象。

Collection接口

Collection的接口定义如下：

1
2
/* Collection的接口定义 */
public interface Collection<E> extends Iterable<E>

它是一个接口，是高度抽象出来的（OOP的四大特征之一）。它包含了集合的基本操作：添加、删除、遍历（读取）、修改、清空、获取大小、是否为空、是否保护某元素等。

Collection接口的所有子类（直接子类或间接子类）都应该提供2种标准的构造器：不带参数和带Collection参数。不带参数的构造器用来生成一个空集合，带Collection参数的构造器用来生成拥有一样元素的集合。JDK文档中是这样描述的：

All general-purpose Collection implementation classes (which typically implement Collection indirectly through one of its subinterfaces) should provide two “standard” constructors: a void (no arguments) constructor, which creates an empty collection, and a constructor with a single argument of type Collection, which creates a new collection with the same elements as its argument.

Collection的API如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* Collection的API */
boolean add(E e);
boolean addAll(Collection<? extends E> c);
void clear();//此方法用来清空Collection效率高,它把每个元素引用指向null，利于GC，时间复杂度为O(n)
boolean contains(Object o);
int size();
Iterator<E> iterator();
boolean isEmpty();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean remove(Object o);
boolean removeAll(Collection<?> c);//此方法用来清空Collection效率较低，因为要判断参数c集合中的元素是否在当前集合中；时间复杂度为O(n^2);
boolean containsAll(Collection<?> c);
boolean retainAll(Collection<?> c);//只在当前集合中保留参数c集合中存在的元素;
boolean equals(Object o);
int hashCode();
default boolean removeIf(Predicate<? super E> filter);//删除满足该Predicate的所有元素
default Spliterator<E> spliterator();//返回一个当前集合的分割迭代器，可用于流的并行计算
default Stream<E> stream();//返回当前集合的一个串行流
default Stream<E> parallelStream();//返回当前集合的一个并行流

List接口

List接口的定义如下：

1
2
/* List的接口定义 */
public interface List<E> extends Collection<E>

List是一个继承于Collection的接口，既List是Collection的一种。List是有序的队列，List中的每一个元素都有索引，第一个的索引值是0，往后依次加1。和Set不同，List中允许重复的元素。官方文档如下：

1
2
3
An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

List的API如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* List的API */
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
default Spliterator<E> spliterator();
/* List中新增的接口（涉及index的都是List新增） */
boolean addAll(int index, Collection<? extends E> c);
E get(int index); 
E set(int index, E element);
void add(int index, E element); 
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
default void replaceAll(UnaryOperator<E> operator);
default void sort(Comparator<? super E> c);

Set接口

Set的定义如下：

1
2
/* Set的接口定义 */
public interface Set<E> extends Collection<E>

Set也是Collection上一种。它没有重复的元素，是数学概念上的集合。官方文档解释如下：

1
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

Set的API如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Set的API， 完全和Collection的API一样 */
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
default Spliterator<E> spliterator();

AbstractCollection抽象类

AbstractCollection的定义如下：

1
public abstract class AbstractCollection<E> implements Collection<E>

AbstractCollection是一个抽象类，它实现了Collection接口中除了iterator()和size()之外的方法。它的主要作用是：实现了Collection接口中的大部分接口方法，从而方便其他类，比如ArrayList、HashSet等，他们这些类想要实现Collection接口，通过继承AbstractCollection就已经实现了大部分的接口方法了。但是注意AbstractCollection里面有个方法是是假实现，add()，它直接就抛出一个UnsupportedOperationException异常，并没有真正的实现。

AbstractList抽象类

AbstractList的定义如下：

1
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

AbstractList是一个抽象类，它实现了List中除get()、size()之外的接口方法，但是它的remove(), add(), set()都是假实现。 对比AbstractCollection，AbstractList实现了iterator()。

AbstractSet抽象类

AbstractSet的定义如下：

1
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>

AbstractSet是一个抽象类，由于Set的API完全和Collection一样，所以AbstractSet和AbstractCollection一样，没有实现iterator()、size()，但是它细化了AbstractCollection的很多实现。作用也是方便其他类实现Set接口。

Iterator

Iterator的定义如下：

1
public interface Iterator<E>

Iterator是一个迭代器，用来遍历集合中的所有元素。

Iterator的API如下：

1
2
3
4
boolean hasNext();
E next();
default void remove();
default void forEachRemaining(Consumer<? super E> action);

注意，Iterator遍历集合的时候，是fast-fail机制的。即，当线程A通过iterator去遍历集合的时候，如果该集合被线程B改变了，那么当线程A访问集合的时候，就会抛出ConcurrentModificationException异常，产生fast-fail事件。关于fast-fail我们后面再详细讨论。

ListIterator

ListIterator的定义如下：

1
public interface ListIterator<E> extends Iterator<E>

ListIterator是继承于Iterator接口的，它是一个队列迭代器，专门服务于List，能提供向前/向后遍历。相比于Iterator，增加了一些接口。官方文档描述如下：

An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator’s current position in the list. A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next().

ListIterator的API如下：

1
2
3
4
5
6
7
8
9
10
11
boolean hasNext();
E next();
void remove();
/* ListIterator新增的接口 */
boolean hasPrevious(); // 是否存在上一个元素
E previous(); // 获取上一个元素
int nextIndex(); // 获取下一个索引
int previousIndex(); // 获取上一个索引
void set(E e); // 设置
void add(E e);

Iterable

Iterable的定义如下：

1
public interface Iterable<T>

Iterable是一个接口，实现了这个接口的类都可以使用for-each loop语句来遍历，比如Collection继承了Iterable，所以所有的Collection都是可以使用for-each loop语句来遍历的。

Iterable的API如下：

1
2
3
Iterator<T> iterator(); // 获取迭代器
default void forEach(Consumer<? super T> action)；
default Spliterator<T> spliterator()；

参考文档