Java基础 ArrayList源码分析 JDK1.8

时间：2023-03-09 17:51:59
Java基础 ArrayList源码分析 JDK1.8

一、概述

　　本篇文章记录通过阅读JDK1.8 ArrayList源码，结合自身理解分析其实现原理。

　　ArrayList容器类的使用频率十分频繁，它具有以下特性:

  • 其本质是一个数组，因此它是有序集合
  • 通过 get(int i) 下标获取数组的指定元素时，时间复杂度是O(1)
  • 通过 add(E e)插入元素时，可直接向当前数组最后一个位置插入(这个描述不是特别准确，其中涉及到扩容、后续将讲解)，其时间复杂度为O(1)
  • 通过 add(int i, E e)向指定位置插入元素时，是在原数组的基础上通过拷贝和偏移量实现，其时间复杂度为O(n)
  • 通过 remove(int i) 删除指定位置的元素时，同样也是在原数组的基础上通过拷贝和偏移量实现，其时间复杂度为O(n)
  • 使用内部类Itr()迭代删除ArrayList删除元素时，需使用迭代器的remove()方法，不能使用ArrayList.remove(Object o)方法
  • ArrayList是非线程安全的，可能造成数据丢失，数组越界的问题

二、源码分析

1.重要属性
 

private static final int DEFAULT_CAPACITY = 10;　　//  扩容因子默认为10

transient Object[] elementData;　　　　　　　　　　　 //　元素数据

private int size;　　　　　　　　　　　　　　　　　　　　//  当前ArrayList中实际元素数量

protected transient int modCount = 0;　　　　　　　　//  ArrayList被修改的次数，这个属性是从java.util.AbstractList继承下来的

　　

2.重要操作

　　构造器

/*

 * 无参构造器 将elementData初始化为一个空的数组

*/

public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

/*

 * int整形构造器，将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);

    }

 }

　　boolean add(E e)　　添加一个元素

将添加数组分解成以下5个步骤

//  添加一个元素时 必须确保当前数组可以添加一个新的元素，因此会根据capacity去计算

public boolean add(E e) {

    ensureCapacityInternal(size + 1);

    // ⑤ 将新元素添加到 扩容之后的数组size++坐标上，(注意是size++，先赋值再自增size)

    elementData[size++] = e;

    return true;

}

private void ensureCapacityInternal(int minCapacity) {

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

// ① 计算容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {

    /* 如果初始化ArrayList时 是使用无参构造 new ArrayList()
       那么第一次向ArrayList添加元素时会将容量设为DEFAULT_CAPACITY 10个*/

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

        return Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    return minCapacity;

}

// ② 确认是否扩容

private void ensureExplicitCapacity(int minCapacity) {

    // ArrayList被修改次数 + 1

    modCount++;

    /* 
       如果计算出来的容量 > elementData数组的长度时，那么会要扩容

       因为elementData数组放不下新元素了；
       否则的话就不需要扩容
    */

    if (minCapacity - elementData.length > 0)

        grow(minCapacity);

}

// ③ 扩容

private void grow(int minCapacity) {

    // 新数组容量 = 老数组容量 * 1.5

    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    /*  但是必须要要保证 新容量 > ①中【计算出来的容量】 ，否则依然放不下新元素

        如果出现这种情况，那么使用①中【计算出的容量】最为新数组容量，保证能放下元素  */

    if (newCapacity - minCapacity < 0)

        newCapacity = minCapacity;

    //    数组元素过多 使用Integer.MAX_VALUE 作为容量

    if (newCapacity - MAX_ARRAY_SIZE > 0)

        newCapacity = hugeCapacity(minCapacity);

    // ④ 通过拷贝的方式扩容 调用native层方法

    elementData = Arrays.copyOf(elementData, newCapacity);

}

　　举个例子

// 往ArrayList中插入11个元素

List<Object> list = new ArrayList<>();

for (int i = 0; i < 11; i++) {

    list.add(new Object());

}

上述代码很简单，步骤为：

  1. 调用无参构造器，初始化一个ArrayList
  2. 循环向该ArrayList插入11个元素

以该步骤为例：

　　List<Object> list = new ArrayList<>();　　// 　　初始化elementData为一个空数组{} ， elementData.length = 0

　　i = 0 时

　　list.add(new Object());

