ArrayList源码解析了解一下

发表于 | 分类于 ， | 评论数：   |   字数统计: 3,752   |   阅读时长: 17min | 热度： ℃

前言

ArrayList是我们最常使用的数据类型之一，也是面试中最容易问到的集合之一。本篇文章主要通过分析ArrayList的源码，更深入的了解ArrayList，ArrayList在JDK1.8中添加了一些新的方法。

本文基于jdk1.8

ArrayList简介

ArrayList底层是一个数组，它的容量可以动态增长。

ArrayList类结构

ArrayList类结构图

可以从上图看出，ArrayList继承AbstractList抽象类，实现了List，Cloneable，Serializable，RandomAccess接口。

ArrayList特点

  1. ArrayList非线程安全，在多线程中保证线程安全的解决方法：使用CopyOnWriteArrayList，Vector，List list = Collections.synchronizedList(new ArrayList());。
  2. ArrayList允许插入null。
  3. ArrayList中的数据存储是有序的。
  4. ArrayList中的数据可以重复。

ArrayList提供的API

方法名 方法解释
add(E e) 将指定的元素添加到ArrayList的末尾。
add(int index, E element) 将指定的元素插入到ArrayList中的指定位置。
addAll(Collection<? extends E> c) 将指定的集合中的所有元素添加到ArrayList的末尾。
addAll(int index, Collection<? extends E> c) 将指定的集合中的所有元素添加到ArrayList中的指定位置。
clear() 删除ArrayList中的所有元素。
clone() ArrayList浅拷贝。
contains(Object o) 判断ArrayList中是否包含指定元素。
ensureCapacity(int minCapacity) 如有必要，增加ArrayList的容量，以确保它至少能容纳由最小容量参数指定的元素数量。
forEach(Consumer<? super E> action) 将消费操作（Consumer）应用于ArrayList的每一个元素，直到处理完所有数据或操作抛出异常为止。
get(int index) 获取ArrayList中指定位置的元素。
indexOf(Object o) 返回ArrayList中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。
isEmpty() 判断ArrayList是否为空。
iterator() 返回ArrayList中元素的迭代器。
lastIndexOf(Object o) 返回ArrayList中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。
listIterator() 返回ArrayList中元素的列表迭代器。
listIterator(int index) 从ArrayList中指定的位置开始，返回ArrayList中元素的列表迭代器。
remove(int index) 删除ArrayList中指定位置的元素。
remove(Object o) 从ArrayList中删除第一次出现的指定元素（如果存在）。
removeAll(Collection<?> c) 从ArrayList中删除指定集合中包含的所有元素。
removeIf(Predicate<? super E> filter) 删除ArrayList中满足给定谓词（Predicate）的所有元素。
removeRange(int fromIndex, int toIndex) 从ArrayList中删除索引介于fromIndex（包含）和toIndex（不包括）之间的所有元素。
replaceAll(UnaryOperator operator) 将运算符（UnaryOperator）应用于该元素的结果替换ArrayList中的每个元素。
retainAll(Collection<?> c) 只保留包含在指定集合中的ArrayList中的元素。
set(int index, E element) 用指定的元素替换ArrayList中指定位置的元素。
size() 获取ArrayList大小。
sort(Comparator<? super E> c) 根据指定的比较器对ArrayList进行排序。
spliterator()
subList(int fromIndex, int toIndex) 返回指定的fromIndex（包含）和toIndex（不包括）之间的部分list。
toArray() 将ArrayList转换为数组。
toArray(T[] a) 将ArrayList转换为指定类型的数组。
trimToSize() 去除ArrayList中为空的位置，将此ArrayList的容量修改为数组的当前大小。

ArrayList源码

ArrayList常量属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 初始化容量为10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * ArrayList容量指定为0时，返回该空数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 默认返回的空数组，用户调用无参构造函数，刚创建一个ArrayList时，内部大小为0，返回的是该空数组
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * ArrayList数组的最大值，-8是因为有些版本的虚拟机会保留8个字节长度的header
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList成员变量

1
2
3
4
5
6
7
8
9
/**
 * ArrayList元素保存的数组
 */
transient Object[] elementData;

/**
 * ArrayList大小
 */
private int size;

ArrayList内部类

ArrayListSpliterator

TODO

ArrayList构造函数

ArrayList一共有三个构造函数

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
/**
 * 指定一个初始容量的构造函数。
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 指定了初始容量为0，数组就是EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * 无参构造函数，构造一个初始容量为默认值10的ArrayList。
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 通过Collection创建ArrayList。
 */
