集合基础

1.集合的接口与实现分离

 Java集合类库将接口与实现分离。

 例如：队列，队列接口指定可以在队列的尾部添加元素，在队列的头部删除元素，并且可以查找队列中元素的个数。当需要收集对象，并按照“先进先出”的规则检索对象时就应该使用队列。

 队列接口的最简形式可能类似下面这样：

public interface Queue<E> {
   void add(E element);
   E remove();
   int size();
}

 这个接口没有说明队列是如何实现的。队列通常有两种实现方式：一种是使用循环数组；另一种是使用链表。

队列的实现.jpg

 每一个队列的实现都可以通过一个实现了Queue接口的类表示(定义最抽象的接口，然后每一个具体的类具体实现)。
 当在程序中使用队列时，一旦构建了集合就不需要知道究竟是使用了哪种实现。因此，只有在构建集合对象时，使用具体的类才有意义。可以使用接口类型存放集合的引用。

Queue<Customer> expressLane = new CircularArrayQueue<>(100);
expressLane.add(new Customer("Harry"));

 利用这种方式，一旦改变了想法，可以轻松地使用另外一种不同的实现。只需要对调用构造器的地方进行修改：

Queue<Customer> expressLane = new LinkedListQueue<>();
expressLane.add(new Customer("Harry"));

 循环数组要比链表更高效，循环数组是一个有界集合，即容量有限。如果需要没有上限，需要使用链表。

2.Collection接口与Iterator迭代器

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

public interface Collection<E> {
    //用于向集合中添加元素
    boolean add(E element);
    //用于返回一个实现了Iterator接口的对象。可以使用这个迭代器对象依次访问集合中的元素。
    Iterator<E> iterator();
}

 Iterator接口包含4个方法：

public interface Iterator<E> {
   E next();
   boolean hasNext();
   void remove();
   default void forEachRemaning(Consumer<? super E> action)
}

 通过反复调用next方法，可以逐个访问集合中的每个元素。
 Iterator接口的remove方法将会删除上次调用next方法时返回的元素，如果调用remove之前没有调用next将是不合法的。

 "for each"循环可以与实现了Iterator接口的对象一起工作。Collection接口扩展了Iterator接口。因此，对于标准类库中的任何集合都可以使用"for each"循环。

 元素被访问的顺序取决于集合类型。如果对ArrayList进行迭代，迭代器将从索引0开始，每迭代一次，索引值加1。然而，如果访问HashSet中的元素，每个元素都会按照某种随机的顺序出现。

 Collection接口中包含大量的方法，为了能够让实现者更容易实现这个接口，Java类库提供了一个类AbstractCollection，它将基础方法size和iterator抽象化了，但是同时提供了很多例行方法。
 一个具体的集合类可以扩展AbstractCollection类，由具体的集合类提供iterator方法，而例如contains方法已由AbstractCollection超类提供了。

3.集合框架中的接口

集合框架的接口.jpg
 集合框架有两个基本接口：Collection(集合)和Map(映射)。

 可以用以下方法在Collection(集合)中插入元素：

boolean add(E element)

 由于Map(映射)包含键/值对，所以要用put方法来插入：

V put(K key, V value)

 要从集合(Collection)中读取元素，可以用迭代器访问元素。不过，从映射(Map)中读取值则要使用get方法：

V get(K key)

 对于有序集合(ordered collection)，例如List。可以采用两种方式访问元素：使用迭代器访问、使用一个整数索引来访问(随机访问)。
 实际中有两种有序集合(数组、链表)，其性能开销有很大差异。由数组支持的有序集合可以快速地随机访问，因此适合使用List方法并提供一个整数索引来访问。与之不同，链表尽管也是有序的，但是随机访问很慢，所以最好使用迭代器来遍历。

 Set接口(集)等同于Collection接口，不过其方法的行为有更严谨的定义。集(set)的add方法不允许增加重复的元素。要适当地定义集的equals方法：只要两个集包含同样的元素就认为是相等的，而不要求这些元素有同样的顺序。

 SortedSet和SortedMap接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集视图的方法。

 Java SE6引入了接口NavigableSet和NavigableMap，其中包含一些用于搜索和遍历有序集(ordered collection)和映射(Map)的方法。TreeSet和TreeMap类实现了这些接口。