源码解析 || ArrayList源码解析

2019-08-09 00:00:00 源码 解析
  • 前言

这篇文章的ArrayList源码是基jdk1.8版本的源码,如果与前后版本的实现细节出现不一致的地方请自己多加注意。先上一个它的结构图

《源码解析 || ArrayList源码解析》

ArrayList作为一个集合工具,对于我而言它值得我们注意的地方有:

  1. 参数的作用细节
  2. 扩容的细节
  3. 迭代的细节
  4. 特殊API的细节

那么我就由这四个细节对ArrayList进行分析。

 

  • ArrayList的参数细节

ArrayList参数其实并不是特别多,值得我们拿出来讲的那就更少了。下面我通过一张图的展示,同时列出一些值得我们谈一谈的参数:

《源码解析 || ArrayList源码解析》

  1. DEFAULT_CAPACITYMAX_ARRAY_SIZE   两个参数规定了ArrayList的默认长度和最大长度。但是,如果使用默认构造函数,在初始化ArrayList的时候,它的长度是0,只有第一次添加数据时,它才会扩容为10;
  2. EMPTY_ELEMENTDATADEFAULTCAPACITY_EMPTY_ELEMENTDATA 这两个参数的值都是Object空数组,至于为什么作者要写两个同样的变量,那当然是为了区分不同方法当中的语义,使源码更加易读,当然这对于我们来说可以往后再关注。
  3. size   ArrayList中的大小,注意这也可以指已存放的数据的个数,和下面elementData的长度也还有一定的区别。
  4.  elementData   Object数组,这个是整个ArrayList最核心的参数之一,ArrayList存放的数据都在这里,对ArrayList的增删改查都基于这个Object数组。同时,它是被transient关键字修饰的,这意味着ArrayList需要进行序列化的时候,会把它忽略。那么我们会有一个问题,elementData 里面的数据难道不用序列化了吗? 答案当然是需要的,但是它不是直接将一整个数组都序列化,而是通过方法writeObject(),把elementData 中有数据的位置序列化。通俗的话就是,它序列化elementData的前size个,而elementData的真实长度中,size后面的空间都认为是没有数据的,如果也将它序列化会造成一定的流量浪费,影响传输性能。
  5. modCount 这个参数不是在ArrayList中声明的,它是在父类AbstractList中声明的,它的作用是记录ArrayList的结构(增加或删除)改变次数,以此来配合迭代器进行安全检查,迭代器一旦发现modCount被修改了,则会抛出ConcurrentModificationException。
  •  扩容的细节

首先,为什么不讲增删改查直接谈扩容呢?因为ArrayList的查找和修改的实现细节其实和普通的数组操作一样,并没有什么特别的地方。而添加和删除涉及到数组的动态调整,也就是我现在写的扩容,其它的其实和普通的数组操作差不多。

那么,当ArrayList执行一次add()方法的时候,它会有什么样的操作呢?首先我们先来看一个图。这是一个方法嵌套,执行到最后,就能确保list的空间是安全的。

《源码解析 || ArrayList源码解析》

上面是执行add方法后的一系列调用流程。可以看出方法内在调用完ensureCapacityInternal()后,空间是能确保数据的填充的。而往下调用的方法中,我们只关注grow()方法就行,这是个扩容方法,具体的代码和意图如下所示。

 1    /**
 2      * Increases the capacity to ensure that it can hold at least the
 3      * number of elements specified by the minimum capacity argument.
 4      *
 5      * @param minCapacity the desired minimum capacity
 6      */
 7     private void grow(int minCapacity) {
 8         int oldCapacity = elementData.length;
 9         //新容量暂时为旧容量的1.5倍
10         int newCapacity = oldCapacity + (oldCapacity >> 1);
11         //这一步是确保扩容的时候,扩容的空间尽量合理,避免频繁扩容
12         if (newCapacity - minCapacity < 0)
13             newCapacity = minCapacity;
14         //假设参数大于MAX_VALUE,设定最大容量为Integer.MAX_VALUE
15         if (newCapacity - MAX_ARRAY_SIZE > 0)
16             newCapacity = hugeCapacity(minCapacity);
17         //调用数组工具把数据覆盖并开辟内存空间
18         elementData = Arrays.copyOf(elementData, newCapacity);
19     }
  • 迭代的细节

ArrayList的迭代器采用的是fast-fail方式,也就是我们的快速失败方式。这是什么意思呢?我们直接贴出源码的注释来解释。

创建迭代器之后,除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

那么 ,iterator通过什么方式判断列表被修改了呢?答案是在ArrayList内部还有一个内部 Iterator的实现类,里面有一个参数expectedModCount,这个值与modCount 比较,若两个值不相等,则抛出异常。

1  //源码方法
2 final void checkForComodification() {
3             if (modCount != expectedModCount)
4                 throw new ConcurrentModificationException();
5         }

