ArrayList源码深度剖析

,而链表是不可以随机访问的，比如说我们想通过下标访问链表当中的某个数据，需要从头结点或者尾节点开始遍历，直到遍历到下标对应的数据，比如下图中的单链表找到第3个数据，需要从头开始遍历，而这个时间复杂度为O(n)。,,如果上面程序当中的TestPerson没有implements Serializable，则上述代码会报异常java.io.NotSerializableException:。,集合的addAll方法实现如下：,在ArrayList当中主要有以下这些字段：,add方法，这个方法用于往容器的末尾增加数据，也是ArrayList当中最核心的方法。他的主要工作流程如下图所示：,,他首先调用函数ensureCapacityInternal确保ArrayList当中的数组长度能够满足需求，不然数组会报数组下标越界异常，add函数调用过程当中所涉及到的函数如下。,上述代码的调用流程如下：,,,set方法，这个方法主要是用于设置指定下标的数据，这个方法比较简单。,这个方法我们在前面已经提到过了，不知道大家有没有观察到他的访问修饰符是public，为什么要设置为public呢？这个意思很明显，我们可以在使用ArrayList的时候自己调用这个方法，防止当我们在往容器中加入数据的时候频繁因为数组长度不够重新申请内存，而原来的数组需要从新释放，这会给垃圾回收器造成压力。我们在ArrayList设计与实现，自己动手写ArrayList这篇文章当中写过一段测试程序去测试这个方法，感兴趣的同学可以去看看！！！,我们首先来看一下下面代码的输出：,执行上面一段代码我们可以在控制台看见对应的输出，我们知道最终打印在屏幕上的是一个字符串，那这个字符串怎么来的呢，我们打印的是一个对象，它是怎么得到字符串的呢？我们可以查看System.out.println的源代码：,从上述代码当中我们可以看见通过String s = String.valueOf(x);这行代码得到了一个字符串，然后进行打印，我们在进入String.valueOf方法看看是如何得到字符串的：,我们可以看到如果对象不为 null 最终是调用对象的toString方法得到的字符串。因此当打印一个对象的时候，最终会打印这个对象的toString方法返回的字符串。,toString方法没有直接在ArrayList当中实现，而是在它继承的类AbstractList当中实现的，toString的源代码如下所示：,上述代码的整个过程还是比较清晰的，大致过程如下：,我们可以发现最终append到StringBuilder当中的字符串仍然是ArrayList当中数据对象的toString方法返回的数据。,在ArrayList当中的equals方法和toString方法一样，equlas方法也是在类AbstractCollection当中实现的，其源代码如下：,上面代码的主要流程：,首先判断o和this是否是同一个对象，如果是则返回true，比如下面这种情况：,如果对象没有实现List接口返回false。,逐个判断链表里面的对象是否相等（调用链表当中存储的对象的equals方法），如果两个链表当中节点数目一样而且都相等则返回true否则返回false。,通过上面的分析我们可以发现ArrayList方法并没有让比较的对象是ArrayList对象，只需要实现List接口并且数据数目和内容都相同，这样equals方法返回的结果就是true，比如下面代码就验证的这个结果：,ArrayList的方法比较简单，就是拷贝了原ArrayList当中的数组中的数据。,整个拷贝过程如下如所示：,,虽然发生了数组的拷贝，但是拷贝之后的数组中数据的指向并没有发生变化，也就是说两个数组指向的内容是一样的，如果一个数组改变了所指向的数据，另外一个数组当中的数据也会发生变化。比如下面的代码：,我们在分析toString方法的时候，有下面这样一行代码：,然后不断通过迭代器的hasNext和next方法对数据进行迭代，比如下面这个例子：,Itr类是ArrayList的内部类，接下来我们仔细分析Itr类的实现。,在Itr类当中主要有一下几个字段：,我们现在来花点时间好好谈一下modCount（英文全称为：modifications count，修改次数）这个字段。当ArrayList当中发生一次结构修改(Structural modifications)时，modCount就++。所谓结构修改就是那些让ArrayList当中数组的数据个数size发生变化的操作，比如说add、remove方法，因为这两个方法一个是增加数据，一个是删除数据，都会导致容器当中数据个数发生变化。而set方法就不会是的modCount发生变化，因为没有改变容器当中数据的个数。,在初始化方法当中，没有任何操作也就印证了我们前面在分析字段的时候说的 cursor的初始化的值为0。,接下来分析迭代器当中比较重要的两个方法next和hasNext。,为什么要抛出ConcurrentModificationException异常呢，我们先想想是什么导致modCount发生变化。肯定迭代器在进行遍历的同时，修改了modCount的值，通常这种现象的发生出现在并发的情况下，因此抛出ConcurrentModificationException异常。像这种通过迭代器遍历过程进行检查并且当发生不符合条件的情况下抛出异常的现象就称作Fast-fail。,其实我们也可以在不使用并发的情况让迭代器抛出这个异常，我们只需要在迭代器迭代的时候我们对ArrayList进行add和remove操作即可。比如像下面这样就会抛出ConcurrentModificationException：,因为ArrayList是随机存取的，因此我们通过下标查找数据的时间复杂度是O(1)。,插入数据的时间复杂度是O(n)。,,还记的我们在ArrayList设计与实现，自己动手写ArrayList当中自己实现ArrayList使用的扩容机制吗？我们自己的扩容机制为扩容为原来长度的两倍，而ArrayList当中的扩容机制为扩容为原来的1.5倍。,,假设我们在使用ArrayList的时候没有指定初始化的时候数组的长度，也就是说初始长度为ArrayList的默认长度也就是10。那么当我们不停地往容器当中增加数据，扩容导致的数组长度的变化如上图所示，横轴表示扩容次数，纵轴表示数组长度，蓝色的扩容为原数组长度的1.5倍，另外一条是2倍。我们很清晰的发现扩容为原来的2倍在后期的数组长度将会远大于扩容1.5倍。这很可能会导致我们会浪费很大的数组空间，比如说刚好加入最后一个数据的时候导致ArrayList进行扩容操作，这可能是ArrayList在设计时候的考量。