容器在日常开发中经常会用到，但是对于一些容器的原理或者边角知识却不太容易被记起，所以作此总结，也算是复习也算是预习。
在本文中会穿插一些小问题，也算是比较好玩的知识，答案是我自己总结的，在面试中可能被问到，可以着重看一下，若有问题还望指出。其他的部分，比如说API，简单看下即可，使用可以自行查阅API文档，更深入的知识将在文末链接的其他文章中指出。
还有一点要注意的是：某些知识点会随着深入而修正（比如说开场的图，就没有包含Queue），这套路貌似跟我们学习数学一样。
1. 简单分类
Java所提供的容器相关API位于java.util中，而一个比较简洁的结构组织如下，在掌握各种各样的容器之前，读懂这幅图至关重要。
可以看到所有的容器会以Collection和Map为父接口来实现的，而Collection的特点就是装的时候是单个元素，Map的特点就是装的时候是键值对。
而我们再看Collection的第二层，分别是Set和List，前者是要求数据没有顺序且不可以重复，而后者的数据是有顺序且可以重复的。
而最下面的相关实现类，远远不止这些，暂时先做简单了解。
2. Collection
public interface Collection<E> extends Iterable<E> {
int size(); //集合大小
boolean isEmpty(); //是否为空
boolean contains(Object o); //包含某个对象
Iterator<E> iterator(); // 返回迭代器
Object[] toArray(); //转换成object数组
<T> T[] toArray(T[] a); //转换成泛型数组
boolean add(E e); //添加一个元素
boolean remove(Object o); //删除一个元素
boolean containsAll(Collection<?> c); //包含另一个集合里的全部元素
boolean addAll(Collection<? extends E> c);//添加另一个集合里的全部元素
boolean removeAll(Collection<?> c); //移除另一个集合里的全部元素
boolean retainAll(Collection<?> c); //求两个集合的交集，并复制给this
void clear(); //清空
boolean equals(Object o); //object equals方法
int hashCode(); //object hashCode方法
}
上面是Collection中定义的相关方法（default未列出），根据字面意思我们就能知道它包含什么功能。
Collection像个协议，实现它的相关容器类就一定要实现它的方法。
要知道Collection是继承自Iterable的，为了实现迭代器的功能。
而我们查看源代码可以看到
iterator方法正是这个接口所提供的，这个方法会返回一个Iterator（遍历器，用于遍历访问），而Iterator也是一个接口，所定义的的方法如下：
//default方法均未列出。
public interface Iterator<E> {
boolean hasNext(); //有下一位
E next(); //取出下一位数据
void remove()； //后期改为default方法，用于删除next元素，迭代期间会加锁，可以用于安全删除。
}
可以看出内部定义很简单，就是若有则取的一种方式。
Q1：为什么要实现这样一个接口？为什么不在Collection里统一定义get方法？
由于我们的容器底层有很多数据结构支撑，比如说ArrayList的数组，LinkedList的链表，学过数据结构的童鞋都知道，两者的遍历方式，取值方式都不一样，这里还是仅仅举了两个例子，还有更多的操作都不一样，所以为了实现各种特殊的方法，就使用了Iterator了。
Q2：补充：foreach
foreach是一种增强的for循环，内部还是依靠于Iterator实现，但是不能实现remove操作，不方便删除集合中的内容，与传统for相比不能方便读取下标。注意一个要点，Iterator内部remove是锁定方法，意味着当使用Iterator遍历容器的时候，容器本身的remove方法是不可用的，所以同理foreach也用不了。
3. Set （集合）
Set的特点上面说过，（添加）不一定有顺序，但一定不重复。
而Set接口内部提供的方法跟Collection是一样的（除个别方法外），所以参考一下上面说过的Collection接口，相关内容在后面介绍。
4. List
List实现的容器是（添加）有序的，且可以重复的，List是有访问的下标的，所以平时用的比较多的还是List的相关实现，如ArrayList，LinkedList，但是List相比Collection的话，增加了一些List相关操作方法，如下：
/*排序*/
default void sort(Comparator<? super E> c)
/*取得指定索引的元素*/
E get(int index);
/* 替换迭代器游标位置的数据，具体规则暂不深究*/
void set(E e);
/*替换index位置的元素为element，返回旧数据*/
E set(int index, E element);
/* 按照位置要求插入数据*/
void add(int index, E element);
/* 返回元素o的第一次出现的位置*/
int indexOf(Object o);
/* 元素o最后一次出现的位置 */
int lastIndexOf(Object o);
/* 返回一个列表iterator*/
ListIterator<E> listIterator();
/* 返回一个从指定位置开始的列表iterator */
ListIterator<E> listIterator(int index);
/* 截取一个子列表 */
List<E> subList(int fromIndex, int toIndex);
这里有一个listIterator我们需要认识一下,大部分方法的原理还是跟我们上面说过的Iterator一样。
public interface ListIterator<E> extends Iterator<E>{
//next组
boolean hasNext();
E next();
//previous组
boolean hasPrevious();
E previous();
//返回对 next 的后续调用所返回元素的索引。（如果列表迭代器在列表的结尾，则返回列表的大小）。
int nextIndex();
//返回对 previous 的后续调用所返回元素的索引。（如果列表迭代器在列表的开始，则返回 -1）
int previousIndex();
//移除元素方法
void remove();
//替换和添加操作
void set(E e);
void add(E e);
}
5. Collections
这个类实现了一些常用的容器工具算法，（注意区分Collection接口和Collections）
常用的如下：
void shuffle(List<?> list) //随机排序
<T> void fill(List<? super T> list, T obj) //数据填充
<T> void copy(List<? super T> dest, List<? extends T> src) //列表复制
int binarySearch(List<? extends Comparable<? super T>> list, T key) //二分查找
<T> void sort(List<T> list, Comparator<? super T> c) //排序
现在来深究一下sort方法。
看一下源代码
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}
仅仅是调用了list的sort方法，继续查看list.sort方法。
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
可以看到list.sort方法是有默认实现的，但是内部也就是调用Arrays.sort方法来排序的。
我们看到的sort方法中，除了待排序数组之外，还有一个Comparator接口，相信它的意思应该很显而易见。
举个例子，1 < 10, 2.0 < 10.0 这种问题很显然。
但是比如说给你studentA 和 studentB ，你如何确定A和B的大小，这就要求我们使用Comparator来定义他们的大小。
在说Comparator之前，我们要先明白一个东西。
我下面贴两个源代码：
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}
这是Collections提供的两个排序方法，可以看到第一个是要求数据类实现Comparable接口，第二个是要求比较的时候传入Comparator对象，那这二者有什么区别呢？
答： 没啥区别，调皮了。
看一下Comparator的这一个核心方法，用于判断o1和o2的大小。
int compare(T o1, T o2);
官方文档说： return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
也就是 若 o1 < o2 返回负数，o1 = o2 返回0 ，o1 > o2返回正数。
再看一下Comparable。
虽然参数不一样，但是注释一模一样,也就是功能一样。
Q3：那为什么还要有这两者呢？
考虑一下Comparable的用法是要实现，Comparator的用法是包装的方式，所以你能想到，如果你要用前者，在版本迭代中加入，就要修改类的源代码，如果用后者，只需要新建一个包装类即可，同时后者也可以实现一些复杂的操作，具体可以自行体验一下。
接下来我们来看一下Integer里的这个方法（必然是有实现的）
可以看到，确实是有自己实现。
所以按照简单的写法，我们将自己的类实现Comparable接口即可。
6. Map
键值对存储方式，实现类如HashMap（哈希表实现），TreeMap(红黑树实现)，键值不允许重复。
下面给出Map中一些常用的方法定义（跟Collection类似的方法就不说了）
public interface Map<K,V> {
/* 是否包含某键*/
boolean containsKey(Object key);
/*是否包含某值*/
boolean containsValue(Object value);
/*通过key取值*/
V get(Object key);
/* 添加键值对，如果已有相应键，替换，返回替换前的值*/
V put(K key, V value);
/* 通过key删除某键值*/
V remove(Object key);
/* 批量添加*/
void putAll(Map<? extends K, ? extends V> m);
/* 返回键集合*/
Set<K> keySet();
/*返回值集合*/
Collection<V> values();
/*返回键值对集合*/
Set<Map.Entry<K, V>> entrySet();
}
7. 总结
本文作为对于容器的相关回顾和总结，提到了一些简单的API和琐碎的知识点。
首先是一张图，这个很重要，但是这张图不是详细的图，只是一个大致的结构。
然后穿插说了迭代器和比较器两种辅助工具。
其次还有提到过三个Question，也比较有意思。
对于其他知识，应该是学习阶段就要了解的，但是不了解也无所谓，可以查阅API文档，不难理解。
8. 相关文章
Set系列：
HashSet 浅谈
