ArrayList源码分析

2019 Java 开发者跳槽指南.pdf (吐血整理)….>>>

目录

1. 概述

为了弥补普通数组无法自动扩容的不足,Java提供了集合类,其中ArrayList就对数组进行了封装,使其可以自动的扩容或缩小长度。

因为是对数据进行了封装,所以底层存储结构是数组结构。可以想象的到,数组长度的自动变化必须需要开辟新内存,然后进行数组元素的拷贝。

因为数组,所以ArrayList也就具有数组的一些性,如支持随机访问。

2. 继承、实现结构

解释一下这些类、接口:

  1. Iterable:定义了集合内元素的循环
  2. Collection:集合类的老大,定义了一些常规操作
  3. AbstractCollection:老大的抽象实现类,实现了简单的方法
  4. List:是ArrayList的父接口
  5. Serializable:标志着类对象可以进行序列化
  6. RandomAccess:支持随机访问
  7. Cloneable:对象可以进行克隆

3. 构造方法

先从构造方法开始分析。

无参构造方法

1
2
3
4
5
6
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

注释说,构造一个容量为10的空的list。

但是这里我们并没有看到数组的容量变为10,而是一个空的数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

那么什么时候会被初始化为10的数组呢?答案是有元素被加入时(add方法)。

带有初始化容量的构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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大小的数组。

入参为集合的构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
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;
    }
}

这里的意思传入一个集合类(Collection的子类即可),转为list。

Collection有一个子抽象类,默认实现了toArray();,如果子类比较特殊需要,进行重写即可。

4. 集合的操作

集合类的重要功能就是进行交互(元素的存储、修改、删除、遍历等)。

4-1. 添加

内部有四种方式的添加:

  1. 直接添加
  2. 指定位置添加
  3. 添加全部
  4. 在指定位置添加全部

4-1-1. 直接添加

因为是动态数组,所以元素添加时需要校验数组空间是否足够,如果不足,需要进行数组的扩容(关于扩容看第5节)。

源码如下:

1
2
3
4
5
6
7
8
9
10
11
/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

4-1-2. 指定位置添加

在指定位置添加,必然会影响到该位置的元素以及后续元素,对于数组这种数据结构,只能进行元素的后移了。

这就体现出数组这种数据结构的不足了:对元素的修改不太擅长。

同普通添加元素一样,需要校验数组容量数组足够,不过在校验之前还要检查一下入参的元素位置(index)是否在范围内。

然后进行数组元素的移动。

源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
 
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

4-1-3. 添加全部

与构造方法类似,这里也使用了toArray();

只不过需要进行数组大小的校验扩容,然后进行元素拷贝。

1
2
3
4
5
6
7
8
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;
}

4-1-4. 在指定位置添加全部

通过上面的说明,这个方法就很容易懂了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

4-2. 修改

修改操作比较简单,就是给数组的某个下标重新赋值。

只有一个方法:E set(int index, E element)

将指定位置上的元素进行更新,会对index进行越界检查。

4-3. 删除

删除操作也意味着数组中会有元素移动,除非删除的是最后一个元素。

删除方法有一下几个:

  1. E remove(int index)
  2. boolean remove(Object o)
  3. boolean removeAll(Collection<?> c)
  4. boolean retainAll(Collection<?> c)

4-3-1. 指定位置删除 E remove(int index)

删除指定位置上的元素,如果删除的不是最后一个元素,则要进行元素的移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
    rangeCheck(index); // 检查下标是否越界
 
    modCount++;
    E oldValue = elementData(index);
 
    int numMoved = size - index - 1; // 最后 -1 是为了数组下标不越界
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
 
    return oldValue;
}

4-3-2. 删除一个元素 boolean remove(Object o)

删除数组中的某个元素,会分为两种情况:null OR !null。

找到元素之后会使用fastRemove(index)进行删除。

源码如下:

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
// 删除成功返回true,失败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;
}
 
// 快速删除指定下标的元素,无越界检查
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
}

4-3-3. 删除所有的元素

传入一个集合c,如果集合c中包含本集合中的元素,则对改元素进行处理,这里利用了一个complement属性,来决定含有的元素是删除还是保留。

简单说一下批量删除/保留操作,把匹配的元素(c.contains(elementData[r]) == complement)进行保留。

