ArrayList源码分析

问题提出

• ArrayList底层采用什么数据结构？
• ArrayList是如何扩容的？
• 频繁扩容导致性能下降如何处理？
• 什么情况下你会使用ArrayList？
• 如何复制某个ArrayList到另一个ArrayList中去？
• ArrayList插入或删除元素一定慢么？
• ArrayList是线程安全的么？

下面就带着问题往下看吧~

重要属性

//默认的初始化容量
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;

//数组最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造器

/**
* 传入指定容量大小
*/
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);
    }
}

/**
* 无参的构造方法
*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

添加数据

add(E e);
add(int index, E element);
addAll(int index, Collection<? extends E> c);
addAll(Collection<? extends E> c);

添加单个数据

注意：这里使用无参构造函数，第一次添加数据作为例子

public boolean add(E e) {
    //扩容处理
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //添加数据到数组末尾
    elementData[size++] = e;
    return true;
}

先进行扩容处理

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
* 如果当前还未存入数据（空数组），返回默认长度10 (第一次添加数据，数组容量为10)
* 否则，返回当前数组长度+1
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    //集合修改次数加1
    modCount++;
    //判断当前数组是否有剩余空间，没有调用grow(minCapacity);
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //扩容新容量=旧容量+旧容量/2
        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;
    }

• 扩容处理逻辑如下：

  
  容量扩充 (1).jpg

添加数据到指定位置

逻辑：先将指定位置元素都往后移动一个位置，再将新元素放在指定位置。

public void add(int index, E element) {
    //越界检测
    rangeCheckForAdd(index);
    //扩容处理
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //对源数组做复制处理，后移（index+1 ~ size-index）
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

添加集合数据到指定位置

public boolean addAll(int index, Collection<? extends E> c) {
    //越界检测
    rangeCheckForAdd(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;
}

添加集合数据

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //直接copy数据到容器中
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

删除元素

remove(int index)；
remove(Object o)；
removeAll(Collection<?> c)；
clear();

删除指定位置的元素

public E remove(int index) {
    rangeCheck(index);
    //集合修改次数加1
    modCount++;
    //取出需要删除的对象赋值给oldValue
    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;
 }

删除指定对象

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) {
    //集合改变数据加1
    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
}

删除指定的集合元素

public boolean removeAll(Collection<?> c) {
    //判断对象是否为null
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //遍历数组，找出不需要删除的元素保存在数组前面
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //未完成遍历出错的情况下。
        if (r != size) {
            System.arraycopy(elementData, r,elementData, w,size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            //w为已经移到数组前面需要保留的数据，删除w之后的数据
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

删除所有元素

public void clear() {
    modCount++;

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

    size = 0;
}

set方法 get方法

/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

转为数组

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

//转化为任意类型的数组
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

小结

• ArrayList 采用动态数组。适合快速查找数据，不适合删除和添加操作
• 频繁扩容导致性能下降，可以初始化估计容量大小的arrayList
• ArrayList 线程不安全