容器在日常开发中经常会用到，但是对于一些容器的原理或者边角知识却不太容易被记起，所以作此总结，也算是复习也算是预习。
在本文中会穿插一些小问题，也算是比较好玩的知识，答案是我自己总结的，在面试中可能被问到，可以着重看一下，若有问题还望指出。其他的部分，比如说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的，为了实现迭代器的功能。
而我们查看源代码可以看到

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 浅谈