本文主要介绍JDK的核心模块之一——集合框架，其内部原理和结构。
要说集合框架最顶层的结构，应该算是Collection接口和Map接口，虽然Collection接口还有更顶层的Iterable接口，但是我觉得该接口只是迭代子模式的实现，不能体现顶层的含义。 ### 关系结构 Collection结构看下图： {% asset_img collection.png %} 从结构图我们可以知道： - Collection有一个父接口Iterable，该接口从更高层意义抽象一种可以被迭代子模式迭代的对象，由于Collection所代表的含义是集合，集合是肯定可以被迭代的，所以它有一个父接口Iterable。同时，由于该接口的关系，我们才可以使用foreach这种类型的迭代方式去迭代Collection。 - Collection有四个子接口，分别是BeanContext、List、Queue、Set。 - BeanContext：该接口和JAVA的Beans包有关系，JavaBean曾是一种可视化Java类的尝试，但是现在感觉，整个JavaBean都没什么应用了，但是JavaBean这个概念却被广泛地应用起来。比如Spring框架就借鉴了JavaBean的一些思想，发明了自己的Bean。至于为什么会放在Collection下面，就不深究了，毕竟Java的Beans包暂时应用不是很广泛。 - List：这就是大名鼎鼎的列表接口了。 - Queue：队列接口，我们不经常使用的一个接口，从名字就知道，它主要定义队列这种数据结构。 - Set：主要定义不含有重复元素的集合，即不含有两个内部元素a,b满足a.equals(b)且至多只有一个null元素的集合。 - Collection还有六个子类，分别是AbstractCollection、CheckedCollection、CollectionView、SynchronizedCollection、UnmodifiableCollection、ValuesView。其中带有Abstract、View字样的是抽象类，其余是普通类。这六个实现类相当于将集合从下面一个层次分成了6种不同功能或者类型的集合。我们常用到的集合子类们大多都是继承自AbstractCollection。而带有View的集合则主要是用来给Map提供视图的。然后我们还有CheckedCollection，用来包装普通的Collection提供类型安全机制，当错误的类型插入该集合时，立即抛出类型转换错误。SynchronizedCollection是Collections类提供的实现类，它包装普通的集合以支持并发操作，其内部使用了对象锁所以性能较差。UnmodifiableCollection也是Collections类提供的，包装普通的集合以产生不可变的集合，在介绍Guava的时候已经介绍过不可变集合的好处。 - 还可以看到，Collection依赖了五个类，被86个类关联，被231个类依赖
除了类之间关系的结构图以外，我们还可以看一下该接口内部的结构图： {% asset_img collection_inner.png %} 其中，empty其实不是properties，我这个uml生成软件错误识别成了properties，因为collection有一个isEmpty()方法。 我们可以看到： - Collection接口定义了一个集合必须有的基础功能，如下： - 添加（add,addAll） - 是否为空（isEmpty） - 是否包含元素或者另一个集合（contains,containsAll） - 清除所有元素（clear） - 获得迭代器（iterator） - 移除元素或者移除同时在另一个集合中的元素（remove,removeAll） - 获得当前集合大小（size） - 转换为Array即数组（toArray），其中，有参数的版本会将元素放入参数传入的数组中，如果放不下，就新创建一个运行时类型相同的array返回 - 还有一些JDK1.8所特供的方法(parallelStream、removeIf、spliterator、stream)
下面我们进入抽象层，首先是最常见的java.util.AbstractCollection，它是一个抽象类。 ### 关系结构 该抽象类的关系结构比较简单。 向上：它实现了Collection接口 向下：它有15个子类 向左：它没有被其他类用到 向右：它仅使用了Iterator和String
它的内部结构如下： {% asset_img abstractCollection_inner.png %} 作为Collection接口的骨骼实现，它的内部结构应该与Collection非常相似。 所谓骨骼实现，就是某个抽象类给接口中的一些方法提供通用默认实现，后续实现类去实现接口的时候，继承该抽象类，这样只需覆盖自己关心的几个方法就可实现接口。 下面就每个方法进行解析： - isEmpty()：直接调用size()来和0做比较，返回结果 - add(E)：直接抛出UnsupportedOperationException。其返回值是boolean，true代表元素添加成功 - addAll(Collection)：基本上就是遍历传进来的集合，然后针对每个元素调用add方法，一旦有add返回了true，就返回ture。 - clear()：通过迭代器来逐个删除元素，很差的性能，所以绝大多数实现都会覆盖这个默认方法。如果迭代器没有实现remove方法，会抛出UnsupportedOperationException - contains(Object)：使用迭代器，然后逐个比较元素 - containsAll(Collection)：遍历入参集合的元素，并逐个调用contains，一旦有false的，直接返回false - iterator()：抽象方法，没实现 - remove(Object)：使用迭代器来遍历元素，找到与入参equals的元素，调用迭代器的remove方法来删除。如果迭代器没有实现remove方法，会抛出UnsupportedOperationException。 - removeAll(Collection)：使用迭代器遍历元素，然后每个元素都调用入参集合的contains方法来判断是不是在入参集合中，在的话，就调用迭代器的remove方法来删除，同样可能抛出上面那个异常。一旦有删除操作，就返回true，否则false。 - retainAll(Collection)：和上面一样，遍历元素，调用contains方法来判断元素是否在入参集合中，但是此处是不在的话，就删除。在的话，会留下。一旦发生删除操作，返回true，否则false。 - size()：抽象方法，没实现 - toArray()：该方法挺复杂的，贴在下面：
public abstract class AbstractCollection<E> implements Collection<E>{//... public Object[] toArray() { // Estimate size of array; be prepared to see more or fewer elements Object[] r = new Object[size()]; Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; }//...}
首先新数组的大小是通过size获得的，然后遍历新数组，同时遍历集合，将每个元素放入新数组中。
如果集合中的元素比新数组大小小（这发生在size方法刚刚返回大小之后，有人从集合中删除了元素），就提前返回新数组。
在遍历结束后，如果集合中的元素和新数组大小相等，就返回新数组。
如果遍历结束后，集合中仍然有元素，即迭代器hasNext返回true，说明在遍历期间，有人向集合添加了元素。此时会调用finishToArray(r, it)来处理。
finishToArray代码如下：
public abstract class AbstractCollection<E> implements Collection<E>{//... @SuppressWarnings("unchecked") private static <T> T[] finishToArray(T[] r, Iterator<?> it) { int i = r.length; while (it.hasNext()) { int cap = r.length; if (i == cap) { int newCap = cap + (cap >> 1) + 1; // overflow-conscious code if (newCap - MAX_ARRAY_SIZE > 0) newCap = hugeCapacity(cap + 1); r = Arrays.copyOf(r, newCap); } r[i++] = (T)it.next(); } // trim if overallocated return (i == r.length) ? r : Arrays.copyOf(r, i); }//...}
继续使用迭代器遍历集合，然后新数组在遍历的过程中动态扩容，扩容公式是：现在容量+现在容量/2+1。
每扩容一次，就要发生一次数组的全拷贝，注意，Arrays.copyOf方法底层是一个native方法。
我们可以看到，作者对溢出数组极大值的情况做了特殊处理。由于数组的下标是由int类型标识的，所以此处设定了一个数组极大值`MAX_ARRAY_SIZE`，它等于int极大值-8。
在扩容后大小超过数组极大值时，就重新处理扩容大小。具体做法如下：
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError ("Required array size too large"); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
即如果刚好容量是int极大值，那么+1之后，它就会变成负数，所以一上来就判断它是不是变成负数了，变成负数说明容量超出了，扩容失败，抛出OutOfMemoryError。
如果容量+1之后，比数组极大值大，那就使用int极大值，如果不是，就使用数组极大值。
这番处理后，扩容的大小至少不会超出int极大值导致接下来拷贝数组失败。
最后，我们还能看到在finishToArray方法返回的时候，还检验扩容是否多了，如果多扩容了，就把多余空间通过数组全量copy给剪掉。
在讲完AbstractCollection之后，按理说还有几个抽象层的类要讲，但是他们大多数是为了实现某个功能，并不是集合框架通用的抽象层，等讲到相应的实现类时，再讲它们。 现在我们进入集合框架最常用最重要的一个接口，List接口。 ### 关系结构 {% asset_img List.png %} 如上图。 其中我们常用的有子抽象类AbstractList以及最著名的子类ArrayList 还可以看到，子类中有几个子类是以成员类（memberClass）的方式存在的。 ### 内部结构 {% asset_img List_inner.png %} 由于这是一个继承Collection接口的List接口，我们只需要关注它和Collection接口不一样的地方，也即额外提供的一些功能，如下图： {% asset_img diff_collection_list.png %} 右边箭头指出的方法都是List新增加的。 下面一一分析： - 可以看到，List和顶层集合最主要的区别在于，List定义的集合是有序集合，它内部的元素一般都和一个Index值挂钩，所以它额外提供了add,addAll,get,set,indexOf,lastIndexOf,remove这7个和index密切相关的方法。允许用户通过index来进行一系列操作 - listIterator会返回一个允许用户双向迭代集合的迭代器，并且可以在迭代过程中修改元素，删除元素，获得下一个或者上一个元素的index。 - sort方法在1.8以前是没有的，只能使用Collections类提供的方法来排序，1.8之后，可以直接使用该方法来排序。 - subList方法会得到一个从某个index开始到某个index结束的子List视图，左边闭区间右边是开区间，由于是视图，一些修改会反映到原List上。
如下图： {% asset_img abstractList.png %} 可以看到： - 该抽象类继承了AbstractCollection - 改抽象类有两个成员类，分别实现了迭代器和List专有的双向迭代器