【集合】Java集合框架

　　Java类库中帮助我们在程序设计中实现了传统的数据结构。本文章跳过理论部分，主要介绍如何使用标准库中的集合类。

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

　　Java集合类库将接口与实现分离。以队列为例：

1 public interface Queue<E> extends Collection<E> {
2     boolean add(E e);
3 
4     E remove();
5 
6    /*
7       其他方法  
8   */  
9 }

上述代码为Java类库中队列的一部分代码，可以看到，这个接口没有说明队列是如何实现的。

队列通常有两种实现方式：

1.使用循环数组

2.使用链表

而在Java中，每一种实现都可以通过一个实现了Queue接口的类表示：

实现循环数组方式的双端队列，Java中使用 ArrayDeque类实现，这个类实现了继承自Queue接口的Deque接口，并使用一个数组存储队列中的元素。

实现链表方式的双堆队列，Java中的 LinkedList类通过实现同样的Deque接口实现。

使用接口与实现的模式，当程序中使用到队列时，一旦构建了集合便不需要知道使用了那种实现，当一旦改变了想法，可以轻松的在构建集合的位置改成另外一种实现。

2 Collection 接口

public interface Collection<E>
{
        boolean add(E element);
        Iterator<E> iterator();
        ...其他方法
}

add 方法用于添加元素，如果添加元素改变了集合就返回true，否则返回false。如果试图想一个集中添加一个已有对象，添加请求就不会生效，因为集中不允许存在重复对象。

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

3 迭代器

 1 package java.util;
 2 
 3 import java.util.function.Consumer;
 4 
 5 public interface Iterator<E> {
 6     boolean hasNext();
 7     E next();
 8     void remove();
 9     void forEachRemaining(Consumer<? super E> action);
10 }

Iterator 接口中包含4个方法：

　　next() :通过反复调用next()方法，可以逐个访问集合中的元素，但是如果到达了集合的末端，next方法将抛出一个 NoSuchElementException，因此，一般在调用next()方法前调用hasNext()方法。

　　hasNext() :如果迭代器对象还有供访问的对象，则返回true。

　　forEachRemaining:Java8中的遍历方法，参数为一个lambda表达式，迭代器将对每一个元素执行这个lambda表达式。

　　remove() :删除上次调用next方法时返回的元素，如果调用remove前没有调用next方法，这将是不合法的，会抛出一个 IllegalStateException 异常。

　　　　如果要删除两个相邻的元素，不能直接调用两次remove

iterator.remove();
iterator.remove(); //error

iterator.remove();
iterator.next();
iterator.remove(); //true

Collection 接口声明了许多实用的方法，为了让实现者更好实现Collection接口，Java提供了一个AbstractCollection的类，它将基础方法size和iterator抽象化了，而其他的方法提供了默认的实现，实现者只需要一个具体的集合类继承AbstractCollection类，就可以实现Collection接口。

4 集合框架中的接口

　　Java集合框架为不同类型的集合提供了大量的接口

集合中的两个基本接口：

　　Collection：

　　　　List 是一个有序集合，可以支持迭代器访问和随机访问。

　　　　Set 其add方法不允许增加重复的元素，因此使用时应适当地定义Set的equals方法：只要两个集包含同样的元素就认为是相等的；适当地定义hashCode方法：保证包含相同的元素的两个集会得到相同的散列码。

　　　　　　SortedSet 会提供用于排序的比较器对象，定义了可以得到集合子集的视图。

　　　　　　NavigableSet 包含一些用于搜索和遍历有序集的方法，TreeSet实现了这个接口。

　　　　Queue 是一个先进先出的队列。

　　　　Deque 双端队列

Map：包含键值对的映射

　　　SortedMap 会提供用于排序的比较器对象，定义了可以得到集合子集的视图。

　　　NavigableMap 包含一些用于搜索和遍历映射的方法，TreeMap实现了这个接口。

　　ListIterator 是Iterator 的一个子接口。它定义了一个方法用于在迭代器位置前面增加一个元素：void add(E element)

　　为了避免对链表进行随机访问操作，Java引入了RandomAccess标记接口，该接口不包含任何方法，但可以用它来测试一个集合是否支持随机访问。

if(c instanceof RandomAccess){
    使用随机访问
}else{
    使用迭代器访问
}