Java集合
Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类。
接口：代表集合的抽象数据类型。例如 Collection、List、Set、Queue、Map 等，这些接口以不同的方式操作集合对象。
具体类：集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。Collections和Arrays提供了这些算法的实现。
下图是《Java编程思想》给出的Java集合框架：
点线框表示接口；实线框表示具体类；带空心箭头的点线表示一个特定的类实现了一个接口；带实心箭头的点线表示某个类可以生成箭头所指的对象；
迭代器（Iterator）
迭代器：迭代器就是对“逐一访问所有元素”这一操作的抽象。实际上就是对一组对象之间的位置，直接后继等关系的集成。
对序列进行遍历时，迭代器始终维护一个当前元素，并且提供访问序列下一个元素的机制，第一次对“访问下一个元素”操作的访问就会给出最初始的当前元素。
因而，根据这些描述，则迭代器必须有：
boolean hasnext() //检查是否有剩余元素 E getnext() //返回下一元素
1.Iterator接口
Iterator接口就是Java在Util包中提供的一个迭代器接口，其思路是通过iterator方法，每个集合均可创建并返回给客户一个实现了Iterator接口的对象，并且将当前位置的概念在对象内部存储下来。
其定义为：
public interface Iterator<E>{ boolean hasNext(); E next(); void remove(); //移除迭代器返回的最后一个元素 }
对于remove()操作，需要注意的是，调用一次remove()之后，不能再次调用该方法，除非又一次调用了next()方法。
2.Iterable接口
Iterable接口返回的是Iterator接口的一个实例，设置这一接口是为了让容器能有不同的遍历方式，通过继承Iterable接口，就能实现多个不同的Iterator类，例如前向迭代、反向迭代、随机迭代等等。
public interface Iterable<T> { Iterator<T> iterator(); }
3.集合类均实现Iterable接口的原因
1.Iterator接口的核心方法next()或者hasNext() 是依赖于迭代器的当前迭代位置的。 如果Collection直接实现Iterator接口，势必导致集合对象中包含当前迭代位置的数据(指针)。当集合在不同方法间被传递时，由于当前迭代位置不可预置，那么next()方法的结果会变成不可预知。 除非再为Iterator接口添加一个reset()方法，用来重置当前迭代位置。但即时这样，Collection也只能同时存在一个当前迭代位置。而Iterable则不然，每次调用都会返回一个从头开始计数的迭代器。多个迭代器是互不干扰的。
2.如上所说，让集合可以有更加灵活的迭代方式。
4.增强的for循环
当编译器看到一个正在用于Iterable对象的增强for循环时，它用对iterator方法的那些调用代替增强for循环以得到一个Iterator对象，然后调用其方法。
例如：
public static <E> void print(Collection<E> collection){ for(E item:collection){ System.out.println(item); } }
编译器将其重写为：
public static <E> void print(Collection<E> collection){ Iterator<E> it = collection.iterator(); while (it.hasNext()){ E item = it.next(); System.out.println(item); } }
Collection与Map
Collection抽象了集合的概念，它存储一组同一类型的对象。其关键接口(部分)如下：
public interface Collection<E> extends Iterable<E>{ int size(); //返回元素数量 boolean isEmpty(); //判断是否为空 void clear(); //清空集合 boolean contains(E x); //判断是否包含某元素 boolean add(E x); //添加某元素 boolean remove(E x); //移除某元素 Iterator<E> iterator(); //返回一个迭代器 Object[] toArray(); //返回一个由这些元素组成的对象数组 }
Map是一种存放一组条目的容器，条目是一种形如(key,value)的组合对象。其关键接口(部分)如下：
public interface Map<K,V>{ int size(); boolean isEmpty(); void clear(); boolean containsKey(Object Key); //判断是否包含某键 boolean containsValue(Object value); //判断是否包含某元素 V get(Object key); //获取某键对应的元素 V put(K key,V value); //添加某键值对 V remove(Object key); //移除某键对应的键值对 V replace(K key,V value); //仅当某键对应有值时替换该值 boolean replace(K key,V oldValue,V newValue); //替换为新值，若无对应旧值，则添加 }
Comparator与Comparable
1.Comparator接口
Comparator是比较器接口，可以实现比较器接口来构建一个比较器，即定义了该类的实例的大小规则。常用方法是将其提供给序列的排序函数。
其定义为：
public interface Comparator<T> { int compare(T o1, T o2); boolean equals(Object obj); }
值得注意的是，任何对象都已实现了equals(Object obj)方法，故实现Comparator接口时可只实现compare方法不实现equals方法。
2.Comparable接口
Comparable可以看作排序接口，任何实现了Comparable接口的类可支持排序，将其称作”自然排序“。例如某list中的类实现了Comparable接口，那么可以使用Collections.sort(list)来对list进行排序。
其定义为：
public interface Comparable<T>{ int comparaTo(T o); }
值得注意的是，需要确保ComparaTo方法与equals方法的结果保持一致，否则会出现一些问题(在有序集或有序映射与自然排序一起使用时会表现会超出预期，显得奇怪)，因而建议重写equals方法。
综上来说，可以将Comparable接口看作”内部比较器"，类实现了comparable接口之后，可以直接调用排序方法；而可以将Comparator接口看作”外部比较器“，当类的设计者没有考虑类的排序时，可以将类与Comparator接口绑定，从而实现排序。
一个实例：
import java.util.*; public class Test { public static void main(String[] args) throws InterruptedException { ArrayList<Person> list = new ArrayList<>(); list.add(new Person("Ming",171)); list.add(new Person("Hong", 165)); list.add(new Person("Xi",165)); list.add(new Person("Long",181)); System.out.println(list); Collections.sort(list); //使用自然排序 System.out.println(list); Collections.sort(list,new PersonComparator()); //使用外接比较器排序 System.out.println(list); } private static class Person implements Comparable<Person>{ String name; int tall; Person(String name, int tall) { this.name = name; this.tall = tall; } public String toString(){ return name + "-"+ tall; } @Override public int compareTo(Person person) { //实现自然排序接口，按照名字排序 return name.compareTo(person.name); } boolean equals(Person person){ //重写equals规则 if (this.name.equals(person.name)){ return true; } return false; } } static class PersonComparator implements Comparator<Person> { //实现比较器接口，按照身高排序 @Override public int compare(Person p1, Person p2) { return p1.tall - p2.tall; } } } //结果 [Ming-171, Hong-165, Xi-165, Long-181] [Hong-165, Long-181, Ming-171, Xi-165] [Hong-165, Xi-165, Ming-171, Long-181]
Collections
Collections仅包含对集合进行操作或返回集合的静态方法，它包含对集合操作的多态算法。其中部分关键API如下（参数已省略）：
public class Collections extends Object{ boolean addAll()； //为集合添加给定元素 Queue<T> asLifoQueue(); //将Deque变为先进后出的Queue int binarySearch(); //二分查找某对象 xxx checkedxxx(); //返回指定xxx的动态类型安全视图 void copy(); //将列表里所以元素拷贝到另一个列表 boolean disjiont(); //判断两个集合是否有交集 xxx emptyxxx(); //返回一个空的xxx集合 void fill(); //用给定的对象填充集合 int frequency(); //返回集合中等于指定对象的元素数量 int indexOfSubList(); //返回目标列表在源列表的起始位置 int lastindexOfSubList(); //返回目标列表在源列表的结束位置 T max(); T min(); void reverse(); //反转集合 void rotate(); //按指定距离轮转集合 void shuffle(); //置乱集合 void sort(); //排序集合 void swap(); //交换指定两个元素 xxx synchronizedxxx(); //返回线程安全的xxx xxx unmodifiablexxx(); //返回不可修改的xxx视图 }
Arrays
Arrays包含用于操作数组的各种方法以及asList()方法，其部分API如下(参数已省略)：
public class Arrays extends Object{ List<T> asList(T... a) //给定对象创建一个列表 int binarySearch(); //二分查找某值 int compare(); //按字典顺序比较两个值 int compareUnsigned(); //按字典顺序比较两个值,这两个值视为无符号的 xxx copyOf(); //拷贝数组指定长度的元素 xxx copyOfRange(); //指定起始位置和长度来拷贝数组元素 int mismatch(); //查找两个数组第一个不匹配的索引 void parallelPrefix(); //并行地对给的子数组的所有元素施加某种操作 void parallelSetAll(); //使用生成器函数并行地设置给的子数组的所有元素 void parallelSort(); //并行排序 void sort(); //排序 Spliterator<T> Spliterator(); //返回覆盖指定数组地拆分器 Stream<T> Stream(); //返回指定数组元素构成的流 String toString(); boolean equals(); //判断两元素是否相等 void fill(); //以指定元素填充数组 int hashCode(); boolean deepEquals(); //deepxxx适用于嵌套数组的情况 int deepHashcode(); String deepToString(); }
后续为集合框架中的那些实现类以及对应的数据结构。