Yuasin

Yuasin

关注
发信
关注(28)粉丝(399)

ArrayList源码剖析与代码实测

ArrayList源码剖析与代码实测（基于OpenJdk14）

  • 写本篇博客的目的在于让自己能够更加了解Java的容器与实现，能够掌握源代码的一些实现与思想，选择从ArrayList入手是因为ArrayList相对来说是实现较为简单的容器，底层实现依赖与数组，将ArrayList整理清楚便于之后理解实现更复杂的容器和线程安全容器
  • 不同JDK的源码实现会有区别，本篇博客基于OpenJdk14进行源码分析
  • 本篇博客除了剖析源码以外还将讨论Java中的fail-fast机制

继承关系

ArrayList源码剖析与代码实测-LMLPHP
  • ArrayList实现List接口，而继承的AbstractList类也实现了List接口，为什么要实现两次List接口呢？详见：https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete
  • List接口定义了方法，但不进行实现（JDK1.8后接口可以实现default方法，List类中就有体现），我们要实现自己特定的列表时，不需要通过实现List接口去重写所有方法，AbstractList抽象类替我们实现了很多通用的方法，我们只要继承AbstractList并根据需求修改部分即可

从构造函数开始

  • 使用一个容器当然要从容器的构造开始，ArrayList重载了三种构造函数

  • 日常中最常使用的是无参数构造函数，使用另一个ArrayList来构造新的ArrayList在诸如回溯算法中也很常见。

    public ArrayList()
public ArrayList(int initialCapacity)
public ArrayList(Collection<? extends E> c)

  • 无参构造函数中将elementData 赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA（即空数组），其中elementData就是ArrayList存放元素的真实位置。也可以在初始化时将容器容量确定为传入的int参数。

//类中定义的变量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access，如果是私有变量，在内部类中获取会比较麻烦

//无参构造
public ArrayList() {
  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);
  }
}
  • 如果使用已有容器来构造ArrayList，则新的容器必须实现Collection接口，且其中的泛型 ? 需要是ArrayList泛型参数E的子类（或相同）。由于每个容器的toArray()方法实现可能不同，返回值不一定为Object[]，即elementData的类型会发生变化（例子见ClassTypeTest.java）。所以需要进行类型判断，若elementData.getClass() != Object[].class则使用Arrays工具类中的copyOf方法将elementData的类型改回。
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

//ClassTypeTest.java
public class ClassTypeTest {
    public class Person{ }
    public class Student extends Person{ }
    public static void main(String[] args) {
        Person[] p = new Student[5];
        System.out.println(p.getClass());
    }
}
//output:
//class [LClassTypeTest$Student;

从add方法深入 / 数组的扩容

  • 容器的本质无非是替我们保管一些我们需要储存的数据（基本数据类型、对象），我们可以往容器里加入，也可以从容器里获取，也可以删除容器内元素。使用容器而不是数组是因为数组对于我们使用来说过于不便利

    • 无法动态改变数组大小
    • 数组元素删除和插入需要移动整个数组

  • ArrayList容器底层是基于数组实现，但是我们使用的时候却不需要关心数组越界的问题，是因为ArrayList实现了数组的动态扩容，从add方法出发查看ArrayList是怎么实现的

ArrayList源码剖析与代码实测-LMLPHP

  • 可以看到add方法的调用链如上，ArrayList提供了两个add方法，可以直接往列表尾部添加，或者是在指定位置添加。elementData数组扩容操作开始于 add方法，当grow()返回扩容后的数组，add方法在这个数组上进行添加（插入）操作。在add方法中看到的modCount变量涉及 Java 的 fail-fast 机制，将在本文后面进行讲解
//size是ArrayList实际添加的元素的数量，elementData.length为ArrayList能最多容纳多少元素的容量
//通过代码可以看出，当size==elementData.length时，容器无法再放入元素，所以此时需要一个新的、更大的elementData数组
private int size;