public ArrayList(Collection<? extends E> c) {
    // 将参数c转为数组
    elementData = c.toArray();
    // 判断数组是否为空，并且设置ArrayList的大小
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // 判断数组的类型是否是Object
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        // 空的数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

ArrayList重要方法解析

arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

1
2
3
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

该方法是native修饰的，由C/C++来编写的。

参数解释：

参数名 参数解释
src 源数组，即被复制的数组
srcPos 源数组被复制的起始位置
dest 目标数组，即源数组的元素会被复制到该数组
destPos 元素放置在目标数组的起始位置
length 复制的长度

add(E e)

1
2
3
4
5
6
7
8
public boolean add(E e) {
    // 尝试容量加1，计算需要的最小容量
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 向数组中添加元素，大小加1
    elementData[size++] = e;
    // 返回成功
    return true;
}

  • ensureCapacityInternal(int minCapacity)

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

  • calculateCapacity(Object[] elementData, int minCapacity)

    1
    2
    3
    4
    5
    6
    7
    8
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 判断是否为空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 获取最小的容量
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

  • ensureExplicitCapacity(int minCapacity)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    private void ensureExplicitCapacity(int minCapacity) {
        // 操作次数加1
        modCount++;

        // overflow-conscious code
        // 需要的最小容量比数组的长度大，就调用grow()进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

  • grow(int minCapacity)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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);
        // minCapacity is usually close to size, so this is a win:
        // 扩容之后进行复制
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

  • hugeCapacity(int minCapacity)

    1
    2
    3
    4
    5
    6
    7
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
    }

  • copyOf(T[] original, int newLength)

    1
    2
    3
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

  • copyOf(U[] original, int newLength, Class<? extends T[]> newType)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        // 获取目标数组
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

add(E e)流程：

  1. 计算需要最小的数组容量
  2. 操作次数加1
  3. 判断计算出来的容量是否大于原数组的长度
  4. 如果计算出来的容量大，就进行扩容
  5. 扩容是将原数组扩大到1.5倍
  6. 最后进行添加元素操作，ArrayList大小加1，并返回成功

