　　Java.util中的容器又被称为Java Collections framework。虽然被称为框架，但是其主要目的是提供一组接口尽量简单而且相同、并且尽量高效、以便于开发人员按照场景选用，而不是自己重复实现的类。容器按接口可以分为两大类：Collection和Map。本文主要关注Collection，以后会将Map这块也进行研究。

一、Collection及子类/接口容器继承关系

　　先从Collection说起。可以看出：

1.Collection接口并不是一个根接口，它的超级接口是Iterator，需要提供其遍历、移除元素(可选操作)的能力。

2.Collection接口定义了基本的容器操作方法。

　　除此以外，

1.remove()和contains()判断元素是否相等的依据是类似的。

对于remove(Object o)，若Collection中包含的元素e，满足(o==null ? e==null : o.equals(e))，移除其中的一个；

对于contains(Object o)，若Collection中包含至少一个或多个元素e，满足(o==null ? e==null : o.equals(e))，则返回true。

2.AbstractCollection抽象类实现了一部分Collection接口的方法，主要是基于iterator实现的，如remove()、toArray()，以及利用本身的属性size实现的size()。如果读一下源码，可以发现虽然AbstractCollection利用add()实现了addAll()，但是add()本身的实现是直接抛UnsupportedOperationException异常的。实际上add()是一种“可选操作”，目的是延迟到需要时再实现。

二、List

　　了解了通用的Collection后，接下来，看看三大类的Collection:List、Set、Queue。首先从List说起。List中的元素是有序的，因而我们可以按序访问List中的元素，以及访问指定位置上的元素。对于“按顺序遍历访问元素”的需求，使用List的超级接口Iterator即可以做到，这也是对应抽象类AbstractList中的实现；而访问特定位置的元素（也即按索引访问）、元素的增加和删除涉及到了List中各个元素的连接关系，并没有在AbstractList中提供。

2.1 ArrayList

　　ArrayList是最常用的List的实现，其包装了一个用于存放元素的数组，并用size属性来标识该容器里的元素个数，而非这个被包装数组的大小。如果对数组有所了解，很容易理解ArrayList的元素是怎么编排的，各个数组的元素如何随机访问（通过索引）、元素之间如何跳转（索引增减）。阅读源码可以发现，这个数组用transient关键字修饰，表示其不会被序列化。当然，ArrayList的元素最终还是会被序列化的，要不然，这个最常用的List之一，不能持久化、不能网络传输，简直不可想象。在序列化/反序列化时，会调用ArrayList的writeObject()/readObject()方法，将该ArrayList中的元素（即0...size-1下标对应的元素）写入流/从流读出。这样做的好处是，只保存/传输有实际意义的元素，最大限度的节约了存储、传输和处理的开销。

2.1.1 序列化的探讨

　　提到序列化，有个问题是，ArrayList的writeObject()/readObject()是如何被调用的？它们并不属于ArrayList的任何一个接口，甚至是Serializabe！其实，序列化是ObjectOutputStream对象调用自身的writeObject()方法时，由它通过反射检查入参——也即待序列化的对象——是否有writeObject()方法，并进行调用，这和接口无关，确实很古怪（可以参考《Java编程思想·第四版（中文）》第581页）。

2.1.2 删除元素

　　ArrayList在删除元素时，不仅要将其他元素前移来占用被移除的元素并缩小size，对于原来位置的元素，如(size-1)位置的元素前移至(size-2)位，那么(size-1)位置是要设置为null的，这样才能让垃圾回收机制发挥作用。这种数据的用法在Java中比较常见，比如利用Vector实现的Stack，也是这样。而在C语言中，一种利用数组实现的栈是可以在pop()后只修改当前栈对应的数组下标而不作清理的。

2.1.3 调整大小

　　利用Arrays.copyOf()方法做数组的调整。

2.2 Vector和Stack(不建议继续使用)

　　虽然Vector经过了改造，但这么做只是为了兼容Java2之前的代码，不建议继续使用。

　　Java1.6的源码中，和ArrayList类似，Vector底层也是数组，但是这个数组并没有transient修饰，其序列化要低效不少。

　　Stack是继承Vector实现的，而不是包装一个Vector。这并不是一个很好的设计，如果要使用栈行为，应该使用LinkedList。Java1.6源码中，Stack每次扩大都需要new新的数组并作拷贝，效率并不好。

　　新代码中误用这两个容器的原因，可能是之前在C++中使用过STL的Vector和Stack。我刚接触Java时，总以为这两个类在Java中的地位类似C++。

2.3 抽象类AbstractSequentialList

　　满足“连续访问”数据存储而非“随机访问”需求的List，对于指定index元素的操作，都需要利用抽象方法listIterator()获得一个迭代器。其唯一实现是LinkedList，对其的讨论放在Queue这部分。

三、Set

　　Set接口模仿了数学概念上的set，各个元素不要求重复。除了这一点，几乎和Collection本身是一样的。

　　Set接口有一个直接子接口SortedSet，该接口要求Set中所有元素有序。和通过Iterable接口依次访问所有元素的“有序”不同，这个“有序”要求Set包括一个比较器，可以判断两个元素的大于、小于或等于关系。此外，该接口提供了访问第一个元素、访问最后一个元素、访问一定范围内元素的方法。SortedSet的子接口NavigableSet进一步扩展了这个系列的方法，提供了诸如返回大于/小于元素E的第一个元素的方法。