　　这个操作会经历上面代码片段的①②③④⑤步骤

  1. 在走步骤①时使用默认容量 10
  2. 走步骤②时  判断10 > elementData.length  因此使用10作为最小容量请求扩容
  3. 走步骤③时 elementData.length 扩大1.5倍后依然为0 因此使用10作为新容量
  4. 通过步骤④native层拷贝方法进行数组拷贝
  5. 通过步骤⑤在新数组的size++ (即第个0个坐标上)，并且size自增为1

Java基础 ArrayList源码分析 JDK1.8

　　当 1 ≤ i ≤ 9时

　　list.add(new Object());

　　在步骤①算计容量时，minCapacity依次计算出来为 1, 2, 3, 4, 5, 6, 7, 8, 9 都小于elementData.length(当前经历了第一次扩容 为10) ，因此不会考虑扩容，直接将新增元素放到指定的下标中

　　ps: 此步骤modCount每次都会+1

　　当 i = 9时， 数组被填充满

Java基础 ArrayList源码分析 JDK1.8

　　当 i = 10 时

　　list.add(new Object());

　　此时就不能将第11个元素放到数组中了，需要第二次扩容

  1. 执行代码片段步骤①，算出minCapacity=11
  2. 步骤②判断出minCapacity(11) > elementData.length(10)，因此需要扩容
  3. 步骤③，通过在elementData.length基础上扩大1.5倍 即 15， 同时大于 minCapacity， 因此使用15作为新容量
  4. 步骤④，以15作为新数组容量，拷贝原数组到新数组中
  5. 步骤⑤，将新的元素放到扩容之后新数组下标10的位置中，并且size自增

Java基础 ArrayList源码分析 JDK1.8

　　

可以看到，上述操作过程中list经历了两次扩容，因此在使用ArrayList的时候可以考虑使用有参构造器，确认ArrayList的大小，防止扩容发生，影响效率

　　　　add(int i, E e)　　向指定位置添加一个元素

public void add(int index, E element) {

    //    检查下标是否越界

    rangeCheckForAdd(index);

    //    计算容量 考虑是否扩容

    ensureCapacityInternal(size + 1);

    //    通过拷贝数组的方式插入

    System.arraycopy(elementData, index, elementData, index + 1,

                     size - index);

    elementData[index] = element;

    size++;

}

