Java集合(一)：Java集合概述

注：本文基于JDK 1.7

1 概述

Java提供了一个丰富的集合框架，这个集合框架包括了很多接口、虚拟类和实现类。

这些接口和类提供了丰富的功能。可以满足主要的聚合需求。

下图就是这个框架的总体结构图：

能够看见，这个框架很大，大到惊讶的地步。这个图的左面部分是接口，右面部分是类。中间的线代表了右面的类实现了左面的哪些接口。比方，AbstractList类实现了List接口。那么继承自AbstractList类的子类都实现了这个接口。还有，假设一个类实现了一个接口，那么这个类也实现了这个接口的全部父接口。

比方，TreeSet类实现了Deque接口，那么TreeSet类也实现了Queue接口、Collection接口和Iterable接口（接口Collection扩展了Iterable。这里没显示出来）。

图中红色的类表示抽象类，大部分抽象类都以Abstract开头，除了Dictionary。绿颜色的类表示遗留类，这些类在Java一開始的时候就已经存在了。

2 接口与实现分离

Java集合类库中将接口（interface）与实现（implementation）分离。这里以队列（queue）为例。

队列接口指出能够在队列的尾部加入元素，在队列的头部删除元素，而且能够查找队列中的元素个数。即队列中的元素依照先进先出的元素使用队列。

假设我们设计queue的接口，可能这样设计：

interface Queue<E>

{

    void add(E element);

    E remove();

    int size();

}

这里给出了三个主要的方法。

这个接口没有给出队列应该是怎样实现的。通常。队列的实现方式有两种：一个是使用循环数组。一个是使用链表。

使用循环数组时须要指出对头head和队尾tail；使用链表时也须要给出头和尾：

class CircularArrayQueue<E> implements Queue<E>

{

    CircularArrayQueue(int capacity){...}

    public void add(E element){...}

    public E remove(){...}

    private E[] elements;

    private int head;

    private int tail;

}

class LinkedListQueue<E> implements Queue<E>

{

    LinkedListQueue(){...}

    public void add(E element){...}

    public E remove(){...}

    public int size(){...}

    private Link head;

    private Link tail;

}

上面的仅仅是我们自己实现的简单的队列，Java类库中没有这两个类。

当须要使用队列时，能够使用LinkedList类。这个类实现了Queue接口。

当在程序中使用队列时，一旦构建了集合就不须要知道到底使用了哪种实现。

因此，仅仅有在构建集合对象时，使用详细的类才有意义。能够使用接口类型存放集合的引用：

Queue<Employee> employee=new CircularArrayQueue<>(100);

employee.add(new Employee("Harry"));

利用这样的方式，一旦改变了想法，能够轻松地使用还有一种不同的实现。仅仅须要对程序的一个地方做出改动，即调用构造器的地方。

假设认为LinkedListQueue是个更好的选择，就能够这样改动：

Queue<Employee> employee=new LinkedListQueue<>();

employee.add(new Employee("Harry"));

接口本身没有给出详细的实现方式。因此也不能给出哪种实现更符合实际应用。

这样，选择哪种实现方式就须要由程序猿选择。Java类库中实现了非常多的类，每一个类都有各自的特性以及适用场景，或许选择了某个实现方式在某个特性上更加优秀，但也可能在还有一个特性上付出了代价。

怎样平衡好各个性能的代价。须要类库使用者自己把握。

在上图中，我们能够发现非常多红色的以Abstract开头的类，这些类都是抽象类，这些类是为类库的实现者设计的，这些类中实现了一些主要的方法。假设想要实现自己的队列类，你会发现扩展AbstractQueue类比实现Queue接口更方便。

3 Java类库中的集合接口和迭代器接口

在Java类库中，集合类的基本接口是Collection接口。这个接口中有例如以下两个方法：

boolean add(E element);

Iterator<E> iterator();

当然，除了这两个方法外还有其他的方法，会在后面介绍。

add方法用于向集合中加入元素，假设加入元素确实改变了集合就返回true，假设集合没有发生变化就返回false。

iterator方法用于返回一个实现了Iterator接口的对象。

能够使用这个迭代器对象依次訪问集合中的元素。

以下来介绍一下Java类库中重要的迭代器。

Iterator迭代器接口有三个方法：

public interface Iterator<E>

{

    E next();

    boolean hasNext();

    void remove();

}

通过重复调用next方法。能够逐个訪问集合中的每一个元素。

可是假设达到了集合的末尾，next方法将抛出一个NoSuchElementException异常。

因此，在调用next方法之前应该调用hasNext方法。假设迭代器对象还有多个供訪问的元素。这种方法就返回true。

因此，能够使用以下的方法訪问集合中的全部元素：

Collection<String> c=...;

Iterator<String> it=c.iterator();

while(it.hasNext())

{

    String element=it.next();

    do something with element

}

从Jave SE 5.0起。还能够使用for each循环訪问集合中的全部元素：

for(String element : c)

{

    do something with element

}

编译器仅仅是将这个for each循环翻译为带有迭代器的循环。

for each循环能够与不论什么实现了Iterable接口的对象一起工作。这个接口仅仅包括一个方法：

public interface Iterable<E>

{

    Iterator<E> iterator();

}

Collection接口扩展了Iterable接口。所以对于标准库中的不论什么集合都能够使用for each循环。

须要注意的是，元素被訪问的顺序取决于集合的类型。

假设对ArrayList进行迭代。迭代器将会从索引0開始。每迭代一次，索引值加1。然而，假设訪问HashSet中的元素。每一个元素将会依照某种随机的次序出现。尽管可以确定在迭代过程中可以遍历全部的元素。但却无法预知元素被訪问的次序。

