Java集合框架中的接口

选择不同的数据结构，程序性能会有很大的不同。每当我们需要在巨量数据中快速搜索元素，或者在有序序列中快速插入删除元素，以及建立键与值之间的关联的时候，Java集合类就能帮上大忙。

1 接口与实现分离

Java的集合类实现了功能完善的数据结构。与常见的数据结构类库一样，Java集合类库也将接口（interface）与实现（implementation）分离。
接口与实现分离有什么好处。假设有一个Queue接口，用来描述队列。队列要包含这些方法：在尾部添加元素，在头部删除元素，查询元素个数。当需要获得队列里的元素，应该遵循先进先出的原则。队列有两种实现方式：使用循环数组，或者使用链表，实现类分别是 CircularArrayQueue 和 LinkedListQueue（实际上没有这两个类）。在程序中构造一个队列时，用接口变量来存放对象，如：

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

以后要是改变了想法，觉得 LinkedListQueue 是更好的选择，只需要修改代码中调用构造器的地方。

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

2 Collection 接口

Collection 是集合类的基本接口，它有两个基本方法：

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

add 方法向集合中添加元素，添加成功则返回 true，没加进去就返回 false。
iterator 方法返回一个实现了 Iterator 接口的对象，可以利用这个对象依次访问集合中的元素。
Collection 接口有许多实用方法，所有的实现类都必须提供这些方法。为了能更容易地实现这个接口，Java类库提供了一个 AbstractCollection 类，它实现了很多实用方法，这样就能通过继承 AbstractCollection 类来方便地实现这个接口。
Collection的hashCode方法应该类似于下面这样，用集合中每个元素的哈希码来计算集合对象的哈希码。这样就保证了 c1.equals(c2) 和c1.hashCode()==c2.hashCode() 的结果相同。

 int hashCode = 1;
 for (E e : collection)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

3 Iterator 接口

包含四个方法：

遍历集合对象中所有元素的正确做法是，先获得一个 Iterator，当 hasNext 返回 true 时反复调用 next。

Collection<String> c = . . .;
Iterator<String> iter = c.iterator();
while (iter.hasNext()) {
    String element = iter.next();
    . . .
}

更方便的做法是用“for each”循环，它能处理任何实现了 Iterable 接口的对象。编译器将 for each 循环转换为带 Iterator 的循环，等价于上面的代码。Collection 接口则是直接继承了 Iterable 接口。Iterable 接口只包含一个抽象方法：

public interface Iterable<E> {
    Iterator<E> iterator();
    . . .
}

访问元素的顺序取决于集合类型，如果迭代处理一个ArrayList，将从索引0开始，往后按1递增；如果访问HashSet，访问顺序是随机的，但也能遍历所有元素。Iterator 的查找操作和位置紧密耦合，只能调用 next 来查找一个元素，调用之后，迭代器就会越过这个元素并返回这个元素，然后到达下一个元素。如果想要删除一个元素，必须先越过它，也就是必须先调用 next 查找这个元素，然后再调用 remove 删除。删除相邻的元素就要交替调用 next 和 remove。

4 ListIterator

ListIterator 除了继承了 Iterator 的所有方法外，还增加了反向遍历，查询当前位置下标，插入元素等方法

集合类的 iterator 和 listIterator 方法返回的迭代器是fail-fast的。这意味着如果调用 iterator 和 listIterator 之后，在其它地方修改了集合对象的结构（比如调用对象本身的add, remove，或者被另一个迭代器修改了），迭代器就会抛 ConcurrentModificationException。但是这个异常不能保证百分百地按期望抛出，这是做不到的，这个异常只能被用来检测bug。

调用 set 方法不被视为修改集合对象的 #结构#，所以不会fail-fast。可以为一个list生成多个迭代器，所有迭代器都可以调用set方法修改当前list的内容。

5 List 接口

List 是有序集合，可以用迭代器访问（顺序访问），也可以用整数索引来访问（随机访问）。List 在Collection的基础上扩展了通过索引进行随机访问的方法：