private void rangeCheckForAdd(int index) {

    if (index > size || index < 0)

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

可以看到向指定位置插入元素和add(E e)方法步骤差不多，只是拷贝方式做了改变

　　1. 不发生扩容时插入过程

Java基础 ArrayList源码分析 JDK1.8

　　2. 发生扩容时插入过程

Java基础 ArrayList源码分析 JDK1.8

　　　　

　　　　E remove(int index)　　根据下标删除元素

public E remove(int index) {

    //    检查索引是否越界

    rangeCheck(index);

    //    修改次数 +1

    modCount++;

    //    取出需要删除的元素

    E oldValue = elementData(index);

    //    判断如果是删除中间的元素，则先自身向前拷贝的再删除；如果删除最后一个元素，则直接删除

    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    //    删除最后一个元素

    elementData[--size] = null; // clear to let GC do its work

    //    返回被删除的元素

    return oldValue;

}

Java基础 ArrayList源码分析 JDK1.8

删除元素时，是没有缩容操作的，例如一个ArrayList中elementData仅有10个元素并且存满了，remove掉9个元素后，size大小是1，但是elementData.length依旧为10

　　　

　　　　void trimToSize()　　修整大小

//    这个方法可以以当前elementData数组的size实际大小 重新拷贝出一个数组

//    防止上面问题的发生

public void trimToSize() {

    modCount++;

    if (size < elementData.length) {

        elementData = (size == 0)

          ? EMPTY_ELEMENTDATA

          : Arrays.copyOf(elementData, size);

    }

}

　　　　E get(int index)　　从指定索引获取元素

//    获取指定元素

public E get(int index) {

    rangeCheck(index);

    return elementData(index);

}

E elementData(int index) {

    return (E) elementData[index];

}

　　　　这个方法很简单，检查完索引范围，直接从elementData数组上去取对应位置的元素

　　　　boolean contains(Object o)　　查询ArrayList中是否包含某个元素

public boolean contains(Object o) {

    return indexOf(o) >= 0;

}

//    遍历elementData数组 查询满足条件的下标

public int indexOf(Object o) {

    if (o == null) {

        for (int i = 0; i < size; i++)

            if (elementData[i]==null)

                return i;

    } else {

        for (int i = 0; i < size; i++)

            if (o.equals(elementData[i]))

                return i;

    }

    return -1;

}

可以看到查询ArrayList中是否包含某个元素时，是通过遍历整个数组，依次查询，因此该方法时间复杂度为O(n)

　　　　

　　　　Iterator<E> iterator()　　迭代

public Iterator<E> iterator() {

    return new Itr();

}

//    内部类 迭代器

private class Itr implements Iterator<E> {

    int cursor;       // 返回数据的游标

    int lastRet = -1; // index of last element returned; -1 if no such

    int expectedModCount = modCount;    //    迭代器期望的被修改的次数 与ArrayList.modCount相同，

    Itr() {}

    public boolean hasNext() {

        return cursor != size;

    }

    @SuppressWarnings("unchecked")

    public E next() {

        //    ①  expectedModCount != modCount 时抛出ConcurrentModificationException

        checkForComodification();

        int i = cursor;

        if (i >= size)

            throw new NoSuchElementException();

        Object[] elementData = ArrayList.this.elementData;

        if (i >= elementData.length)

            throw new ConcurrentModificationException();

        cursor = i + 1;

        return (E) elementData[lastRet = i];

    }

    //    通过迭代器进行删除，每删除一个元素时expectedModCount会被重新赋值

    public void remove() {

        if (lastRet < 0)

            throw new IllegalStateException();

        checkForComodification();

        try {

            ArrayList.this.remove(lastRet);

            cursor = lastRet;

            lastRet = -1;

            expectedModCount = modCount;

        } catch (IndexOutOfBoundsException ex) {

            throw new ConcurrentModificationException();

        }

    }

    @Override

    @SuppressWarnings("unchecked")

    public void forEachRemaining(Consumer<? super E> consumer) {

        Objects.requireNonNull(consumer);

        final int size = ArrayList.this.size;

        int i = cursor;

        if (i >= size) {

            return;

        }

        final Object[] elementData = ArrayList.this.elementData;

        if (i >= elementData.length) {

            throw new ConcurrentModificationException();

        }

        while (i != size && modCount == expectedModCount) {

            consumer.accept((E) elementData[i++]);

        }

        // update once at end of iteration to reduce heap write traffic

        cursor = i;

        lastRet = i - 1;

        checkForComodification();

    }

    final void checkForComodification() {

        if (modCount != expectedModCount)

            throw new ConcurrentModificationException();

    }

}

前文中多次提到ArrayList的属性modCount，内部类Itr中提供的remove方法，在删除元素成功后，会将expectedModCount进行更新，因此，通过迭代器迭代ArrayList时，不能使用ArrayList.remove(Object o)方法，如果直接使用ArrayList.remove(Object o)进行删除(这个方法会对modCount减1)，会导致迭代器进行下一次迭代时调用next()方法 检查到expectedModCount与modCount不同(上述代码①处)，抛出ConcurrentModificationException，下面的代码示例将展示正确与错误在迭代中删除元素的操作

//    正确操作

List<Integer> list = new ArrayList<>();

Iterator<Integer> iterator = list.iterator();

while (iterator.hasNext()) {

    iterator.next();    //    next()操作会更新游标cursor

    iterator.remove();

}

//    错误操作：将抛出ConcurrentModificationException

List<Integer> list = new ArrayList<>();

Iterator<Integer> iterator = list.iterator();

while (iterator.hasNext()) {

    Integer next = iterator.next();

    list.remove(next);

}

3.线程安全问题(非线程安全)

/*  size++非原子操作  elementData[size++] = e  等同于

  elementData[size] = e;

  size = size + 1  */

public boolean add(E e) {

    ensureCapacityInternal(size + 1);

    elementData[size++] = e;

    return true;

}

　　ArrayList是非线程安全的，原因是在add操作时，由于size++是非原子操作，多个线程去对同一ArrayList执行add(E e)方法时，会出现下面两种情况

　　1.情况1：当两个线程同时进入add()方法，读取到当前size为0，并都往0的下标存元素时，就会导致其中的一个值被覆盖掉的问题

　　2.情况2：假设当前ArrayList为elementData[10]，可存放10个元素，并且当前已经存了9个元素了，那么此时size=9

情况1
线程A 线程B
add(e1) add(e2)
读到size为0 读到size也为0
elementData[0] = e1  
  elementData[0] = e2
情况2
线程A 线程B
add(e1) add(e2)
读到size为9 不需要扩容 读到size为9 不需要扩容
elementData[9] = e1  

size=size+1//size = 10

  
 

elementData[10] = e2

// 由于没有扩容导致数组越界
... 抛出异常了

相关文章