Java集合类库中的迭代器与其他类库中的迭代器在概念上有着重要的差别。C++的迭代器是依据数组索引建模的。假设给定这样一个迭代器。就能够查看指定位置上的元素。就像知道数组索引i就能够查看数组元素a[i]一样。不须要查找元素，就能够将迭代器向前移动一个位置。

这与不须要运行查找操作就能够通过i++将数组索引向前移动一样。可是。Java迭代器不是这样操作的。

查找操作和位置变更是紧密相连的。查找一个元素的唯一方法是调用next。而在运行查找操作的同一时候，迭代器的位置随之向前移动。

即，能够将迭代器看做一个位置。这个位置在两个元素之间。

而next操作会改变这个位置。

但调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

Iterator接口的remove方法用于删除上次调用next方法返回时的元素。也就是说，remove操作和next操作具有依赖性，假设没有调用next方法而调用remove方法是非法的，会抛出一个IllegalStateException异常。

以下是删除集合中的第一个元素：

Iterator<String> it=c.iterator();

it.next();

it.remove();

假设删除两个相邻的元素，以下的方法是错误的：

it.remove();

it.remove();

必须先调用next方法越过待删除的元素：

it.remove();

it.next();

it.remove();

有一个不怎么恰当的比喻，能够将迭代器看做光标：

Collection<String> c=ArrayList<>();

c.add("a");

c.add("b");

c.add("c");

Iterator<String> it=c.iterator();

这时，迭代器的位置例如以下：

| a b c

当调用next方法，光标就会后移，然后返回刚才越过的元素：

it.next();

此时，迭代器的位置例如以下：

a | b c

并返回元素a。

假设要删除元素，删除的行为就像后退键（Backspace）一样，删除光标后面（以右为前）的元素：

it.remove();

此时，迭代器的位置例如以下：

| b c

和后退键不同的是，假设迭代器的后面即使还有元素，没有调用next方法也不能删除。

因为Collection接口和Iterator接口都是泛型接口，能够编写操作不论什么集合类型的有用方法。事实上，Collection接口中有非常多方法：

public interface java.util.Collection<E> extends java.lang.Iterable<E> {

  public abstract int size();

  public abstract boolean isEmpty();

  public abstract boolean contains(java.lang.Object);

  public abstract java.util.Iterator<E> iterator();

  public abstract java.lang.Object[] toArray();

  public abstract <T> T[] toArray(T[]);

  public abstract boolean add(E);

  public abstract boolean remove(java.lang.Object);

  public abstract boolean containsAll(java.util.Collection<?>);

  public abstract boolean addAll(java.util.Collection<? extends E>);

  public abstract boolean removeAll(java.util.Collection<?>);

  public boolean removeIf(java.util.function.Predicate<? super E>);

  public abstract boolean retainAll(java.util.Collection<?>);

  public abstract void clear();

  public abstract boolean equals(java.lang.Object);

  public abstract int hashCode();

  public java.util.Spliterator<E> spliterator();

  public java.util.stream.Stream<E> stream();

  public java.util.stream.Stream<E> parallelStream();

}

有非常多的方法的含义都非常明白，这里不做过多的解释。

当然，假设实现Collection接口的每个类都要实现这些例行方法将是一件非常烦人的事。为了能够让实现者更easy地实现这个接口，Java类库提供了一个AbstractCollection类，在这个类里提供了一些例行方法。这样。一个详细的集合类就能够扩展AbstractCollection类而不须要实现全部的例行方法了。并能够覆盖里面的方法。

4 Java类库中的接口

下图给出了Java类库中的全部接口：

当中。Collection和Map是集合框架的两个主要接口。全部的集合类都实现了这两个接口中的一个。Iterator接口和ListIterator接口是迭代器接口。而ListIterator接口提供了更丰富的操作，这个接口会在List列表中介绍。

RandomAccess接口是一个标签接口。也就是说这个接口没有不论什么方法。可是能够用这个接口标注某个类，然后检查一个类是否支持随机訪问。

在随后的介绍中，会具体介绍这些接口的方法和使用。

5 Java类库中的类

以下是Java类库中的全部实现类：

当中红颜色的是抽象类。能够明显的分为两个部分，一个集合（Collection），一个映射（Map）。

这些是经常使用的类，再加上一些专用的类，比方：EnumSet、LinkedHashSet、EnumMap、LinkedHashMap、IdentityHashMap和WeakHashMap，一共14类，它们的特点例如以下：

Java库中的详细集合
集合类型	描写叙述
ArrayList	一种能够动态增长和伸缩的索引序列
LinkedList	一种能够在不论什么位置进行高效插入和删除操作的有序序列
ArrayDeque	一种用循环数组实现的双端队列
HashSet	一种没有反复元素的无序集合
TreeSet	一种有序集
EnumSet	一种包括枚举类型值的集
LinkedHashSet	一种能够记住元素插入顺序的集
PriorityQueue	一种同意高效删除最小元素的集合
HashMap	一种存储键/值关联的数据结构
TreeMap	一种键值有序排列的映射表
EnumMap	一种键值属于枚举类型的映射表
LinkedHashMap	一种能够记住键值项加入次序的映射表
WeakHashMap	一种其值无用武之地后能够被垃圾回收器回收的映射表
IdentityHashMap	一种使用==而不是equals比較键值的映射表

对于有序无序、元素可反复和元素不可反复。特点总结例如以下。注意，对于Map，考察的是键的值是否可反复：

6 很多其它

在后序的分析中，会给出这些详细类和集合的介绍：

巴特西