注意!我所说的迭代要注意的细节,指的是在循环过程中,伴随着ArrayList结构上的修改,例如添加或删除如果只是简单的循环遍历输出,其实各种方法没有太大的区别。

下面例举集中常见的错误使用方式:

这种情况通常是迭代用迭代器,而对于修改则是用ArrayList的方法引起的,要解决这个问题只需要利用iterator的remove()方法即可。

 1  ArrayList<Integer> list = new ArrayList<>(3);
 2         list.add(111);
 3         list.add(222);
 4         list.add(333);
 5 
 6         Iterator<Integer> iterator = list.iterator();
 7         while(iterator.hasNext()){
 8             Integer next = iterator.next();
 9             if (next.equals(111)){
10                 //错误的使用,在创建迭代器后使用list方法来remove,会抛出ConcurrentModificationException
11                 list.remove(new Integer(111));
12             }
13             System.out.println(next);
14         }
15     }

下面这种情况如果你只是想要找到一个目标值,同时将这个值删除并break退出是可以的。但是,如果你还要继续遍历下去,这种情况则会导致ArrayList集合遍历的不完整。

 1 ArrayList<Integer> list = new ArrayList<>(3);
 2         list.add(111);
 3         list.add(222);
 4         list.add(333);
 5         for (int i=0;i<list.size();i++){
 6             if (list.get(i).equals(222)){
 7                 //执行这一步,size的值为2,导致333这个值没有输出就结束循环。
 8                 list.remove(i);
 9                 continue;
10             }
11             System.out.println(list.get(i));  //输出结果:111
12         }
13 
14     }

 

一般来说,当我们迭代有对ArrayList进行remove的需求的时候,可以利用迭代器来遍历ArrayList的结构,这样比较安全规范的且不会产生错误。

 1 import java.util.ArrayList;
 2 import java.util.Iterator;
 3 
 4 public class ArrayListDemo {
 5     public static void main(String[] args) {
 6         ArrayList<Integer> list = new ArrayList<>();
 7         list.add(111);
 8         list.add(222);
 9         list.add(333);
10         Iterator<Integer> iterator = list.iterator();
11         while (iterator.hasNext()){
12             Integer next = iterator.next();
13             if(next.equals(222)){
14                 iterator.remove();
15                 continue;
16             }
17             System.out.println(next);
18         }
19     }
20 }
  • 特殊API的细节

  1. remove方法参数的不确定性。

就在我刚才的示例代码中就有一种隐藏的危险,当你的ArrayList存放的是Integer类型的时候,有一种场景下你需要移除一个值。你会理所当然的调用list.remove(222);这个方法来移除222这个值。但是,这个时候其实它是指移除索引位置在222上的值。这个时候就会有删除错误或者范围异常的发生。

1  Integer next = iterator.next();
2      if (next.equals(222)){
3                
4         list.remove(222);
5    }

   2. subList方法的实现及返回类型

下面先列出subList方法返回在SubList内部类的继承关系和构造方法。

 1  private class SubList extends AbstractList<E> implements RandomAccess {
 2         private final AbstractList<E> parent;
 3         private final int parentOffset;
 4         private final int offset;
 5         int size;
 6         
 7         SubList(AbstractList<E> parent,
 8                 int offset, int fromIndex, int toIndex) {
 9             this.parent = parent;
10             this.parentOffset = fromIndex;
11             this.offset = offset + fromIndex;
12             this.size = toIndex - fromIndex;
13             this.modCount = ArrayList.this.modCount;
14         }
15 }

ArrayList中有一个subList方法可以用于对ArrayList的切割。一般我们要用List接口来接收返回的集合,但是其实它返回的具体类型是一个内部类SubList。与ArrayList肯定不是同一个类型,因此,如果你把它强制转换为ArrayList则会发生错误。

1  public static void main(String[] args) {
2         ArrayList<Integer> list = new ArrayList<>(3);
3         list.add(111);
4         list.add(222);
5         list.add(333);
6         List<Integer> subList = list.subList(0, 1);
7         //编译不报错,运行时报错
8         ArrayList worngList = (ArrayList)subList;
9     }

同时,从构造函数可以看出。SubList类中的集合其实是从ArrayList中直接赋值来的,它只是通过修改边界范围和size来构成一个新集合。也就是说,实质上SubList和ArrayList用的是同一个elementData数组。因此,当对SubList进行增删改的时候,也会影响到ArrayList的存放的数据。示例代码如下:

1  public static void main(String[] args) {
2         ArrayList<Integer> list = new ArrayList<>(3);
3         list.add(111);
4         list.add(222);
5         list.add(333);
6         List<Integer> subList = list.subList(0, 1);
7         subList.add(444);
8         subList.add(555);
9     }

我们通过debug可以看到,当添加到444,555的时候,两个对象都出现了这两个数据。

《源码解析 || ArrayList源码解析》

 

相关文章