Arraylist

继承自AbstractList，实现了List，RandomAccess，Cloneable，和Serializable接口，具有List的特性，提供可随机访问，提供自身克隆以及序列化的一个容器类。
特点：线程不安全；数组实现

主要成员变量

• 来自自身的成员变量：

        // 序列化ID
        private static final long serialVersionUID = 8683452581122892189L;
         // 默认初始化容量
        private static final int DEFAULT_CAPACITY = 10;
        // 空的数组
        private static final Object[] EMPTY_ELEMENTDATA = {};
        // 默认容量的空数组
        private static final Object[]  DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        // 真正存放对象的数组
        transient Object[] elementData; 
        // 容器的大小
        private int size;

• 来自父类和接口的成员变量：

        // 操作计数
        protected transient int modCount = 0;

这些变量都怎么被用到？接下来看方法

方法

方法的话，分几个模块来看吧

• 初始化
  初始化的构造函数有三个
  第一个，无参构造函数ArrayList()，函数直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData

        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

第二个，带int形参的构造函数ArrayList(int initialCapacity),函数首先判断initialCapacity是否为0，如果是0，则将EMPTY_ELEMENTDATA赋值给elementData，如果大于0，就将elementData初始化为一个容量为initialCapacity的对象数组

      public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
      }

第三个，带Collection形参的构造函数ArrayList(Collection<? extends E> c)，首先调用Collection的toArray()方法，返回的结果赋值给elementData,这里值得注意的是，有可能返回的结果不是Object[]（有可能是null），所以才会有if (elementData.getClass() != Object[].class)的判断,如果判断成立，调用Arrays.copyOf()来将collection中的数据复制到elementData中。其次，如果collection中没有数据，就将EMPTY_ELEMENTDATA赋值给elementData

public ArrayList(Collection<? extends E> 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;
}
}

这就是全部的构造函数，有疑问，就是三个构造函数都存在赋值一个空数组给elementData，但是为什么无参的赋的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，剩余两个是EMPTY_ELEMENTDATA，带着疑问进入下面的方法

• 添加
  添加元素这个功能涉及到好几个方法，一个一个来看，首先是最基本的Add方法，把一个元素添加到elementData中，要做这个之前，要扩容

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

扩容方法，在这里就看到了DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果EMPTY_ELEMENTDATA是由DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值而成，那么就将扩容的数量minCapacity和DEFAULT_CAPACITY进行比较，然后取其中的最大值，最大值再传参给ensureExplicitCapacity函数

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

ensureExplicitCapacity(minCapacity)方法，在这个方法中先将操作数记录值modCount自增，然后根据minCapacity和elementData.length的大小来决定是否需要增加容量

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

grow(minCapacity)方法，这个就是重头戏

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = 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倍的实现

int newCapacity = oldCapacity + (oldCapacity >> 1);

if (newCapacity - minCapacity < 0)的判断是因为oldCapacity有可能为0，这样得到的newCapacity也会为0
if (newCapacity - MAX_ARRAY_SIZE > 0)的判断确保数组的容量不大于Integer的最大值

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :  MAX_ARRAY_SIZE;
    }

最后再返回一个包含原来数据的新容量的数组

elementData = Arrays.copyOf(elementData, newCapacity);

到这里上文的DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的选择问题也就明了清晰了

• 调用无参构造函数时创建容器时，当第一次往该容器添加对象时，执行到ensureCapacityInternal,因为这个时候minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)形参列表中的minCapacity必定是1，所以初始化出来的elementData必定是长度为10的数组，这就是为什么网传默认的ArrayList的容量为10的由来

• 当调用剩下两个构造函数初始化时，即便初始化出来是容量为0的容器，在第一次往容器里添加对象时，只会让容量扩充到1

// oldCapacity为0，newCapacity为0，minCapacity为1，
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

个人猜测这个设计的由来是为了容器容量的缓慢增长，避免浪费太多的空间，所以以后编码遇到容器类需要存储比较少对象的时候，用带参数的构造函数有利于节省内存

好了，上面就是ArrayList的重头戏扩容，还有剩余的几个add方法也一并过了

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }

add(int index, E element)方法，根据制定下标开始添加元素，首先会调用rangeCheckForAdd方法判断下标是否有错，然后再判断是否需要扩容，然后调用

System.arraycopy(elementData, index, elementData, index + 1,
size - index);

将index之后的数据往后移一位，最后将element添加到elementData的index，同时size增加

add系列还有

public boolean addAll(Collection<? extends E> c) // 添加集合
public boolean addAll(int index, Collection<? extends E> c) // 往直接下标开始添加集合

具体实现就不再啰嗦了，大同小异，有兴趣可以自己翻阅，我们进入下一个模块

• 获取
  ArrayList提供好几种获取容器内对象的方法

第一种，get

public E get(int index) {
rangeCheck(index);
return elementData(index);
}

简单易懂，就不叙述了

第二种，通过Iterator()返回私有内部类Itr对象(Itr实现了Iterator接口)，然后在迭代器对象基础上获取容器内的对象

各种迭代器的方法我就不在叙述了

第三种，通过listIterator()或者listIterator(int index)返回私有内部类ListItr对象(ListItr继承Itr并实现了ListIterator接口)，然后在迭代器对象基础上获取容器内的对象

ListIterator继承于Iterator，在普通的迭代的基础上增加了往前迭代的操作，因此使用ListIterator迭代ArrayList对象也提供了往前操作对象的方法
这里有一个点注意的是上文中提到的modcount,就拿ListItr中的previous()方法举例吧
我们先过一遍这个方法，游标减1后赋值给i，如果i的值小于0，报错；然后通过闭包获取到外部类的elementData，如果i大于elementData的长度，报错；然后将i赋值给游标，然后直接获取到elementData中的值

@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}

checkForComodification()，就是这个方法用到了modCount我们点进去看下

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

然后再看下代码中expectedModCount是什么东西

private class Itr implements Iterator<E> {
int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
....
}

可以看到expectedModCount就是modCount的一个副本，是在Itr类对象被创建的时候初始化的，也就是一经创建就不会改变。而modCount是在每次操作容器内的数据的时候会自增的，那么什么时候modCount != expectedModCount呢？没错，就是已经通过list对象获取到一个迭代器对象之后，又对list对象进行了数据对象的操作，为此我做了一个测试

意料之中的ConcurrentModificationException

这也是ArrayList线程不安全的一个体现，共享变量是没加锁的，在多线程环境下很容易被修改然后数据就乱套了
其他方法和正常的ListIterator差不多，这里也不再啰嗦了

• 其他模块
  其他的大概就是set，remove,size,indexOf序列化的两个方法(readObjact(),writeObject())，在搞定了add()的扩容基础上，前四个也是很小case了，而后两个是私有方法，我们是无法直接使用，找了找资料说是调用ObjectOutInputStream序列化的时候会通过反射调用，这里还没了解过和测试过，也不自作高明了。

后言

看了源码才发现源码真的就像高中数理化那些基础一样，基础好了，弄很多东西都顺手拈来，也是看了源码才知道一个类有哪些地方需要注意，甚至是有哪些地方可以优化，而不是一个API工程师

水平有限，难免有错，还请评论区指责下