然后对不需要保留的下标赋予null值。

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
29
30
31
32
33
34
35
36
public boolean removeAll(Collection<?> c) {
    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++)
            // 如果complement为false,则c集合包含本集合中的元素,则不进行操作,这就是保留不属于c集合中的所有元素。
            // 这就是 4-3-4. boolean retainAll(Collection<?> c)
            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
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

4-4. 查找

这部分就不贴源码了,很容易理解。

查找可以分为两种情况:

  1. 通过下标直接定位元素
  2. 通过元素进行定位下标

包含的方法:

  1. boolean contains(Object o)
  2. int indexOf(Object o)
  3. int lastIndexOf(Object o)
  4. E elementData(int index)
  5. E get(int index)

contains(Object o)方法使用了indexOf(Object o)作为底层实现,我们需要了解indexOf(Object o)的底层实现。

indexOf(Object o)是从数组的头开始查找,查找到相同元素时,进行返回,而lastIndexOf(Object o)正好相反,从数组的尾开始查找,查找到相同元素时进行返回。

可以使用indexOf和lastIndexOf进行返回值的比较,如果相等,说明该元素在数组中唯一(前提是返回非-1)。

elementData(int index)则是内部方法,获取指定下标处的元素。

而get(int index)内部调用了element(int index),调用之前会进行下标越界的校验。

4-5. 遍历

遍历分为三种方式:

  1. 普通for
  2. foreach
  3. iterator

至于三种方式的性能,自己测试吧,哈哈哈

重点:只有某种情况下的普通for和iterator可以在循环的同事进行元素的删除。

例如:

普通for

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 该情况下不会发生异常
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);
    // do something...
    list.remove(i);
}
 
// 这种情况会出现越界问题
int size = list.size();
for (int i = 0; i < size; i++) {
    String s = list.get(i);
    // do something...
    list.remove(i);
}

第一种情况下,for循环的终止条件会随着数组元素的移除不断的变化。
第二种情况下,for循环的种植条件不会变化。

foreach

1
2
3
4
for (String s : list) {
    // do something...
    list.remove(s);
}

这种方式会发生ConcurrentModificationException,因为ArrayList内部有一个属性为modCount,每当数组中的元素发生变化是,该数值会增1,而foreach形式的循环编译后会变为

1
2
3
4
5
6
Iterator var2 = list.iterator();
 
while(var2.hasNext()) {
    String s = (String)var2.next();
    list.remove(s);
}

这种形式。因为ArrayList内部的Iterator也维护了一个属性expectedModCount来标识数组元素的变化,初始化为modCount,如果modCount与expectedModCount不一致的话,就会抛出这个异常。

iterator

1
2
3
4
5
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    // do something...
    iterator.remove();
}

foreach时我们直接调用了list.remove(s);方法,该方法只会改变modCount的值,并不会改变expectedModCount的值,相反,使用Iterator提供的remove方法则会对两个值一起修改。

5. 扩容方式

首先记住一点:每次会扩容原数组的 1.5倍(正常情况下)。

非正常情况当前是两端的情况:

  1. 初始化时第一次扩容会扩容到初始化容量(DEFAULT_CAPACITY)
  2. 当容量达到最大值时不会遵循这个规律

扩容方式:在每次添加新元素时,会调用扩容代码,扩容方式还是比较简单的。只是进行了一些防止溢出的判断。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 进行扩容调用
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
 
// 计算是使用 DEFAULT_CAPACITY 还是传入的 minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
 
    // 当使用 new ArrayList() 创建实例时,数组的默认容量为10就是在这里产生的。
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
 
// 进行一次modCount的修改,表示数组元素发生了变动
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
 
    // overflow-conscious code
    // 防止元素溢出
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
 
/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 获取旧数组长度
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 计算出新数组长度 oldCapacity + oldCapacity / 2。
    if (newCapacity - minCapacity < 0) // 如果计算出的长度比传入的长度小,则使用传入的长度作为新数组长度。
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新数组长度比MAX_ARRAY_SIZE,进行溢出的校验
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 进行数组的拷贝
    elementData = Arrays.copyOf(elementData, newCapacity);
}
 
// 如果minCapacity比MAX_ARRAY_SIZE大,就取Integer.MAX_VALUE的值作为新数组长度,否则使用MAX_ARRAY_SIZE
// 也就是传入的长度,而非通过原数组计算出来的长度。
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

 

原文链接:https://www.cnblogs.com/wuqinglong/p/9597694.html