Java ArrayList源码浅析

简介

ArrayList 是集合中最常见一个实现类，ArrayList继承AbstractList抽象类，实现List接口。

ArrayList UML图

ArrayList 定义

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList简单而言就是一个动态数组，它的容量是动态增长的，默认容量是10。它继承了AbstractList，实现了List、RandomAccess、Cloneable及Serializable接口。

1. RandomAccess：支持随机访问标记
2. Serializable：支持序列化

ArrayList属性

// 保存元素的数组
transient Object[] elementData;
// 数组实际大小（元素总数）
private int size;

构造方法

// 构造一个默认容量（10）的ArrayList
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 构造一个指定容量的ArrayList
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，这些元素的是按照Collection的迭代器返回的顺序排列的
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;
    }
}

方法摘要

返回类型	方法名称	描述
boolean	add(E e)	增加指定的元素
void	add(int, index, E e)	在指定位置元素
boolean	addAll(Collection<? extends E> c)	增加指定集合的所有元素
boolean	addAll(int index, Collection<? extends E> c)	在指定位置开始增加集合的所有元素
void	clear()	清空所有元素
Object	clone()	克隆副本
boolean	contains(Object o)	判断是否包含指定的元素。如存在返回true，否则返回false
void	ensureCapacity(int minCapacity)	如有必要增加容量，确保至少能容纳指定的（minCapacity）元素
void	forEach(Consumer<? super E> action)	迭代执行每个元素的业务逻辑直至完成或抛出异常
E e	get(int index)	返回指定位置的元素
int	indexOf(Object o)	返回列表中首次出现指定元素的位置，不存在返回-1
boolean	isEmpty()	判断集合是否为空
Iterator	iterator()	返回此集合元素的迭代器
ListItrator	listIterator()	返回列表中元素的列表迭代器（按适当的顺序）。
ListItrator	listIterator(int index)	返回从指定位置开始的列表迭代器（按适当的顺序）。
boolean	remove(Object o)	删除指定的元素
E	remove(int index)	删除列表指定位置的元素
boolean	removeAll(Collection<?> c)	删指定集合的所有元素
boolean	removeIf(Predicate<? super E filter)	删除满足条件的所有元素
void	removeRange(int fromIndex, int toIndex)	删除列表中fromIndex(含)到toIndex（含）之间的所有元素
E	set(int index, E e)	用指定的元素替换列表中指定位置的元素
int	size() 解析	返回集合元素大小
void	sort(Comparator<? super E> c)	排序
List	subList(int fromIndex, int toIndex)
Object[]	toArray()
T []	toArray(T [])
void	trimToSize()	容量调整为当前元素大小

核心源码（基于1.8）

增加元素

/**
 * 增加一个元素
 */
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!!
    // 拷贝数组，目的就空出index位置插入element，并将index之后的元素后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将数组index位置赋值
    elementData[index] = element;
    // 实际大小+1
    size++;
}
/**
 * 增加给定集合的所有元素
 */
public boolean addAll(Collection<? extends E> 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;
}
/**
 * 在指定位置增加一个集合
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 越界检查
    rangeCheckForAdd(index);
    // 转换为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 扩容检查
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 计算要移动的长度（index之后元素个数）
    int numMoved = size - index;
    if (numMoved > 0)
        // 拷贝数组，目的就空出index～index + numNew,位置插入element，并将index之后的元素后移一位
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 将要插入的集合元素复制到数组空出的位置中
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

/**
 * 下标越界检查
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * 扩容检查
 */
private void ensureCapacityInternal(int minCapacity) {
    // 如果当前数组为空，取minCapacity与缺省容量（10）较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 扩容
    ensureExplicitCapacity(minCapacity);
}
/**
 * 扩容
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果minCapacity大于当前数据容量增进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * 扩容
 */
private void grow(int minCapacity) {
    // 当前数组容量
    int oldCapacity = elementData.length;
    // 扩容后数组容量。即原来的1.5倍， oldCapacity>>1相当于oldCapacity/2取整
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩容后比需要的最小容量还小，则用最小需要容量扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果扩容后大于Integer.MAX_VALUE - 8，则用Integer.MAX_VALUE扩容
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 进行数据拷贝，Arrays.copyOf底层实现是System.arrayCopy()
    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;
}

扩容过程

0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	1	2	3	4	5	6	7	8	9

插入元素过程

0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5

0	1	2	3	4	5	6	7	8	9
0	1	2		3	4	5

0	1	2	3	4	5	6	7	8	9
0	1	2	9	3	4	5

删除元素

/**
 * 删除指定位置的元素
 */
public E remove(int index) {
    // 越界检查
    rangeCheck(index);
    modCount++;
    // 取出要删除的元素
    E oldValue = elementData(index);
    // 计算要复制（移动）的数量
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // index之后的元素前移一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 实际元素个数-1，最后个元素置空
    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) {
    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
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * 容量缩小为实际元素大小
 */
public void trimToSize() {
    modCount++;
    // 实际元素数小于数组容量
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

ArrayList遍历元素

1. 通过迭代器遍历

Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
    System.out.println(iter.next());
}

2. 随机访问，然后通过索引值遍历

for(int i=0;i<list.size();i++){
    System.out.println(list.get(i));
}

####3. foreach

for(Integer i : list) {
    System.out.println(list.get(i));
}

总结

1. ArrayList是基于动态数组实现的数据结构
2. 扩容时会扩充为原容量的1.5倍
3. 删除元素时不会自动缩容，但提供了trimToSize()方法缩容为实际元素大小
4. 随机（下标）访问效率高
5. 插入删除要移动数组，效率较低
6. 非线程安全

---

本系列文章是为团队内部分享参考网络资料及个人理解整理而成