写点什么

ArrayList 源代码分析

用户头像
肥鱼先生
关注
发布于: 2020 年 12 月 31 日
ArrayList源代码分析

此篇主要解析 ArrayList 的源码处理逻辑

继承关系


几个有意思的参数

// 默认初始容量private static final int DEFAULT_CAPACITY = 10;// 共享空数组private static final Object[] EMPTY_ELEMENTDATA = {};// 同上private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 指向实际存储数据的数组transient Object[] elementData;// 当前列表中所含元素的个数private int size;
复制代码

为什么会有两个空数组

源代码中的解释:为了在添加第一个元素时,确定初始空间的大小。

此话怎讲?先从上述两变量的引用处说起。初始化一个 ArrayList 对象的构造函数有 3 个,分别如下

// 不带任何参数public ArrayList() {    // 当第一次添加元素时,元素个数小于10,初始容量置为10    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}// 指明容器初始容量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);    }}// 从集合中添加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;    }}
复制代码

可以看出,只有没有指明容量的情况下,才会使用 DEFAULTCAPACITYEMPTYELEMENTDATA。且在添加第一个元素时,会进行相应的判断,如果为 DEFAULTCAPACITYEMPTYELEMENTDATA 就会使用默认的容量 10。

public boolean add(E e) {  ensureCapacityInternal(size + 1);  elementData[size++] = e;  return true;}private void ensureCapacityInternal(int minCapacity) {  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  }  // 由此看来,初始化的容量会因为上述两个空数组的不同而不同  ensureExplicitCapacity(minCapacity);}
复制代码

那为什么不能在 ArrayList() 中使用 EMPTY_ELEMENTDATA 呢?因为这样会与 ArrayList(int initialCapacity) 一样,但后者必须初始化成指定的容量,如 0。

为什么可以序列化却使用了`transient`修饰`elementData`

数组中所有的容量并非一直都被元素占用,可能会存在此数组大部分空间并未使用的情况,此时序列化所有的元素会比较浪费空间。因此在这里源码选择的是,将所有添加的元素,进行序列化。

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException    // Write out element count, and any hidden stuff    int expectedModCount = modCount;    s.defaultWriteObject();    // Write out size as capacity for behavioural compatibility with clone()    s.writeInt(size);    // Write out all elements in the proper order.    for (int i=0; i<size; i++) {        s.writeObject(elementData[i]);    }    // ...}
复制代码

带参与不带参构造函数之间的差别是什么

添加第一个元素之后,容量不一样。

增加元素

增加元素到 list 当中,也就是我们常用的add()。有两种增加方式,一种是添加元素到尾端:

// 添加到列表的尾部public boolean add(E e) {    ensureCapacityInternal(size + 1);    // 此时elementData的长度已经被保证可以存下当前元素    elementData[size++] = e;    return true;}// 此函数的主要作用是确定列表初始容量private void ensureCapacityInternal(int minCapacity) {    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }// 此处的解析如前面对初始容量那块所述    ensureExplicitCapacity(minCapacity);}// 检测是否需要扩容private void ensureExplicitCapacity(int minCapacity) {    modCount++;    //当前的minCapacity为size+1或10,所以当此条件成立时,说明再不扩容    //将有可能导致溢出    if (minCapacity - elementData.length > 0)        grow(minCapacity);}// 扩容private void grow(int minCapacity) {    // 防止溢出    int oldCapacity = elementData.length;    // 右移1位,变成一半,因此此时的容量变成了之前的1.5倍    int newCapacity = oldCapacity + (oldCapacity >> 1);    // 若新的容量比所需要的最小容量小,那么将新容量改成最小所需容量    if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    // 若新的容量比MAX_ARRAY_SIZE大    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);    // 分配新的数组,并将原数据拷贝到其中    elementData = Arrays.copyOf(elementData, newCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private static int hugeCapacity(int minCapacity) {    // 此时已超过Integer.MAX_VALUE,变成负数,溢出    if (minCapacity < 0)        throw new OutOfMemoryError();    // 到这一步,有两个原因:    // 1. 通过扩容至原来的1.5倍,引起比MAX_ARRAY_SIZE大;    // 2. 此次加入的元素数量太多,以至于1.5倍的扩容也不能满足。    return (minCapacity > MAX_ARRAY_SIZE) ?        Integer.MAX_VALUE :// 此处为第二种情况        MAX_ARRAY_SIZE;// 此处为第一种情况}
复制代码

