【集合】- ArrayList源码分析

简介

概述

ArrayList底层是一个数组，数组元素类型为object，支持动态扩容，所以ArrayList也相当于一个动态数组；ArrayList继承自 AbstractList，实现了 List 接口，允许 null 的存在；

接下来我们通过类层次结构、构造方法及常用方法三方面看ArrayList源码；

类图-继承关系

ArrayList继承了AbstractList，实现了List、RandomAccess、Serializable、Cloneable这些接口；

• List：是一个数组队列，提供了相关的添加、删除、修改、遍历等操作；
• RandomAccess：提供了随机访问功能，ArrayList中可以通过元素序号快速获取元素对象；
• Serializable：表示ArrayList支持序列化
• Cloneable：支持克隆

ArrayList的实现

属性

    /**
     * 存储ArrayList元素的数组，
     * 添加到 ArrayList 中的元素数据（第一次添加元素时，空ArrayList会扩容到 DEFAULT_CAPACITY = 10 ）
     */
    transient Object[] elementData;

    /**
     * ArrayList大小，包含元素数量
     */
    private int size;
1
2
3
4
5
6
7
8
9
10

构造方法

1. ArrayList()无参构造方法

DEFAULTCAPACITY_EMPTY_ELEMENTDATA，使用无参构造方法创建ArrayList数组的时候，是一种懒加载模式，创建的时候不设置大小，而是在使用的时候设置大小；

//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的共享空数组实例，从0开始，按照1.5倍扩容
private static final Object[] EMPTY_ELEMENTDATA = {};

//共享的空数组对象，用户ArrayList() 构造方法，和EMPTY_ELEMENTDATA区分开，在第一次添加元素时，首次扩容为10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3
4
5
6
7
8
9
10
11

2. ArrayList(int initialCapacity)

根据传入的初始化容量，创建Array数组，如果传入参数是大于等于0，则使用用户的参数初始化，如果传入参数小于0，则抛异常；

