ArrayList源码思考

其实这篇内容原本记于11月初，放了好久了，最近整理下发出来吧。

这篇文章，大体上写的是源码的阅读，实际上与其他人写的思路是完全不同的。写这篇文章的目的并非让大家知道ArrayList是怎么实现的，而是找一些我不会的点。因此有些方法在ArrayList中可能是个核心的方法，但是我并不会详细写；有些可能是边边角角的东西，但是我会着重去说一下。

现在这个时间点（大概就是1个半月之后）重新看下来这篇文章，感觉写的并不好。

概观

继承与实现

ArrayList这个类继承了AbstractList抽象类，同时实现了List接口，其他就是一些标记接口什么的，如cloneable、Serializable、RandomAccess这些了。

除了这些之外还有间接实现的接口如Iterable这类，这类接口一般都是内部类实现的，实现了隐藏内部类的真实实现，只向外暴露接口的效果。

static全局共享的变量

  • default_capacity 很好理解，默认初始化值
  • empty_element data 注释翻译过来是：共享的空array实例，为空对象创建？

构造器

初始化构造器有三种方式

  • 无参数构造器——把static 的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给element data
  • int参数构造器——初始化的时候，指定一个值，指定ArrayList的size长度
  • Collection接口构造器——初始化的时候，给一个实现Collection接口的对象，这个类会被转为object[]类型的数组直接赋值给element data。如果这个对象是空的，那么跟第二个构造器是一样的。如果不为空，还会检查element data类型

内部方法

batchRemove(Collection<?> c, boolean complement)

这个方法内部实现了取交和取并两种操作，通过制定true和false来把控制需要的元素挪到前面，不需要的可能会被重置为null

void writeObject(java.io.ObjectOutputStream s)

序列化需要实现的method，不过这个东西没有写作接口？

内部类

Itr

在arraylist中有一个内部类，这个内部类实现了迭代器接口。即可以通过接口类型，获得内部类对象的引用。内部类是一个迭代器的实现。

在这个内部类中，有两个值，一个是 modCount另一个是expectedModCount，只有接口中的remove（）和初始化实例的时候才能让这两个值相同，也就是说在使用Iterator迭代的时候，只能通过remove来安全移除数据，且不报错。其他的方式都不行。

下面是内部类的一个工具方法，只要这两个值不同步，就会抛出异常。这个检查在next()和hasNext（）中都有

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

其中 remove（）是通过引用外部类直接修改的。而next（）方法每次执行都会获得整个object对象的引用，来获取下一个数据。获取的方式是通过迭代器的游标。在next（）中，还有一个游标lastRef，用来记录每次next的对象位置。所以remove（）的时候能够正确删除。

ListItr extends Itr implements ListIterator<E>

另一个list专用的迭代器。不怎么常用，（懒得看了）。

SubList extends AbstractList<E> implements RandomAccess

这个内部类主要的作用是为了给List<E> subList(int fromIndex, int toIndex)提供一个片段的预览。对返回的对象操作，会对应到原来的对象上面。

官网doc 给出了一个习惯的用法是list.subList(from, to).clear();这样，能够清空指定位置的元素。

这个内部类实现了大部分方法，甚至还实现了一个匿名的迭代器。

ArrayListSpliterator<E> implements Spliterator<E>

这个接口是一个为了实现并行的stream内部类。 暂时不看，很少用。

辅助工具

T requireNonNull(T obj)

public static <T> T requireNonNull(T obj) {
    if (obj == null)
        throw new NullPointerException();
    return obj;
}

Object对象提供的静态方法，用于检查对象值，是否为空，空的话抛出空指针

疑惑(有答案的)

RandomAccess用途

这是一个标记借口，从官方文档给的东西来看，仍然看不懂在做什么。猜测是这样的，底层虚拟机相关可能给这个接口的实现类做了一些优化，实现了这个借口的list对象，能够达到常数时间的随机访问效果。JVM有可能会给这里面的数组类型对象做一些优化。

又实现了一遍List接口

以ArrayList为例，为什么这个类extend 的AbstractList实现了list接口，还要自己再实现一遍list接口？

查了下，网上的解释是没啥用，主要是为了程序识别的，又实现了一下这个接口。场景是这样的：你想看这个类实现了什么接口，点击一下直接转调到接口定义。就是这个用途。stof1

抽象类为什么要实现某些方法，并抛出异常？

AbstractList这个抽象类为什么要实现某些方法，并抛出异常？

查了一下是这个样子的。如果你的 抽象类 提供了一个抽象方法，子类必须要重写，才能实现。但是有 方法 可以不需要重写，所以可以通过这种默认跑出异常的方式解决，反正你要想用这个方法就必须要重写，不写就抛异常，你也用不了。

疑惑（没答案）

  1. static 中empty_element data 到底有什么用？为什么还要拆出来一个DEFAULT CAPACITY_EMPTY_ELEMENT DATA另作他用？
  2. batchRemove(Collection<?> c, boolean complement)看不懂。为什么要判断r!=size?这个判断有什么意义？为什么这些循环要写到finally中？
  3. 为什么serialize序列化那个接口是标记接口，但是还需要某些实现类实现writeObjet() 、readObject()方法？为什么不把这几个方法写在接口里面。

感悟

  1. ArrayList对象本质就是做了一堆脏活累活，利用系统提供的最基础的数组类型的，在此基础上做了很多自动扩容、封装移动、数据检查等操作，同时还提供了便捷的操作方法。
  2. 某些方法尽可能的少用，因为这对一个List来说，操作成本还是比较高的。
  3. 看了下AbstractList这个抽象类，也就是ArrayList这个类的直接父类。这个父类里面有3个class文件，其中只有最核心的是public class，其他的都是包内 class，这两个class位置跟内部类有点像（再一个.java中的类），但是并没有写到public class内部，也就是说不是内部类。然后我看了一下，里面完全没有任何需要用到内部类特性的东西。——也就是说，如果需要构造一个类，这个类和用的位置没有关联，那么我写在一个文件中就可以了。如果这个类需要调用到内部的某些东西，才需要把这个类写成内部类，利用内部类的特性来实现功能。