静态工厂方法 List.of 和 List.copyOf 可以方便地生成不可变的 List 对象。这些 List 对象不能进行添加、删除、替换元素的操作；不允许有null元素；元素的次序跟原来的集合中元素的次序相同，或者跟参数的次序相同；不能对元素使用相等运算符，因为元素的内存地址是不确定的，可能直接引用源List中的元素，也可能是一个拷贝。不可变的List对象，如果其中包含的元素本身是可变的，对元素的字段进行修改就可能改变源List里的元素的字段。
static List copyOf(Collection<? extends E> coll)
static List of() // 创建空的不可变列表
static List of(E… elements) // 创建包含任意个元素的不可变列表
List 类的实例方法 boolean equals(Object o) 保证，只有当参数 o 是List，且元素数目以及元素顺序都相同，才返回true。

值得注意的是，List接口实现了一个默认的排序方法： default void sort(Comparator<? super E> c) 这个方法接受一个比较器对象，用它来对list中的元素进行两两比较。如果比较器为null，那么列表里的元素必须自己实现Comparable接口。调用sort方法的对象本身必须是可被修改的。 提示：Comparator 接口只有一个抽象方法 int compare(T o1, To2); Comparable 接口只有一个抽象方法int compareTo(T o); 。

由数组实现的有序集合可以快速地随机访问，适合用List本身的方法；而链表实现的有序集合适合用Iterator访问，因为随机访问链表非常慢。 为了避免对链表进行随机访问操作，Java有一个标记接口 RandomAccess。它不包含任何方法，专门用来测试一个集合对象是否适合随机访问：

if (c instanceof RandomAccess) {
    使用随机访问算法
} else {
    使用顺序访问算法
}

6 Set 接口

Set 接口和 Collection 接口等同，但是 Set 中不允许添加重复元素。实现 Set 接口的时候，要适当的定义 equals 方法：只要两个 Set 包含同样的元素就认为他们相等，而不要求顺序相同。hashCode方法也要保证元素相同而顺序可能不同的 Set 会得到相同的哈希值。
Set 也实现了静态工厂方法 List.of 和 List.copyOf，作用跟List里面的类似，不同在于Set不允许重复元素。
Set的实例方法 boolean equals(Object o) 只有当参数 o 是Set，且o里面的元素跟Set实例的元素完全一样，才返回true。

为什么**要在子接口里声明跟父接口一样的方法**？举例来说，Set和Collection源码基本是一样的，但是Set的方法添加了其它的约定，这些约定就要写在方法的注释里，所以要再次声明。这样也可以一目了然的看出Set包含的方法，不用去Collection找。

7 Queue 和 Deque 接口

在Collection的基础上，Queue增加了特别的插入，提取，查找方法。Queue的实现类既可以按先进先出来组织元素，也可以按后进先出来组织元素。

Deque的意思是double end queue，它能在队列的两端都进行插入和删除操作。类似于Queue，Deque的方法也有两类，这里不做详细说明。

Deque也可以当成Stack来使用，它提供了push和pop方法。

8 Map 接口

Map就是映射，用来存放键 / 值对。如果提供了键，就能查找到对应的值。Map中的键不能重复，每个键对应唯一的一个值。添加元素时，必须同时提供键和值。
Map 的 key 如果是字段可变的类，那么就不要修改Map对象里的元素的键，这种行为会导致键和值的对应关系被打乱，equals 和 hashCode 方法也会不正常。所以禁止将Map里的键设为 Map。但是值可以设为 Map。
集合框架不认为映射是一个Collection。不过，可以得到映射的视图View，这是实现了Collection接口或某个子接口的对象。有三种视图：键集、值集合、以及键/值对集。因为键和键/值对不允许重复。下面的三个方法分别返回这三个视图：
Set keySet()
Collection values
Set> entrySet()
对视图可以调用remove，但是不能添加元素。对视图的修改会影响到原来的Map，反之亦然

9 SortedMap