　　由于Set的操作与底层的实现关联性很强，AbstractSet中实现的方法有限，在Java1.6中只有equals()、hashCode()、removeAll()进行了实现。

3.1 HashSet和LinkedHashSet

　　HashSet之所以命名中包含了“Hash”，是因为其底层是用HashMap实现的。Map有个特点，各个Key是唯一的，这和Set的元素唯一很类似。对HashSet的元素E进行的操作，实际上是对其包装的HashMap中对应的<E,PRESENT>的操作，其中PRESENT是一个private static final的Object。因此，HashSet的原理，放到HashMap那一块来研究。

　　HashSet有一个很特别的构造方法：HashSet(int initialCapacity, float loadFactor, boolean dummy)。这个方法第三个参数的唯一作用是，与其他两个参数的构造方法相区分。使用这个构造方法，在底层使用的是HashMap的子类LinkedHashMap。而LinkedHashSet，正是使用了这个构造方法，在内部创建并封装了一个LinkedHashMap而非一般的HashMap。

　　假如先有HashSet，后有HashMap，用HashSet实现HashMap，是否是一个好的主意？这也放在HashMap处研究。

　　HashSet的包装的HashMap也使用transient关键字修饰，采用了和ArrayList一样的序列化策略。

3.2 TreeSet

　　TreeSet是SortedSet的一个实现，也是其子接口NavigableSet的实现。

　　与HashSet/LinkedHashSet类似，TreeSet底层封装了一个NavigableMap，同样使用transient修饰，以及序列化策略。

四、Queue

　　Queue和List有两个区别：前者有“队头”的概念，取元素、移除元素、均为对“队头”的操作（通常但不总是FIFO，即先进先出），而后者只有在插入时需要保证在尾部进行；前者对元素的一些同一种操作提供了两种方法，在特定情况下抛异常/返回特殊值——add()/offer()、remove()/poll()、element()/peek()。不难想到，在所谓的两种方法中，抛异常的方法完全可以通过包装不抛异常的方法来实现，这也是AbstractQueue所做的。

　　Deque接口继承了Queue，但是和AbstractQueue没有关系。Deque同时提供了在队头和队尾进行插入和删除的操作。

4.1 PriorityQueue

　　PriorityQueue用于存放含有优先级的元素，插入的对象必须可以比较。该类内部同样封装了一个数组。与其抽象父类AbstractQueue不同，PriorityQueue的offer()方法在插入null时会抛空指针异常——null是无法与其他元素比较通常意义下的优先级的；此外，add()方法是直接包装了offer()，没有附加的行为。

　　由于其内部的数据结构是数组的缘故，很多操作都需要先把元素通过indexOf()转化成对应的数组下标，再进行进一步的操作，如remove()、removeEq()、contains()等。其实这个数组保持优先级队列的方式，是采用堆(Heap)的方式，具体可以参考任意一本算法书籍，比如《算法导论》等，这里就不展开解释了。和堆的特性有关，在寻找指定元素时，必须从头至尾遍历，而不能使用二分查找。

4.2 LinkedList

　　很有趣的是，LinkedList既是List，也是Queue(Deque)，其原因是它是双向的，内部的元素(Entry)同时保留了上一个和下一个元素的引用。使用头部的引用header，取其previous，就可以获得尾部的引用。通过这一转换，可以很容易实现Deque所需要的行为。也正因此，可以支持栈的行为，天生就有push()和pop()方法。简而言之，是Java中的双向链表，其支持的操作和普通的双向链表一样。

　　和数组不同，根据下标查找特定元素时，只能遍历地获取了，因而在随机访问时效率不如ArrayList。尽管如此，作者还是尽可能地利用了LinkedList的特性做了点优化，尽量减少了访问次数：

    private Entry<E> entry(int index) {

        if (index < 0 || index >= size)

            throw new IndexOutOfBoundsException("Index: "+index+

                                                ", Size: "+size);

        Entry<E> e = header;

        if (index < (size >> 1)) {

            for (int i = 0; i <= index; i++)

                e = e.next;

        } else {

            for (int i = size; i > index; i--)

                e = e.previous;

        }

        return e;

    }

　　LinkedList对首部和尾部的插入都支持，但继承自Collection接口的add()方法是在尾部进行插入。

五、一些琐碎的话题

5.1 线程安全

　　ArrayList、HashSet/LinkedHashSet、PriorityQueue、LinkedList是线程不安全的，可以使用synchronized关键字，或者类似下面的方法解决:

 List list = Collections.synchronizedList(new ArrayList(...));

5.2 clone()

　　ArrayList、LinkedList、HashMap/LinkedHashMap、TreeSet的clone()是浅拷贝，元素的引用和拷贝前相同；PriorityQueue的clone()继承自Object。

5.3 foreach

　　在for(Element e : collection)中：

　　collection == null，直接抛异常；

　　容器内容为空，即刚刚被new出来，里面什么也没有，直接跳过循环；

　　容器中放了null（如果允许的话），则将这个null取出并赋值给e，执行循环中的语句。

5.4 null对象

　　List可以放无限多个，set只能放一个。EnumSet、PriorityQueue是不能放null的。这个null也在计数中。所以放进去null用foreach取出来时需要判空。

码农公寓