从源码阅读认识ArrayList

优秀源码的阅读对于开发者来说是一个不错的提升方法。今天我们就要通过JDK源码的阅读来重新认识大家所熟悉的ArrayList

ArrayList

//源码
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;

ArrayList定义了这四个参数：
DEFAULT_CAPACITY是默认的容量
EMPTY_ELEMENTDATA定义了一个空的数组
elementData是列表中存放对象的数组
size该列表的所存放的对象数量

扩展阅读——transient
细心的读者会发现elementData被关键字transient修饰，这意味着elementData不参与序列化。
这么设计的原因是由于ArrayList的自动扩容机制，保证了ArrayList的容量总是大于等于其所
存放的对象，如果对elementData进行序列化就会造成浪费。因此ArrayList的序列化是对于
elementData所存放的对象进行，而不是elementData本身
部分源码：
for (int i = 0; i < size; i++){ //遍历上限为size，而非elementData.length
    s.writeObject(elementData[i]);
}
可以看到，JDK底层的源码对于内存空间的使用是非常谨慎的。优秀的源码如是，优秀的应用
也应如是。

ArrayList的底层是基于数组实现的。既然ArrayList是用数组对象来作为存储容器，那么其内存模型也和数组是一致的，是一个连续的大小相同的内存。

List<String> list = new ArrayList<String>(5);
list.add("Hello");
list.add("world");
lsit.add("!");

ArrayList内存模型

如图所示，在这段源码中数组对象的长度为5，但是调用list.size()则返回的是3。

构造方法

//源码
    //构造方法一
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }

    //构造方法二
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    //构造方法三
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

ArrayList有三种构造方法（见源码），其中构造方法一是最常用的，这里elementData引用了空的对象数组，当需要容量时，会执行扩容操作（详细见add方法）；构造方法二让ArrayList在初始化的时候遍分配好了所需要的内存容量，笔者建议使用ArrayList的时候，如果能够知道即将添加入数组列表中的数据量，则选择这个构造方法预先申请好内存优于其自动扩容，毕竟扩容操作是有开销的；构造方法三可以将已有的Collection子类直接转成ArrayList类型数据。

add & 扩容

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

add()比较简单，首先确认下容量是否足够(不够就进行扩容)，然后将待添加的对象放置于数组当中。
ensureCapacityInternal()方法就是ArrayList比一般的数组灵活的核心所在。大家都清楚，ArrayList的动态扩容避免了数组越界的问题。接下来就看看ArrayList是如何实现动态扩容机制。

//源码
   private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            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);
    }

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

grow()方法就是对ArrayList进行扩容的操作，判断是否扩容的条件就是minCapacity - elementData.length>0，当ArrayList所需的最小容量大于elementData数组的容量。
oldCapacity >> 1移位操作的细节，相比于直接除以2，得到的结果是一样的，但是由于计算机底层实现是通过移位来实现的，所以直接调用移位方法比直接调用'/'的数学运算运算速度来得快。优秀的源码真是让人受益匪浅，细心点，可以发现不少可以帮助你优化程序性能的地方。

ArrayList动态扩容

通过这段源码，可以知道，扩容机制，就是将数组中的内容复制到另一个容量更大的数组中。这也是为什么笔者建议尽可能地指定ArrayList的初始容量，特别是在容量需求较大是，不指定初始容量会让ArrayList不断扩容，不断地读写内存，导致效率更低。

扩展阅读——机制的利用与滥用
可能有很多读者觉得ArrayList提供了动态扩容的机制，就无需注意这些使用上
的细节，这个想法是错误的，Jvm给我们提供了垃圾回收机制，但很多源码还是
会及时地对数据进行回收处理，来获得更为强大的性能。详情可以去了解Java GC
相关知识。
小实验：
ArrayList<String> list = new ArrayList<String>();  //耗时0ms
for(int i = 0; i<1000000; i++){  //耗时15ms
            list.add("hello");
}
ArrayList<String> list2 = new ArrayList<String>(1000000);  //耗时1ms
for(int i = 0; i<1000000; i++){  //耗时4ms
            list2.add("hello");
}

get()

//源码 get的实现
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

经常看源码，可以让你的代码变得优雅，很多人觉得，这里rangeCheck()方法只有一个判断，为何还要单独一个方法，如果去细看其他方法的实现，会发现这个方法被多次的调用。本人在项目上见得最多的一个反例，就是这样的代码：

反例：
Object  object = objectDao.get(objectId);  //Object代指某个实例
if(object == null){
  throw new xxxException("object不存在")
}

推荐做法：
public Object getObjectEntity(String objectId){
    Object  object = objectDao.get(objectId);  //Object代指某个实例
    if(object == null){
        throw new xxxException("object不存在")
    }
    return object;
}

但凡需要获取这个Object对象，都是这样的一段代码。而且经常会因为忘记条件语句而出现NPE(空指针异常)。用本人的话来说，就是“不够面向对象”。虽然很简单，不就是封装吗，但是很多开发者都做不到，导致大量不易看懂的业务逻辑，大量的重复代码。

remove()

//源码 remove的实现
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

简单提一下，对于不需存活的对象，比如被Listremove的对象，可以将对对象的引用指向null，这样GC就会回收这个对象，避免造成内存的浪费，对于提升程序的性能是很有帮助的。

对于ArrayList的其他方法就不多说了，有兴趣的建议去看看源码实现。
欢迎查看下一篇相关的文章《从源码阅读认识LinkedList》