一种是将元素添加元素到列表中的某一位置。


// 添加到列表中的某个位置public void add(int index, E element) {    rangeCheckForAdd(index);// 检查index是否合理,比如说超出当前size以及小于0    ensureCapacityInternal(size + 1); // 如前所述    // 将elementData中从index起的size-index个元素,依次拷贝到elementData中index+1起后续位置上    // 简而言之,就是从index位起,整体后移1位    System.arraycopy(elementData, index, elementData, index + 1,                     size - index);    // 复制到目标位置上    elementData[index] = element;    size++;}
复制代码

删除元素

删除确定元素(删除最先加入的那个元素,如果存在的话)

public boolean remove(Object o) {    if (o == null) {// 为什么要做这个判断?为避免NullPointer        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;    // 大于0说明:所删除的不是最后一项    // 因为其最多等于0,且为0时index为最后一项,即size - 1 == index.    if (numMoved > 0)// 从index+1项起,整体前移1位        System.arraycopy(elementData, index+1, elementData, index, numMoved);    elementData[--size] = null; //注意:此处置空的是最后一位。}
复制代码

删除指定下标的元素

public E remove(int index) {    rangeCheck(index);//不要超过size    modCount++;    E oldValue = elementData(index);//先取出元素。为负数,如何处理?    int numMoved = size - index - 1;//计算其位置    if (numMoved > 0)         // 同前述        System.arraycopy(elementData, index+1, elementData, index, numMoved);    elementData[--size] = null; // 同前述    return oldValue;//返回所删除的元素}
复制代码

批量删除元素。这两个函数的唯一差别在于传给batchRemove()的第二个参数,前者为 false,后者为 true。它们之间的差距,我们可以通过后续源码进行分析。

public boolean removeAll(Collection<?> c) {    Objects.requireNonNull(c);// 处理为null情况    return batchRemove(c, false);}public boolean retainAll(Collection<?> c) {    Objects.requireNonNull(c);// 处理为null情况    return batchRemove(c, true);}
复制代码

批量处理删除

private boolean batchRemove(Collection<?> c, boolean complement) {    final Object[] elementData = this.elementData;// 指向当前list元素数组    int r = 0, w = 0;    boolean modified = false;    try {        for (; r < size; r++)            if (c.contains(elementData[r]) == complement)                elementData[w++] = elementData[r];        // 体现差距的地方,就在这里:对于elementData中的每个元素,        // complement为true:c中存在,则将其移动到最前端;c中不存在,略过。        //          为false:c中存在,略过;c中不存在,保留。    } finally {        // r未达到size,说明中途遇到错误        if (r != size) {            // 将r到size的元素,保存到w后面            System.arraycopy(elementData, r,                             elementData, w,                             size - r);            w += size - r;        }        // w未达到size,说明需要删除某些元素;==size说明,全部保留,不作处理。        if (w != size) {            // 从w位开始,到size-1,全部置为空            for (int i = w; i < size; i++)                elementData[i] = null;            modCount += size - w;            size = w;            modified = true;        }    }    return modified;}
复制代码

清空列表

public void clear() {     modCount++;
for (int i = 0; i < size; i++) elementData[i] = null;// 全部置空 size = 0; }
复制代码

查询

访问非常便捷。

public E get(int index) {    rangeCheck(index);    return elementData(index);}E elementData(int index) {    return (E) elementData[index];}
复制代码

修改

修改同样非常便捷。

public E set(int index, E element) {    rangeCheck(index);    E oldValue = elementData(index);    elementData[index] = element;//更新    return oldValue;//返回之前的值}
复制代码

关键的一些操作,感觉已经摸得差不多了。其它的一些查询、更新,都比较简单。


发布于: 2020 年 12 月 31 日阅读数: 22
用户头像

肥鱼先生

关注

码狗向前冲冲冲 2018.06.21 加入

定期分享 JAVA、Go 相关原创干货,涉及 Spring、Redis、Linux、Kubernetes 等技术领域。

评论

发布
暂无评论
ArrayList源代码分析