Java编程拾遗『容器概述』

在大学时，我们肯定都学过一门叫数据结构的课，里面详细的介绍了链表、栈、队列、散列、树、图等数据结构的概念及其实现。接下来的几篇文章将详细介绍一下Java API对常见数据结构的实现原理及应用，也就是Java API中的集合类(集合框架)。首先看一下Java集合框架的总体概况，如下：

总体而言，基本上可以分为两类，表示集合的Collection和表示K-V的Map。可以看到，所有的集合都间接实现了Collection接口，所有的Map都实现了Map接口。

1. 集合接口

1.1 Java集合设计思想

从上面集合框架的图中也可以发现一个规律，所有的具体集合类都会实现一个或多个接口，这其实就是Java API设计中，接口(interfaces)与实现(implementations)分离的思想。下面通过队列(queue)分离设计的例子，来解释一下这种实现思想的细节及优势。

我们都知道，队列是一种“先进先出”的数据结构，并且入队操作只能在队尾，出队操作只能在队头。所以队列接口应该提供方法，在队列尾部添加元素，在队列头部删除元素，并且可以查看队列中元素的个数，如下所示：

public interface Queue<E> {

    void add(E element);

    E remove();

    int size();
}

接口定义中，并没有说明队列是如何实现的。队列通常有两种实现方式：一种是使用循环数组，另一种是使用链表，如下所示：

 所以对于Queue接口可以有一下两种实现方式：

public class CircularArrayQueue<E> implements Queue<E> {

	public CircularArrayQueue(int capacity) {……}
	public void add(E element) {……}
	public E remove() {……}
	public int size() {……}

	private E[] elements;
	private int head;
	private int tail;
}

public class LinkedListQueue<E> implements Queue<E> {
	public LinkedListQueue() {……}
	public void add(E element) {……}
	public E remove() {……}
	public int size() {……}

	private Link head;
	private Link tail;
}

注意：这里讲的CircularArrayQueue和LinkedListQueue并不是Java API中真是存在的类，这里只是为了讲述一下Java集合的设计思想——接口和实现分离。实际上在Java API中，如果要使用一个循环数组队列，就可以使用ArrayDequeue，如果需要使一个链表队列，就可以使用LinkedList，这个类实现了Queue接口。

有如上两种队列的定义，在使用队列时，根据泛型类的继承规则，可以将实现类对象赋值给相同泛型类型的接口变量引用，如下：

Queue<Integer> queue = new CircularArrayQueue<>(100);
queue.add(1);

如果一旦改变了想法，就可以轻松的使用另一种不同的实现，只要对程序的一个地方做出修改，即修改调用构造器的地方就可以。如果觉得LinkedListQueue是个更好的选择，只需要将代码改为：

Queue<Integer> queue = new LinkedListQueue<>(100);
queue.add(1);

具体选用哪种实现，要根据具体需求而定。接口本身并不能说明哪种实现效率高，哪种实现效率低。循环数组队列一般情况下比链表队列效率高，但是循环数组是一个有界集合，容量有限。如果程序中要收集的对象没有上限，最好使用链表队列。

另外，仔细观察上面的集合框架图，也可以发现一个规律，一个具体的类一般会继承一个Abstract打头的抽象类，实现一个(多个)接口。这些Abstract打头的抽象类，其实也实现了相同的接口，并对接口中的一部分方法进行了实现。这些抽象类就是为类库实现者更方便的实现接口而设计的，比如如果我们要实现一个自定义队列，那么通过继承AbstractQueue类同时实现Queue接口的方式，要比直接实现Queue接口的方式要方便的多，因为一些通用方法已经在AbstractQueue中实现了。

1.2 Collection接口

所有的具体集合类都直接或间接实现了Collection接口，Collection接口定义了集合的一些通用方法，如下：

上面讲过，Java集合框架中，一个接口往往会对应一个抽象类，实现一些接口中的通用方法。Collection接口也不例外，在Java API中存在一个叫AbstractCollection的抽象类，提供一些基于迭代器Iterator的contains、remove、removeAll等方法的实现，这样就能让实现者更容易的实现Collection接口。如下：

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

	public abstract Iterator<E> iterator();

	//……
	public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    //……
}

1.3 迭代器Iterator

Java API中迭代器接口定义如下：

public interface Iterator<E> {

	boolean hasNext();

	E next();

	default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

1.3.1 遍历元素

通过反复调用next方法，可以逐个访问集合中的每一个元素。但是到达集合的末尾，next方法将抛出一个noSuchElementException异常。因此在调用next之前要调用hasNext方法，判断是否存在下一个元素。如果要遍历一个集合中的所有元素，就可以请求一个迭代器，并在hasNext返回true时反复地调用next方法，如下：

Collection<String> c = …… ;
Iterator<String> iterator = c.iterator();
while(c.hasNext()) {
	
	String element = iterator.next();
	//处理element
}

Java 5之后，这种循环可以采用一种更优雅的方式进行遍历——for each循环。Java编译器会简单地将“for each”循环翻译为带有迭代器的循环。如下：

for (String element : c) {
	//处理element
}

1.3.2 删除元素

Iterator接口的remove方法用于删除上次调用next方法时返回的元素。通过如下方式，可以删除集合中第一个元素：

Iterator<String> iterator = c.iterator();
iterator.next();
iterator.remove();

一定要注意的是，remove方法的调用对next方法具有依赖性。如果调用remove方法之前没有调用next方法将是不合法的，会抛出一个IllegalStateException异常。比如要删除两个连续的相邻元素，不能直接这样调用：

iterator.remove();
iterator.remove(); //remove前未调用next方法，异常

1.3.3 forEachRemaining

forEachRemaining是Java 8中新引入的default方法，方法的参数Consumer用于逐个消费集合中的元素，如下：

List<String> list = Lists.newArrayList("this", "is", "list");
list.iterator().forEachRemaining(ele -> System.out.println("consume :" + ele));

2. Map

Java API中Map用于保存具有映射关系(K-V)的数据，Map的key不允许重复。HashMap、LinkedHashMap、TreeMap都实现了Map接口，下面来看一下Map接口的方法定义：