说到Java的集合框架，最先会想到Collection和Collections，之后再是Collection的具体实现如有继承关系的List<E>，Set<E>和非继承关系的Map<K, V>。在Chuck加入春招大军以来的两个多月中，几乎所有面试都会问到对集合框架的理解，绝对算得上Java笔试面试中的高频考点。希望通过本文对自己的知识进行总结方便日后温习，也希望能帮助到正在征战各大企业面试的各位朋友。

（一）基础概念

集合统称Collection，是Java API里一个重要的接口，在Java各种开发中发挥巨大作用。其下的具体实现由List<E>，Set<E>和Map<K, V>三种。其中List<E>和Set<E>继承自Collection，'E'指泛型，在创建集合时指定集合中存储的元素类型（不指定默认Object，不提倡）。Map<K, V>是键值对映射容器，'K'、'V'也指泛型，与List和Set相似。

List、Set和Map的区别：

前两者与Map的区别显而易见，前两者属于单个元素级别的存储，而Map是键值对的存储方式。那么List和Set的区别呢？在不分析源码的情况下，可以先理解为List采用线性结构存储，元素可以为null。Set采用离散存储方式，不允许存储值为null的元素且存储的元素不能重复。在接下来的文章中对List、Set和Map源码分析便可以看出他们的显著区别和联系。

Collection和Collections的区别：

这种问题属于集合框架送分题，一般问这种题的面试官要么是带你预热（好人啊！），要么就是不懂Java（比如腾讯的面试官）。Collection是集合类List和Set的父接口，规定了集合的通用方法，不同子类的具体实现略有不同。Collections是集合工具类，提供了一系列static方法辅助操作，常用的有排序sort()、转化为线程安全的synchronizedXXX()等。

（二）集合类源码分析之ArrayList

List类中，Chuck主要讲解ArrayList和LinkedList两个具有代表性也最常用的List集合。首先，ArrayList采用的是Object数组的形式存放元素，由于是数组形式存放，其随机访问的性能优异，但可能会存在空间浪费，并且在不断插入过程中会调整数组大小。
以下是给出的ArrayList类的定义：

public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承自AbstractList<E>，同时实现了List<E>接口，从Cloneable和Serializable得知ArrayList也支持克隆和序列化等操作。（这些面试时候问到可以说，细节是面试的加分项），RandomAccess是一个标记接口，未实现任何内容，感兴趣的读者可以自行查看源码。

ArrayList中的两大核心属性：

/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData;// non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*@serial
*/
private int size;

Object类型的数组elementData和size，前者是ArrayList对象存储的容器，从注解中可以看出，数组创建采用懒加载的方式，只有在第一次插入元素时才创建。后者是当前存储的元素个数，除了通过size()方法获取集合大小，size属性在很多时候会有用到。

构造函数

//直接指定大小的方式创建
publicArrayList(intinitialCapacity) {
  if(initialCapacity > 0) {
    this.elementData = newObject[initialCapacity];
  }else if(initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  }else{
    throw newIllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
  }
}
//未指定大小创建
publicArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//传入集合的方式创建
publicArrayList(Collection c) {
  elementData = c.toArray();
  if((size = elementData.length)  != 0) {
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
  if(elementData.getClass()  !=  Object[].class)
    elementData = Arrays.copyOf(elementData, size, Object[].class);
  }else{
    // replace with empty array.
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

无论哪种方式，源代码都很通俗易懂，指定大小的情况下，要做的就是验证传入参数是否合法，实际上就是对代码鲁棒性的保证，合法则创建数组，否则抛出异常即可。
而未传入初始大小的情况下，老版本中调用this(10)的方式创建初始大小为10的Object数组。Chuck的jdk 1.8中将elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}

可见1.8中的改变是创建一个空数组。
传入集合初始化的方式其实就是将原有集合转化为数组，通过Arrays.copyOf()函数赋值给新数组直接初始化。
其实一般情况下讲到这里就已经挺长时间了，如此细致的理解已经不错了，但ArrayList中常用的add()方法是整个类中比较复杂且开发中最常用到的方法，在此给出深入的讲解：

public boolean add(E e) {
  ensureCapacityInternal(size + 1);// Increments modCount!!
  elementData[size++] = e;
  return true;
}

ensureCapacityInternal(size + 1)方法顾名思义，因为要插入新元素了集合的大小肯定会+1，所以该函数的作用就是验证插入新元素是否会超出数组大小限制，若会超出则先进性扩容再进行插入。

private void ensureCapacityInternal (int minCapacity) {
  if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  ensureExplicitCapacity(minCapacity);
}

这里注意，DEFAULTCAPACITY_EMPTY_ELEMENTDATA是前文在未传入初始大小情况下进行构造是的空Object数组，这里将对elementData进行初始化，DEFAULT_CAPACITY是一个值为10的int型常量，如果之前是未传入初始大小构造集合，就在这步构造一个大小为10的Object数组。
ensureExplicitCapacity()函数又是什么作用？

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;
  // overflow-conscious code
  if(minCapacity - elementData.length > 0)
    grow(minCapacity);
}

modCount是ArrayList的一个int型属性，很多方法里都会有它的自增操作，其实就是记录ArrayList备操作次数的一个变量。函数中判断如果当前规模小于需求的规模，调用grow函数。

private void grow(int minCapacity) {
// overflow-conscious code
  intoldCapacity = elementData.length;
  intnewCapacity = oldCapacity + (oldCapacity >> 1);
  if(newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if(newCapacity -MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容过程也不难，先试图将数组变为原先的1.5倍，若还达不到预期的大小就直接指定为预期大小即可，之后就是数组的新建和复制操作，不再赘述。再把目光返回add()函数，接下来只需要插入新元素并返回即可。
add()函数算是整个ArrayList中比较复杂的业务流程了，其它函数addAll()，remove()等就请各位读者感兴趣的话自行学习。以上知识点对付ArrayList类的面试题绰绰有余。接下来的文章中还将谈到另一个List的代表类LinkedList。