public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
  • 当扩容发生时，要求容器需要至少能多放置 minCapacity 个元素（即容量比原来至少大minCapacity）
private static final int DEFAULT_CAPACITY = 10;

private Object[] grow() {
  return grow(size + 1);
}
private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
        		// 当oldCapacity==0 || elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时进入该分支
          	// 即容器使用无参构造函数 或 new ArrayList(0)等情况时进入
          	// elementData数组大小被扩容为 10
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
  • 通常情况下prefGrowth=oldCapacity/2，由此处可看出大部分情况下扩容后的数组大小为原数组的1.5倍
    • 扩容后的数组大小为原来的1.5倍，可能存在越界情况，此处使用 newLength - MAX_ARRAY_LENGTH <= 0 进行判断，不能使用 newLength <= MAX_ARRAY_LENGTH 进行判断，如果 newLength 超过 2147483647 ，会溢出为负值，此时newLength依旧小于MAX_ARRAY_LENGTH。而用newLength - MAX_ARRAY_LENGTH <= 0 则是相当于将newLength这个数字在“int环”上向左移动了MAX_ARRAY_LENGTH位，若这个数字此时为负数（即落在绿色区域），则直接返回当前newLength，否则进入hugeLength方法。
    • ArrayList源码剖析与代码实测-LMLPHP
    • 在hugeLength中，当老容量已经达到 2147483647 时，需求的最小新容量加一则溢出，此时抛出异常
public static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
  // assert oldLength >= 0
  // assert minGrowth > 0

  int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
  //!!! 判断数组大小是否超过int值允许的大小
  if (newLength - MAX_ARRAY_LENGTH <= 0) {
    return newLength;
  }
  return hugeLength(oldLength, minGrowth);
}

private static int hugeLength(int oldLength, int minGrowth) {
  int minLength = oldLength + minGrowth;
  if (minLength < 0) { // overflow
    throw new OutOfMemoryError("Required array length too large");
  }
  if (minLength <= MAX_ARRAY_LENGTH) {
    return MAX_ARRAY_LENGTH;
  }
  return Integer.MAX_VALUE;
}
  • 除了add方法，还有public boolean addAll(Collection<? extends E> c)方法以及它的重载public boolean addAll(int index, Collection<? extends E> c)方法

其他的删查改方法

  • 因为是基于数组的容器，其他一些删查改的方法都比较简单，基本上就是在数组上操作，此处就不一一展开
//删除元素：
public E remove(int index)
public boolean remove(Object o)
public boolean removeAll(Collection<?> c)
boolean removeIf(Predicate<? super E> filter, int i, final int end)
public void clear()

//修改元素：
public E set(int index, E element)
public void replaceAll(UnaryOperator<E> operator)

//查询/获得元素：
public E get(int index)
public int indexOf(Object o)
public List<E> subList(int fromIndex, int toIndex)

modCount与fail-fast机制

根据官方文档的描述，ArrayList是一个非线程安全的容器，两个线程可以同时对一个ArrayList进行读、写操作。通常来说对封装了ArrayList的类进行了同步操作后就能确保线程安全。

当然，ArrayList实现中也通过fail-fast确保了不正确的多线程操作会尽快的抛出错误，防止Bug隐藏在程序中直到未来的某一天被发现。

  • fail-fast机制的实现依赖变量 modCount，该变量在ArrayList执行结构性的修改（structural modification）时会 +1，如add、remove、clear等改变容器size的方法，而在set方法中不自增变量（但令人迷惑的是replaceAll和sort方法却会修改modCount的值，总结来说不应该依赖modCount实现的fail-fast机制）
//java.util.AbstractList.java
protected transient int modCount = 0;
  • equals方法就使用到了fail-fast，将modCount赋值给一个expectedModCount变量，在对两个容器内的元素一一进行完比较判断后得出两个对象是否相等的判断，但在返回判断之前要问一个问题，在对比判断的过程中当前这个ArrayList(this)有没有被其他人（线程）动过？所以加了一个checkForComodification方法进行判断，如果modCount与原先不同则代表该ArrayList经过改动，则equals的判断结果并不可信，抛出throw new ConcurrentModificationException()异常
