本文共 8720 字，大约阅读时间需要 29 分钟。

前言

因为在看其他文章的时候，其中提到ArrayList其实就是对数组的一些操作细节封装起来，对集合的操作，实际上是对里面的数组进行操作，相比较于数组，ArrayList可以动态扩容的。所以就引起了自己去查看ArrayList的源码实现。

简单的分析下主要几个方法的实现过程

1、几个成员变量

//默认的数组的容量       private static final int DEFAULT_CAPACITY = 10;     // initialCapacity为0的实例（new ArrayList(0)）对应的空的数组实例         private static final Object[] EMPTY_ELEMENTDATA = {};    //通过不设置数组容量（new ArrayList()）的实例对应的空数组实例，      private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    //用来存放元素的数组    transient Object[] elementData;    //集合中元素的数量    private int size;

我们可以看到其实最终 加入到ArrayList集合中的元素都存放到了Object[] elementData中，并且ArrayList的默认的容量为10。

注意elementData采用transient修改表示该字段不被序列化。

2、构造函数

我们可以通过三种方式来创建一个ArrayList实例。

1）public ArrayList()

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

就是初始化一个空的elementData数组

2）public ArrayList(int 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);        }    }

就是初始化一个initialCapacity大小的elementData数组或着一个空的elementData数组

3）public ArrayList(Collection<? extends E> c)

public ArrayList(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;        }    }

根据传入的集合来初始化elementData数组。

3、添加元素

1）public boolean add(E e)

直接在集合元素依次累加元素

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

从源码中可以看到，其实就是给对应的size 的位置的elementData数组元素进行赋值。当然在赋值之前，会通过ensureCapacityInternal()来确定elementData数组大小是否满足要求，从而创建出一个可用的elementData数组来存放元素。重点看下ensureCapacityInternal()这里面的一些源码

（1）ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {//如果通过new ArrayList这种方式创建的ArrayList，则取得minCapacity和DEFAULT_CAPACITY的最小值    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    ensureExplicitCapacity(minCapacity);}

• 取得minCapacity

 从源码中可以看到如果通过new ArrayList这种方式创建的ArrayList，则取得minCapacity和DEFAULT_CAPACITY的最大值。还没有添加元素之前size为0，minCapacity为1，而DEFAULT_CAPACITY为10，那么最后minCapacity的值为10，随着size的累加，会逐渐minCapacity变成size的大小。

• 调用ensureExplicitCapacity(minCapacity)。

private void ensureExplicitCapacity(int minCapacity) {//集合被修改的次数        modCount++;        // overflow-conscious code        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }

判断集合中的元素和elementData的数组长度。如果集合中的元素超出elementData容量时，则通过grow()进行扩容；否则直接返回。

分析下上面三种构造函数创建的ArrayList的第一次调用add()情况：

（a）new  ArrayList()

此时minCapacity为10，elementData.length为0，那么需要调用grow()进行扩容

（b） new  ArrayList(int initialCapacity)

此时minCapacity为1，initialCapacity＝0时，elementData.length为0，那么需要调用grow()进行扩容；如果initialCapacity>1，则直接返回即可。

（c）new  ArrayList(Collection<? extends E> c)

此时minCapacity为c.length＋1，elementData.length也为传入c.length，此时需要调用grow()进行扩容。

• grow()进行扩容

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;    }

通过oldCapacity + (oldCapacity >> 1);来获取 newCapacity，即1.5倍的oldCapacity。通过分析各种情况，对elementData的数组进行复制扩容。直到超过最大值。

得到能够存放元素的数组之后，直接在数组后面进行添加元素即可。

（2） elementData[size++] = e;

数组直接赋值即可。

2）public void add(int index, E element)

在特定位置进行添加元素

public void add(int index, E element) {        if (index > size || index < 0)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));        ensureCapacityInternal(size + 1);  // Increments modCount!!        System.arraycopy(elementData, index, elementData, index + 1,                         size - index);        elementData[index] = element;        size++;    }

同样首先会先确定 elementData数组中足以放下该元素

然后调用System的arrayCopy()将elementData起始index位置的元素复制到elementData元素的index+1的位置开始存放，一共复制size-index个元素。

最后进行赋值即可。

3）public E set(int index, E element)

替换特定位置的元素。

public E set(int index, E element) {        if (index >= size)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));        E oldValue = (E) elementData[index];        elementData[index] = element;        return oldValue;    }

从源码中可以看到，其实就是直接将 elementData数组中的元素对应位置进行修改，同时将该位置的原值返回。

 4）public boolean addAll(Collection<? extends E> c)

添加集合。

public boolean addAll(Collection
    c) {        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacityInternal(size + numNew);  // Increments modCount        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;        return numNew != 0;    }

原理和添加单个元素是一样的，唯一的区别就是在size累加的大小由1变成了添加集合的length。通过System.arraycopy()将a从0位置的元素复制到elementData数组的从size开始的后面，一共复制a.length大小的元素。

5）public boolean addAll(int index, Collection<? extends E> c)

指定位置添加集合

public boolean addAll(int index, Collection
    c) {        if (index > size || index < 0)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacityInternal(size + numNew);  // Increments modCount//判断要插入的位置，将后面的位置后移        int numMoved = size - index;        if (numMoved > 0)            System.arraycopy(elementData, index, elementData, index + numNew,                             numMoved);        System.arraycopy(a, 0, elementData, index, numNew);        size += numNew;        return numNew != 0;    }

同样确保elementData的容量是足够的，然后会判断index的位置 ，如果在中间，首先需要System.arraycopy()将elementData从index位置之后的元素开始复制到elementData的index+c.length的位置之后，共复制size－index个元素（即index后面的所有元素）。

4、取元素

    1）public E get(int index) 

取出给定位置的元素。

public E get(int index) {        if (index >= size)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));        return (E) elementData[index];    }

很简单直接读取 elementData对应位置的元素

2）public int indexOf(Object o)

查找object对应的索引值

public int indexOf(Object o) {        if (o == null) {            for (int i = 0; i < size; i++)                if (elementData[i]==null)                    return i;        } else {            for (int i = 0; i < size; i++)                if (o.equals(elementData[i]))                    return i;        }        return -1;    }

直接通过循环进行匹配object，找到对应在 elementData数组中的位置。

5、移除元素

1）public E remove(int index)

移除指定位置的元素

public E remove(int index) {        if (index >= size)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));        modCount++;        E oldValue = (E) elementData[index];        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        return oldValue;    }

从 elementData读取元素，并将elementData的对应index+1之后的元素复制到index位置，同时将elementData的存储空间减1，返回对应位置的元素。

2）public boolean remove(Object o)

将指定的object对象给移除

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;    }

与上面1）不同的是，首先要找到该object对应的index，然后从elementData中删除的理论通1）。从上面也可以看到ArrayList中支持null。 

3）public void clear()

清空所有的元素

public void clear() {        modCount++;        // clear to let GC do its work        for (int i = 0; i < size; i++)            elementData[i] = null;        size = 0;    }

就是直接将 elementData中的所有元素置为null即可。

总结

从源码读下来，发现ArrayList的一些操作就是在操作里面的一个数组，其实就是对数组的操作，只不过会根据加入的元素个数动态对数组进行扩容。

 

 

转载地址：http://kpejz.baihongyu.com/