ArrayList源码分析

2020-06-03

源码版本是java1.8。主要是分析他的增删查改，扩容机制，迭代器使用等。他基本复写了AbstractList和AbstractCollection中有所实现的方法。

构造方法

无参构造
给定一个初始化大小
把一个Collection的实现类通过toArray()方法转换成当前ArrayList可以装下的列表。
1
2
3
ArrayList()
ArrayList(int initialCapacity)
ArrayList(Collection<? extends E> c)

数据结构

我们首先需要了解一下两个外部方法

Arrays.copyOf 方法，他有几个重载的同名方法，但是作用都是类似的。他的作用是可以把一个数组赋通过System.arraycopy复制到一个新的数组当中，可以根据类型，需要复制的目标长度等进行复制，然后返回新数组。
System.arraycopy方法，他的一个主要方法是arraycopy(Object src, int srcPos, Object dest, intdestPos, int length)，其中src是原数组，srcPos是原数组开始复制的坐标，dest是目标数组，intdestPos是目标位置的开始坐标，length是复制的长度。

在ArrayList内部做一些数据操作，比如移除，扩容等的操作的时候基本都会使用到上面的两个方法去做。
ArrayList的存储数据结构是使用Object[]数组来存储，从这里我们就可以看得出泛型他是一种编译期的行为，因为Object是可以存储任何数据类型的。他不是用的E[]这样的泛型数组存储，看看他的成员变量：

//这是序列化的id
private static final long serialVersionUID = 8683452581122892189L;
//默认数组elementData的初始化大小，也就是当使用无参构造器的时候或者是传入的Collection为空的时候
private static final int DEFAULT_CAPACITY = 10;
//默认数组的值，使用指定长度或者是Collection传入为空的elementData默认值
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
//无参函数的elementData默认值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
//存储数据使用到的数组
transient Object[] elementData;
//当前的数据长度，需要注意这个不是elementData的长度，而是元素个数的长度
private int size;
//最大值，他的值是Integer.MAX_VALUE-8
private static final int MAX_ARRAY_SIZE = 2147483639;

扩容机制

因为在java中，数组一旦定义长度就不可以更改，但是我们的ArrayList是相当于可变长度数组，所以我们需要达到这个需求，就需要对elementData数组进行扩容，以add(E var1)方法为例。

调用该方法是往elementData中的末尾追加一个元素
调用之前需要通过ensureCapacityInternal(int var1)来保证当前elementData的长度是>=当前的size+1
通过calculateCapacity(Object[] var0, int var1)方法来确定当前的长度，假如当前的，elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取当前的DEFAULT_CAPACITY和size+1中的最大者，假如不是则取size+1
得到长度之后，通过ensureExplicitCapacity(int var1)方法来与当前的elementData数组长度进行比较，假如该长度比elementData.length大(不是相等)，则进行扩容
通过grow(int var1)方法进行扩容，var1是最少需要的长度，详细代码和解析如下

private void grow(int var1) {
        int var2 = this.elementData.length;
        //目标长度为var2+var2左移1位，也就是var3=1.5*var2，他是var2的1.5倍
        int var3 = var2 + (var2 >> 1);
        //假如var3比需要的小，则目标长度改为var1
        if (var3 - var1 < 0) {
            var3 = var1;
        }
        //如果目标长度比Integer.MAX_VALUE-8大，则再次检测，比Integer.MAX_VALUE则溢出，小则继续
        if (var3 - 2147483639 > 0) {
            var3 = hugeCapacity(var1);
        }
        //利用 Arrays.copyOf方法，把旧数组的全部复制到新数组中，新数组的长度为var3，完成扩容
        this.elementData = Arrays.copyOf(this.elementData, var3);
    }
    //检测是否溢出
    private static int hugeCapacity(int var0) {
        if (var0 < 0) {
            throw new OutOfMemoryError();
        } else {
            return var0 > 2147483639 ? 2147483647 : 2147483639;
        }
    }

方法和注意点

add相关的方法，包括addAll，是往里面增加元素
get 获取某个位置的元素
set 设置某个位置的元素
clear 清除全部元素
remove，这个方法需要我们调用的时候注意，假如我们使用的是ArrayList<Integer>，假如需要移除的是某个元素，则需要进行类型声明，比如list.remove((Integer)1)，否则是移除对应位置的元素。removeAll则是移除elementData中包含在传入参数的元素。比如

List<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        Set<String> sub = new HashSet<>();
        sub.add("1");
        sub.add("3");
        //只剩下2
        list.removeAll(sub);

retainAll 求与传入集合的交集，这个方法会改变当前集合，他只会保留相同的，不相同的去除。
toArray 把集合转为数组，需要注意假如是传入数组参数的话，他的长度加入比当前集合小，则是把集合前半部分(传入数组的长度)然后返回，否则是整个集合复制然后返回
contains，是否包含某个元素
isEmpty 是否是空集合
size() 集合的当前元素长度
indexOf，定位第一个出现索引到的元素的位置，lastIndexOf则是相反，是定位到最后一个与传入参数相同的元素的位置。
subList，返回一个从指定开始和结束位置的ArrayList，他不是我们java.util.ArrayList，而是这个ArrayList的子类SubList，当不做修改的时候，也就是subList的返回值只是比如用来get()，set之类的非结构性修改(不改长度)则会与源集合互相影响，当做结构性修改，比如remove之类的，则只能subList去做而且会反映到源集合，而源集合不能做结构性修改，否则会报错
forEach，这是java8中的用来自身直接替换一般的循环
replaceAll，对每一个元素进行某种规则的替换
sort，使用某一种排序方法对集合进行排序。
Iterator 返回一般的迭代器
listIterator 返回ListIterator对象，可以进行增删改

迭代器

主要是讲ListIterator，在ArrayList中实现了该接口，实现的内部类是ArrayList.ListItr，他的构造方法是ListItr(int var2)，传入的参数是某个元素的位置，传入之后就把ListIterator的游标指向这里，然后通过内部类可以访问外部类的方法来实现修改elementData的目的。他可以向前或者向后遍历都是可以的。

其他实现接口

Cloneable ，实现了这个接口则是说明ArrayList可以通过clone()方法进行复制
Serializable，实现了这个说明可以进行序列化
RandomAccess，这个是一个标记性接口，它的作用就是用来快速随机存取，实现了该接口，那么使用普通的for循环来遍历，性能更高