//java.util.ArrayList.java
public boolean equals(Object o) {
        if (o == this) {
            return true;
        }

        if (!(o instanceof List)) {
            return false;
        }

        final int expectedModCount = modCount;
        // ArrayList can be subclassed and given arbitrary behavior, but we can
        // still deal with the common case where o is ArrayList precisely
        boolean equal = (o.getClass() == ArrayList.class)
            ? equalsArrayList((ArrayList<?>) o)
            : equalsRange((List<?>) o, 0, size);

        checkForComodification(expectedModCount);
        return equal;
}

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

我使用代码模拟了在使用迭代器的情况下throw new ConcurrentModificationException()的抛出

public class failFastTest_02 {

    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        List<Integer> list = new ArrayList<>();
        int changeIndex = 5;
        for(int i=0;i<10;i++){
            list.add(i);
        }

        Iterator iterator = list.iterator();

        //反射获取expectedModCount
        Field field = iterator.getClass().getDeclaredField("expectedModCount");
        field.setAccessible(true);

        //反射获取modCount
        Class<?> l = list.getClass();
        l = l.getSuperclass();
        Field fieldList = l.getDeclaredField("modCount");
        fieldList.setAccessible(true);

        while(iterator.hasNext()){
            if(changeIndex==0){
                list.add(-42);
            }
            System.out.println("Value of expectedModCount:" + field.get(iterator));
            System.out.println("Value of modCount:" + fieldList.get(list));
            System.out.println("iterator get element in list  "+ iterator.next());
            changeIndex--;
        }
    }
}

getClass()方法来获取类的定义信息,通过定义信息再调用getFields()方法来获取类的所有公共属性,或者调用getDeclaredFields()方法来获取类的所有属性,包括公共,保护,私有,默认的方法。但是这里有一点要注意的是这个方法只能获取当前类里面显示定义的属性,不能获取到父类或者父类的父类及更高层次的属性的。使用Class.getSuperClass()获取父类后再获取父类的属性。

  • 可以看到，在迭代器初始化后，迭代器中的expectedModCount不会因为ArrayList方法对列表的修改而改变，在这之后对于该列表（ArrayList）的结构性修改都会导致异常的抛出，这确保了迭代器不会出错（迭代器使用 cursor维护状态，当外界的结构变化时 size改变，不使用fail-fast public boolean hasNext() {return cursor != size;}可能会产生错误结果），如果想在使用迭代器时修改列表，应该使用迭代器自带的方法。上述代码报错如下。
ArrayList源码剖析与代码实测-LMLPHP
  • 插一句题外话， cursor顾名思义跟光标一样，读取一个元素后要将光标向后移动一格，删除一个元素则是将光标前的一个元素删除，此时光标随之退后一格。当然，ArrayList迭代器不能一直退格（remove），必须要先能读取一个元素然后才能将其删除

总结

  • ArrayList底层基于数组实现，元素存放在elementData数组中，使用无参构造函数时，加入第一个元素后elementData数组大小为10。
  • new ArrayList<>().size()为列表储存真实元素个数，不为列表容量
  • 正常情况下每次扩容后，容量为原先的1.5倍
  • ArrayList中还有内部类Itr、ListItr、SubList、ArrayListSpliterator，其中Itr、ListItr为迭代器，SubList是一个很神奇的实现，方便某些ArrayList方法的使用，对于SubList的非结构性修改会映射到ArrayList上。关于这几个内部类的内容，或许之后还会在该博客内继续更新

参考

fail-fast相关：https://www.cnblogs.com/goody9807/p/6432904.html

​https://baijiahao.baidu.com/s?id=1638201147057831295&wfr=spider&for=pc

内部类访问外部类私有变量：https://blog.csdn.net/qq_33330687/article/details/77915345

09-10 16:17
Powered by LMLPHP ©2024 Yuasin 0.057578