public ArrayList(int initialCapacity) {
	//初始化容量>0时，创建Object数组
	if (initialCapacity > 0) {
	     this.elementData = new Object[initialCapacity];
	 //初始化容量=0时，使用EMPTY_ELEMENTDATA对象
	 } else if (initialCapacity == 0) {
	     this.elementData = EMPTY_ELEMENTDATA;
	 //初始化容量<0时，抛IllegalArgumentException异常
	 } else {
	     throw new IllegalArgumentException("Illegal Capacity: "+
	                                        initialCapacity);
	 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. ArrayList(Collection c)

构造一个包含指定集合元素的列表，这些元素按照 collection 集合迭代器返回的顺序排列的

/**
 * 按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表
 */
public ArrayList(Collection<? extends E> c) {
	//将C 转换为 object 数组
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
    	//判断集合元素是否为 Object[]类型，不是的话，会创建新的 Object[]数组，并把 elementData 赋值到新数组中，最后赋值给 elementData
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    //如果数组size = 0 ,则直接将空对象 EMPTY_ELEMENTDATA 
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

常用方法

1. add(E e) 方法

顺序添加单个元素到数组

/**
 * 在列表末尾添加元素
 */
public boolean add(E e) {
	//增加数组操作次数
    modCount++;
    //添加元素
    add(e, elementData, size);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    //如果容量不够，进行扩容
    if (s == elementData.length)
        elementData = grow();
    //设置到末尾
    elementData[s] = e;
    //数量大小加一
    size = s + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. add(int index, E element) 方法

插入单个元素到指定位置

public void add(int index, E element) {
    // 校验位置是否在数组范围内
    rangeCheckForAdd(index);
    // 增加数组修改次数
    modCount++;
    //如果数组大小不够，进行扩容
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    //将 index + 1 位置开始的元素，进行往后挪
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    //设置到指定位置
    elementData[index] = element;
    //数组大小加一
    size = s + 1;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3. addAll(Collection c) 方法

批量添加多个元素，如果明确知道会添加多个元素时，使用该方法，避免使用单个元素添加带来的多次扩容；

public boolean addAll(Collection<? extends E> c) {
    //转成 a 数组
    Object[] a = c.toArray();
    //增加操作次数
    modCount++;
    //如果 a 数组大小为 0 ，返回 ArrayList 数组无变化
    int numNew = a.length;
    if (numNew == 0)
        return false;
    //如果 elementData 剩余的空间不够，则进行扩容。要求扩容的大小，至于能够装下 a 数组。
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    //将 a 复制到 elementData 从 s 开始位置
    System.arraycopy(a, 0, elementData, s, numNew);
    //数组大小加 numNew
    size = s + numNew;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4. addAll(int index, Collection c) 方法

从指定位置开始批量添加多个元素

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    // 增加数组修改次数
    modCount++;
    //如果 a 数组大小为 0 ，返回 ArrayList 数组无变化
    int numNew = a.length;
    if (numNew == 0)
        return false;
    //如果 elementData 剩余的空间不够，则进行扩容，扩容的大小，至于能够装下 a 数组。
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    /**
     * 如果 index 开始的位置已经被占用，将原有元素向后移
     */ 
    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    //将 a 复制到 elementData 从 s 开始位置
    System.arraycopy(a, 0, elementData, index, numNew);
    //数组大小加 numNew
    size = s + numNew;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

5. remove(int index)方法

删除index位处的数据

public E remove(int index) {
    //校验 index 不要超过 size
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    //记录该位置的原值
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    //快速移除
    fastRemove(es, index);
    //返回该位置的原值
    return oldValue;
}
1
2
3
4
5
6
7
8
9
10
11

6. fastRemove(Object[] es, int i)快速删除

private void fastRemove(Object[] es, int i) {
    //增加数组修改次数
    modCount++;
    //如果 i 不是最末尾的元素，则将 i + 1 位置的数组往前挪
    final int newSize;
    if ((newSize = size - 1) > i) // -1: size 是从 1 开始，而数组下标是从 0 开始
    	//把i+1位后的 newSize-i的数据往前移一位
        System.arraycopy(es, i + 1, es, i, newSize - i);
    //末尾置为 null
    es[size = newSize] = null;
}
1
2
3
4
5
6
7
8
9
10
11

7. indexOf(Object o)查找单个元素

获取指定元素位置，找不到，返回-1

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    //null 的情况
    if (o == null) {
    	//从start循环到end,如果数据为空，则返回对应下标
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    //非 null 的情况
    } else {
        for (int i = start; i < end; i++) {
        	//调用目标函数的equals方法
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

8. lastIndexOf(Object o) 方法

查找元素最后一次出现位置

public int lastIndexOf(Object o) {
	//范围内查询元素最后一次出现位置（即逆第一次出现位置）
    return lastIndexOfRange(o, 0, size);
}
int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = end - 1; i >= start; i--) { // 倒序
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = end - 1; i >= start; i--) { // 倒序
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

9. clone() 方法

克隆 ArrayList 对象

// ArrayList.java
public Object clone() {
    try {
        //调用父类，进行克隆
        ArrayList<?> v = (ArrayList<?>) super.clone();
        //拷贝一个新的数组
        v.elementData = Arrays.copyOf(elementData, size);
        //设置数组操作次数为0
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

10. grow()扩容方法

创建一个新的更大的数组，然后将原数组复制到新数组中，最后返回新数组
以下是扩容核心代码：

//JDK 9
private Object[] grow() {
    //调用 #grow(int minCapacity) 方法，要求扩容后至少比原有大1 
    return grow(size + 1);
}
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //如果原容量大于0 ，或者数组不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，计算新的数组大小，并扩容
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity,
                oldCapacity >> 1 
        return elementData = Arrays.copyOf(elementData, newCapacity);
    //如果是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组，直接创建新的数组
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//JDK8
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //将 oldCapacity 右移一位，相当于 oldCapacity / 2
        //将容量更新为 原容量 的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //判断 新容量 与 最小需要容量，如果新容量 < 最小需要容量，就把最小需要容量作为 新容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果 新容量 > MAX_ARRAY_SIZE，就 比较 minCapacity 和 MAX_ARRAY_SIZE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //如果 minCapacity > MAX_ARRAY_SIZE，则 新容量为 Integer.MAX_VALUE，否则为 MAX_ARRAY_SIZE
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 初始化ArrayList数组时有无参，无参，则在添加第一个元素的时候，设置 newCapacity = minCapacity(10)，当添加第 11 个元素时，进行扩容，执行 grow() 方法，newCapacity = 15，数组容量扩容至 15，size = 11；
• 有参时，使用参数容量，添加元素时，判断 容量 够不够，容量满了进行扩容

“>>” 移位运算符：>>1 向右移一位相当于除以2，右移 N 位相当于除以2的 N 次方；
oldCapacity >> 1：oldCapacity 右移了一位，相当于 oldCapacity / 2；

11. set(int index, E element)方法

set(int index, E element)方法，设置指定位置的元素

public E set(int index, E element) {
    // 校验index不要超过 size
    Objects.checkIndex(index, size);
    // 获得index位置的原元素
    E oldValue = elementData(index);
    // 修改index位置为新元素
    elementData[index] = element;
    // 返回index位置的原元素
    return oldValue;
}
1
2
3
4
5
6
7
8
9
10

12. get(int index) 方法

get(int index) 方法获取指定位置的元素

public E get(int index) {
    Objects.checkIndex(index, size);
    //获得 index 位置的元素
    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}
1
2
3
4
5
6
7
8

常见问题

总结

• ArrayList本质是一个数组，动态数组，创建时可以指定初始化容量，当添加元素超过当前容量大小时，会调用grow()进行扩容;
• 查询元素效率高，插入和删除元素效率不高