ArrayList源码解析——JDK1.8

转载：http://www.cnblogs.com/skywang12345/p/3308556.html

1、ArrayList介绍

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。

ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

2、关键点

ArrayList包含了两个重要的对象：elementData 和 size。

elementData 是”Object[]类型的数组”，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。
size 则是动态数组的实际大小。

    transient Object[] elementData;

private int size;

3、构造函数

    //带指定初始容量的构造函数
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);
        }
    }

//创建一个空的ArrayList, 默认容量为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//创建一个包含Collection的ArrayList
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;
        }
    }

4、扩容函数

    //增加容量为minCapacity
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_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);
    }

扩容的核心，grow()函数：

    //每次重新分配内存时，新的容量为旧的1.5倍 
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
////设置新的容量 = 旧容量*1.5 
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果小于可允许的最小容量
if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
//如果大于可允许的最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
//复制元素
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

5、clone()函数

 public Object clone() {
try {
 ArrayList<?> v = (ArrayList<?>) super.clone();
 v.elementData = Arrays.copyOf(elementData, size);
 v.modCount = 0;
return v;
 } catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
 }
 }

6、add()、get()、set()、remove()、clear()

6.1 add()操作

    //添加元素
public boolean add(E e) {
//首先确定容量，如果不够，需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
//在数组中下一个空位置上添加元素
        elementData[size++] = e;
return true;
    }

    //指定位置index上添加元素，原来位置元素并没有消失，只是后移了一位,
//即将当前位于该位置的元素以及所有后续元素右移一个位置。 
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!

//移动元素。
//将 elementData 中从index位置开始、长度为size-index的元素，
//拷贝到从下标为index+1位置开始的新的elementData数组中。
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

6.2 get()操作

    public E get(int index) {
//检测有没有数组越界
        rangeCheck(index);
//返回index位置上的元素
return elementData(index);
    }


    E elementData(int index) {
return (E) elementData[index];
    }

6.3 set()操作

设置index上的元素为element，会覆盖原来的值。

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
return oldValue;
    }

6.4 remove()操作

    //去除指定位置index上的元素,该位置后所有元素前移一位
public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = 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;
    }

    //移除在数组中首次出现的指定元素o,如果不存在返回false。
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;
    }

6.5 clear()操作

清空数组中的所有元素的引用。让GC回收这些引用指向的对象。

    public void clear() {
        modCount++;

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

        size = 0;
    }

秒客网