add(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void add(int index, E element) {
    // 判断下标是否越界
    rangeCheckForAdd(index);

    // 尝试容量加1，计算需要的最小容量
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将下标之后的数据都往右移动一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 添加元素
    elementData[index] = element;
    // 大小加1
    size++;
}

  • rangeCheckForAdd(int index)

    1
    2
    3
    4
    5
    private void rangeCheckForAdd(int index) {
        // 判断下标是否越界
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

addAll(Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean addAll(Collection<? extends E> c) {
    // 将集合转换为数组
    Object[] a = c.toArray();
    // 集合转换为的数组的长度
    int numNew = a.length;
    // 尝试容量加1，计算需要的最小容量
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将转换为的数组添加到ArrayList数组的后面
    System.arraycopy(a, 0, elementData, size, numNew);
    // 增加数组大小
    size += numNew;
    // 返回结果
    return numNew != 0;
}

addAll(int index, Collection<? extends E> c)

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
public boolean addAll(int index, Collection<? extends E> c) {
    // 判断下标是否越界
    rangeCheckForAdd(index);

    // 将集合转换为数组
    Object[] a = c.toArray();
    // 集合转换为的数组的长度
    int numNew = a.length;
    // 尝试容量加1，计算需要的最小容量
    ensureCapacityInternal(size + numNew);  // Increments modCount

    // 计算需要向右移动的元素数量
    int numMoved = size - index;
    // 如果需要移动的数量大于0，进行相关的移动
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    // 将集合转换的数组添加到ArrayList中
    System.arraycopy(a, 0, elementData, index, numNew);
    // 增加ArrayList大小
    size += numNew;
    // 返回结果
    return numNew != 0;
}

contains(Object o)

1
2
3
4
public boolean contains(Object o) {
    // 根据匹配方法返回的元素下标判断是否存在该对象
    return indexOf(o) >= 0;
}

  • indexOf(Object o)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public int indexOf(Object o) {
        if (o == null) {
            // 判断的对象为null，遍历数组，返回匹配到的下标
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            // 判断的对象不为null，遍历数组，返回匹配到的下标
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        // 没有匹配到返回-1
        return -1;
    }

get(int index)

1
2
3
4
5
6
7
public E get(int index) {
    // 判断下标是否越界
    rangeCheck(index);

    // 返回查找的元素
    return elementData(index);
}

  • elementData(int index)

    1
    2
    3
    4
    E elementData(int index) {
        // 返回数组中的元素
        return (E) elementData[index];
    }

    get(int index)流程：

  1. 判断数组下标是否越界
  2. 根据下标获取数组中的元素

remove(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E remove(int index) {
    // 判断下标是否越界
    rangeCheck(index);

    // 操作次数加1
    modCount++;
    
    // 获取下标匹配的数组元素
    E oldValue = elementData(index);

    // 计算需要移动的元素数量
    int numMoved = size - index - 1;
    // 如果需要向左移动的数量大于0，就进行相关的移动
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将数组最后一位元素置为null，并且大小减1
    elementData[--size] = null; // clear to let GC do its work

    // 返回原来的元素
    return oldValue;
}

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean remove(Object o) {
    // 如果需要移除的元素为null
    if (o == null) {
        // 遍历数组进行匹配，并删除，返回true
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // 遍历数组进行匹配，并删除，返回true
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    // 返回false
    return false;
}

  • fastRemove(int index)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    private void fastRemove(int index) {
        // 操作加1
        modCount++;
        // 计算需要向左移动的元素数量
        int numMoved = size - index - 1;
        // 如果要移动的数量大于0，进行相关的复制
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将数组最后一位元素置为null，并且大小减1
        elementData[--size] = null; // clear to let GC do its work
    }

removeAll(Collection<?> c)

1
2
3
4
5
6
public boolean removeAll(Collection<?> c) {
    // 判断是否为null，如果为null，抛出空指针异常
    Objects.requireNonNull(c);
    // 批量删除
    return batchRemove(c, false);
}

  • batchRemove(Collection<?> c, boolean complement)

    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
    private boolean batchRemove(Collection<?> c, boolean complement) {
        // 获取ArrayList数组
        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
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

removeIf(Predicate<? super E> filter)

TODO

replaceAll(UnaryOperator operator)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void replaceAll(UnaryOperator<E> operator) {
    // 判断操作方法是否为null
    Objects.requireNonNull(operator);
    // 设置预期操作次数
    final int expectedModCount = modCount;
    // 设置大小
    final int size = this.size;
    // 遍历ArrayList，对每一个元素进行操作
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        elementData[i] = operator.apply((E) elementData[i]);
    }
    // 在调用该方法的时候，ArrayList的操作次数改变了，就抛出并发异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    // 操作次数加1
    modCount++;
}

set(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
public E set(int index, E element) {
    // 判断下标是否越界
    rangeCheck(index);

    // 获取下标对应的元素
    E oldValue = elementData(index);
    // 将新的元素设置到下标位置
    elementData[index] = element;
    // 返回旧的值
    return oldValue;
}

sort(Comparator<? super E> c)

1
2
3
4
5
6
7
8
9
10
11
12
public void sort(Comparator<? super E> c) {
    // 设置预期操作次数
    final int expectedModCount = modCount;
    // 调用Arrays的排序
    Arrays.sort((E[]) elementData, 0, size, c);
    // 在调用该方法的时候，ArrayList的操作次数改变了，就抛出并发异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    // 操作次数加1
    modCount++;
}

trimToSize()

1
2
3
4
5
6
7
8
9
10
public void trimToSize() {
    // 操作次数加1
    modCount++;
    // 判断ArrayList大小是否小于数组的长度，是的话就去除数组中空的值
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

为什么ArrayList不能在for-each循环中删除元素

for-each循环时，会调用ArrayList的内部类Itr的hashNext方法进行判断是否还有下一个元素需要遍历。

hasNext()

1
2
3
4
public boolean hasNext() {
    // 判断元素下标是否与ArrayList大小相同
    return cursor != size;
}

可以看出若删除前面的元素，此处就会为true

ps：删除倒数第二个元素，cursor就是最后一个索引值size()-1 ，size也-1了，此处会返回false，不会调用next方法了（即不存在操作次数的判断）。所以可以删除倒数第二个元素。

如果hashNext方法返回true，就会继续调用next方法获取下一个元素。

next()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E next() {
    // 判断操作次数与预期的是否相同
    checkForComodification();
    // 获取元素下标
    int i = cursor;
    // 判断元素下标是否越界
    if (i >= size)
        throw new NoSuchElementException();
    // 获取ArrayList元素
    Object[] elementData = ArrayList.this.elementData;
    // 判断是否有删除操作
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    // 获取元素
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

我们看一下checkForComodification方法：

1
2
3
4
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

这里的modCount经过remove之后，已经+1了，所以这里的modCount和expectModCount肯定不相等，所以会抛出ConcurrentModificationException异常。

总结

通过这篇文章，我们对ArrayList进行了更深入的了解，这有利于我们之后使用ArrayList。可以避免遇到一些坑。

ps：有一些TODO的内容，后续有空了再进行添加。

欢迎关注博主其他的文章。

感谢您的支持！

本文标题:ArrayList源码解析了解一下

文章作者:yoga

发布时间:2017年01月19日 - 20:01

原始链接:https://yoga0521.github.io/2017/01/19/ArrayList源码了解一下/

版权声明:本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。 转载请注明出处！