2020-04-25

基础 / JavaSE

36 分钟读完 (大约 5333 个字) 0次访问

ArrayList源码分析

部分参考自:

https://www.cnblogs.com/aflyun/p/6444913.html

https://www.cnblogs.com/ysocean/p/8622264.html#_label0

概述

ArrayList底层是由数组实现的，是一个自动扩容的数组。(由于数组的长度是固定的，扩容时其实是进行数组复制)

1 2	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

ArrayList继承AbstractList类，实现了List接口, 所有有List的所有功能。
ArrayList实现了RandomAccess接口，支持随机访问，可以直接通过下标进行访问。
ArrayList实现了Cloneable接口，支持克隆。
ArrayList实现了Serializable接口，支持序列化功能。

数组复制

由于ArrayList底层是数组，所以会涉及到数组复制等操作，我们先来了解一下：

数组复制Arrays.copyOf

int[] oldArr = {1,2,3,4,5};
int[] ints = Arrays.copyOf(oldArr, 4);
System.out.println(Arrays.toString(ints));//[1, 2, 3, 4]
int[] ints1 = Arrays.copyOf(oldArr, 10);
System.out.println(Arrays.toString(ints1));//[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]

数组复制 System.arraycopy

/**
 * 参数1：源数组
 * 参数2：原数组的起始下标
 * 参数3：目标数组
 * 参数4：目标数组的起始下标
 * 参数5：复制的元素个数
 */
System.arraycopy(
    sourceArr, 
    0, 
    descArr, 
    0, 
    sourceArr.length < descArr.length ? sourceArr.length : descArr.length
);
System.out.println(Arrays.toString(sourceArr));//[1, 2, 3, 4]
System.out.println(Arrays.toString(descArr));//[1, 2, 3, 4, 55]

方法综述和源码分析

属性

/**
 * Default initial capacity.
 * 默认初始化容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 * 底层是基于数组实现的
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 共享的空数组实例，用于默认大小的空实例。
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * ArrayList的元素存储的数组。ArrayList集合的容量就是数组的长度，
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 * 任何空集合的数组如果等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当第一个元素添加时，
 * 将会被扩容至默认容量大小。
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * ArrayList的size，元素的个数
 */
private int size;

根据方法功能的不同，来进行分类。

构造方法

1
2
3

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

/**
 * 指定初始化集合数组大小来实例化集合。如果指定的大小是负数，则抛出IllegalArgumentException
 */
public ArrayList(int initialCapacity) {
    //指定大小大于0 ，就直接实例化。
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];//指定初始化容量
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;//空数组
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 * 构造一个初始化容量为10的空列表（注意：根据注释是10，但是源码其实是一个长度为0的空数组）
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 构造一个包含指定集合的List,将指定集合的数据全部添加到当前集合中。
 *      如果指定的集合为null,则会抛出NullPointerException（因为直接调用了c.toArray()）
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();//如果c为空，则会抛出空指针异常
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

注意：通过上面的elementData 属性注释，以及 ArrayList()构造方法和 add()方法可以知道:

在不指定容量的情况下，初始化的ArrayList的容量为0，在添加第一个元素的时候，容量才会扩充到默认大小10.
在指定容量的时候，是根据指定容量大小来实例化集合的，不会采用默认大小10.

Add Element

public E set(int index, E element) {}
public boolean add(E e) {}
public void add(int index, E element) {}
public boolean addAll(Collection<? extends E> c) {}   
public boolean addAll(int index, Collection<? extends E> c) {}

/**
 * 设置值，返回旧值
 */
public E set(int index, E element) {
    //下标检查
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

/**
 * 在列表最后添加元素,通过查看源码可以发现，ArrayList()初始化是，数组的大小是0，当我们
 *  添加第一个元素的时候，将大小扩充到了10.
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //这一个条件成立的情况只有初始化时未指定大小，并且是第一个次添加元素
    //即：ArrayList list = new ArrayList();
    // list.add(1); 能通过这个条件
    // list.add(2); 不能通过这个条件
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity); 1 ==> 10
    }
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    int capacity = calculateCapacity(elementData, minCapacity);//10
    ensureExplicitCapacity(capacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)//第一次之后，elementData.length,就是10
        grow(minCapacity);//10
}

private void grow(int minCapacity) {//
    // overflow-conscious code
    int oldCapacity = elementData.length;//
    int newCapacity = oldCapacity + (oldCapacity >> 1);//  按照1.5倍的方法进行扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

//数组的最大容量不会超过MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}


/**
 * 将指定元素插入指定位置，将原有元素及其右边的元素均向后移动一个（下标加1）
 */
public void add(int index, E element) {
    //检查下标是否合法，否则抛出IndexOutOfBoundsException
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

/**
 * 将指定元素插入指定位置，将原有元素及其右边的元素均向后移动一个（下标加1）
 */
public void add(int index, E element) {
    //检查下标是否合法，否则抛出IndexOutOfBoundsException
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

/**
 * 在末尾添加指定集合的所有元素
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);//使用数组复制。
    size += numNew;
    return numNew != 0;
}

/**
 * 从指定位置开始添加集合元素，如指定为止及其右边有元素，则全部向后移动
 */
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

对于 ArrayList 集合添加元素，我们总结一下：

　　①、当通过 ArrayList() 构造一个空集合，初始长度是为0的，第 1 次添加元素，会创建一个长度为10的数组，并将该元素赋值到数组的第一个位置。

　　②、第 2 次添加元素，集合不为空，而且由于集合的长度size+1是小于数组的长度10，所以直接添加元素到数组的第二个位置，不用扩容。

　　③、第 11 次添加元素，此时 size+1 = 11，而数组长度是10，这时候创建一个长度为10+10*0.5 = 15 的数组（扩容1.5倍），然后将原数组元素引用拷贝到新数组。并将第 11 次添加的元素赋值到新数组下标为10的位置。

　　④、第 Integer.MAX_VALUE - 8 = 2147483639，然后 2147483639%1.5=1431655759（这个数是要进行扩容）次添加元素，为了防止溢出，此时会直接创建一个 1431655759+1 大小的数组，这样一直，每次添加一个元素，都只扩大一个范围。

　　⑤、第 Integer.MAX_VALUE - 7 次添加元素时，创建一个大小为 Integer.MAX_VALUE 的数组，在进行元素添加。

　　⑥、第 Integer.MAX_VALUE + 1 次添加元素时，抛出 OutOfMemoryError 异常

　　注意：能向集合中添加 null 的，因为数组可以有 null 值存在。

为了测试上述的扩容方法是否为真，我们这里利用反射机制来查看ArrayList底层的数组的长度。

public class Test {
    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        /*
         * ArrayList 在没有指定容量的情况下初始化，只是初始化一个空的数组。
         * 当指定第一个add方法时，才会先将其容量扩容到10，其默认第一次初始化大小为10.
         */
        ArrayList<String> strList = new ArrayList<>();
        Class<ArrayList> aClass = ArrayList.class;
        Field elementData = aClass.getDeclaredField("elementData");
        elementData.setAccessible(true);
        Object[] o = (Object[]) elementData.get(strList);
        System.out.println(o.length);//0
        strList.add("A");
        o = (Object[]) elementData.get(strList);
        System.out.println(o.length);//10
        for (int i = 0; i < 10; i++) {
            strList.add(String.valueOf(i));
        }
        o = (Object[]) elementData.get(strList);
        System.out.println(o.length);//15
        for (int i = 0; i < 5; i++) {
            strList.add(String.valueOf(i));
        }
        o = (Object[]) elementData.get(strList);
        System.out.println(o.length);//22
        for (int i = 0; i < 7; i++) {
            strList.add(String.valueOf(i));
        }
        o = (Object[]) elementData.get(strList);
        System.out.println(o.length);//33
    }
}

打印结果如上述所示，按照1.5倍增长

1	0 => 10 => (10 + 10/2 = 15) => (15 + 15/2 = 22) => (22 + 22/2 = 33)

Remove Element

public E remove(int index) {}
public boolean remove(Object o) {}
public boolean removeAll(Collection<?> c) {}
public boolean retainAll(Collection<?> c) {}
public void clear() {}

通过 remove(Object) 方法可以看到，删除是进行了null 和 非null 的判断，所以：ArrayList是可以存储null 值的。

/**
 * 移除指定位置上的元素，在其右侧元素均向左移动一位（下标减1）
 */
public E remove(int index) {
    rangeCheck(index);

    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;
}

/**
 * 移除下标最小的所指定的元素，如果不存在，则不变.
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}


/**
 * 移除当前集合中存在于指定集合中的元素。
 */
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 *  保留当前集合中存在于指定集合中的元素。即：移除所有存在于指定集合中的元素。
 *      集合改变了则返回true，集合未改变则返回false.
 *  如果当前集合存在于指定集合类型不符时，会抛出ClassCastException.
 *  如果当前集合存在null值，但是指定集合不允许使用null时，则抛出NullPointerException.
 */
public boolean retainAll(Collection<?> c) {
    //确保c集合不为null，否则抛出NullPointerException
    Objects.requireNonNull(c);
    return batchRemove(c, true);//complement:补充
}

//批量移除
/**
 * 当 complement为true,  返回的是this集合中包含在指定集合c中的所有元素。
 * 当 complement为false, 返回的是this集合中不包含在指定集合c中的所有元素。
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)//如果c包含当前集合中的，
                elementData[w++] = elementData[r];//保留elementData中所有在集合c中的元素。
    } finally {
        if (r != size) {
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;//将后续的元素置为null
            modCount += size - w;// modCount = modCount + (size - w)
            size = w;
            modified = true;
        }
    }
    return modified;
}

/**
 * 清除所有元素
 */
public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

Get Element

1	public E get(int index) {}

/**
 * 查询指定下边的元素
 */
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

/**
 * 获取指定位置上的元素
 */
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

Search Element

1
2
3

public int indexOf(Object o) {}
public int lastIndexOf(Object o) {}
public boolean contains(Object o) {}

同样在查询的时候都进行了null 和 非null的区分。

/**
 * 判断是否包含某个元素
 */
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
 * 根据指定元素，返回第一次出现在这个列表中的下标，如果列表中不包含这个元素，则返回 -1
 * 如果元素为空，则返回第一个为null的元素的下标，如果不为空，则比较元素相同，返回第一个
 * 相同的下标，如果不存在，则返回-1
 */
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;
}

/**
 * 返回最后一个匹配的该元素的下表，元素可以为空，如果没有则返回-1
 */
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

To Array

1 2	public Object[] toArray() {} public <T> T[] toArray(T[] a) {}

/**
 * 这个方法将ArrayList中的数组复制一份，再返回。即：需要新分配一个数组。
 */
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

/**
 *  将集合中装换到指定数组中。如果给定的数组长度小于集合元素个数，则会新创建一个数组，并返回。
 *      如果给定的数组长度大于或等于集合元素个数，则直接复制进指定数组，并将剩余空间置为null.
 *  如果指定数组的运行时类型不是每个元素的运行时类型或父类型时，抛出ArrayStoreException
 *  如果指定数组为null,则会抛出NullPointerException.
 *
 *  @Test
 *  public void testToArray(){
 *      ArrayList<Integer> list = new ArrayList<>();
 *      list.add(1);
 *      list.add(2);
 *      list.add(3);
 *
 *      Integer [] arr = new Integer[4];
 *      Integer[] array = list.toArray(arr);
 *      System.out.println(arr == array);//true
 *
 *      Integer[] arr1 = new Integer[1];
 *      Integer[] array1 = list.toArray(arr1);
 *      System.out.println(arr1 == array1);//false
 *  }
 */
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;//将剩余位置置为null.
    return a;
}

Other

public int size() {}
public boolean isEmpty() {}
public Object clone() {}
public List<E> subList(int fromIndex, int toIndex) {}
public void forEach(Consumer<? super E> action) {}
public boolean removeIf(Predicate<? super E> filter) {}
public void replaceAll(UnaryOperator<E> operator) {}
public void sort(Comparator<? super E> c) {}

/**
 * 元素的个数
 */
public int size() {
    return size;
}

/**
 * 集合大小是0，返回true
 */
public boolean isEmpty() {
    return size == 0;
}

/**
 * ArrayList实例的浅拷贝
 */
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

/**
 * 使用subList(fromIndex,toIndex)，返回的是原来集合的一个视图，所以操作的其实是原集合。
 * Returns a view of the portion of this list between the specified
 * 注意：包括fromIndex,不包括toIndex.如果fromIndex和toIndex相等，则返回empty List。
 * 当我们需要在当前集合的某些范围内操作，就可以使用subList，例如：
 * list.subList(fromIndex,toIndex).clear().另外List中的方法同样适用于返回的subList,
 * 因为subList()返回的SubList集合继承自AbstractList.
 * 下标越界则抛IndexOutOfBoundsException,参数异常则抛IllegalArgumentException。
 */
public List<E> subList(int fromIndex, int toIndex) {
    //检查集合下标是否合法。
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

至于剩下的三个方法，我们通过测试案例来说明:

RemoveIf(Predicate) 如果满足则删除

@Test
public void testRemoveIf(){
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    list.removeIf(new Predicate<Integer>() {
        /**
             * test返回true，则去除，否则，保留
             * @param integer
             * @return
             */
        @Override
        public boolean test(Integer integer) {
            if (integer == 1){
                return true;
            }
            return false;
        }
    });
    System.out.println(list);//[2, 3]
}

replaceAll(UnaryOperator) 替换所有满足条件的

@Test
public void testReplaceAll(){
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    list.replaceAll(new UnaryOperator<Integer>() {
        @Override
        public Integer apply(Integer integer) {
            if (integer == 1){
                return 11;
            }
            return integer;
        }
    });

    System.out.println(list);//[11, 2, 3]
}

sort(Comparator) 排序

@Test
public void testSort(){
    ArrayList<Integer> list = new ArrayList<>();
    list.add(2);
    list.add(1);
    list.add(5);
    list.add(4);

    list.sort(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o1 < o2){
                return -1;//负数表示o1<o2, 正数表示o1>o2.
            }else if (o1 > o2){
                return 1;
            }
            return 0;
        }
    });
    System.out.println(list);
}

迭代器

// 创建Iterator
public ListIterator<E> listIterator(int index) {}
public ListIterator<E> listIterator() {}
public Iterator<E> iterator() {}

// 创建一个从指定下标开始到结尾的ListIterator.
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

//创建一个从开始到结尾的ListIterator.
public ListIterator<E> listIterator() {
    return new ListItr(0);
}

//创建一个Iterator
public Iterator<E> iterator() {
    return new Itr();
}

集合遍历

普通for循环遍历

@Test
public void testLoop(){
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        list.add(i);
    }

    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == 5){
            list.remove(i);
        }
    }
    System.out.println(list);//[0, 1, 2, 3, 4, 6, 7, 8, 9]
}

foreach 循环遍历

@Test
public void testForeach(){
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    for (Integer i : list) {
        if (i == 2){
            list.remove(i);
        }
    }
    System.out.println(list);
}
//以上代码会抛出 并发修改异常
/*
java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at com.ooyhao.list.ListTest.testForeach(ListTest.java:215)
*/

使用foreach去增加或删除元素时,会出现并发异常。我们先来看一下反编译的代码：

@Test
public void testForeach() {
    ArrayList<Integer> list = new ArrayList();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    Iterator var2 = list.iterator();

    while(var2.hasNext()) {
        Integer i = (Integer)var2.next();
        if (i == 2) {
            list.remove(i);
        }
    }

    System.out.println(list);
}

经过编译器编译之后的代码如上。

我们先看一下Iterator 类源码:

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        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];
    }

    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();
    }
}

并发修改异常

通过源码可以看到，方法next 和 remove 都有调用检查是否并发修改方法checkForComodification .再回来看下列代码：

Iterator var2 = list.iterator();
while(var2.hasNext()) {
    Integer i = (Integer)var2.next();
    if (i == 2) {
        list.remove(i);
    }
}

猜想分析：当i==2 时，调用remove方法可以正常删除，但是此时 list的modCount属性和迭代器expectedModCount的值不同了，下一次循环，调用var2.next() 方法时，会调用checkForComodification 方法，此时会抛出 ConcurrentModificationException异常。

验证：

此时可以看到，list中的元素正常删除了，我们在往下走一步。就报错了。所以，报错不是发生在执行list.remove(i) 时，而是下一次执行var2.next().

综合上述两个案例可以知道：增强For循环其实使用的就是Iterator迭代器。

如果使用普通For循环遍历 ,则只能使用list.remove()。
如果使用增加for循环遍历,则只能使用迭代器的remove 方法。

Iterator迭代器

迭代器源码上面已经看了，可以发现，Iterator迭代器除了hasNext() 和 next() 方法，用于操作的只有一个remove() 方法，所以这个迭代器只能用于remove，不能进行modify 和 add。

使用Iterator迭代器来遍历和删除：

@Test
public void testIterator(){
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    Iterator<Integer> iterator = list.iterator();
    while(iterator.hasNext()){
        Integer next = iterator.next();
        if (next == 2){
            iterator.remove();
        }
    }
    System.out.println(list);//[1, 3, 4]
}

ListIterator迭代器

我们先看一下ListIterator的源代码：

/**
 * An optimized version of AbstractList.ListItr
 */
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

我们通过源码可以看出：

具有hasPrevious() 和 previous() 两个方法，可以倒序遍历。
具有hasNext()和 next() 两个方法，可以顺序遍历。
具有nextIndex() 和 previousIndex() 两个方法，可以获取游标的上一个和下一个位置。
具有remove(),add(),set() 三个方法，可以实现增删改。

下面通过例子测试一下：

@Test
public void testListIterator(){
    ArrayList<Integer> list = new ArrayList<>();
    list.add(3);
    list.add(2);
    list.add(3);
    list.add(4);

    //遍历和删除
    ListIterator<Integer> listIterator = list.listIterator(1);
    while (listIterator.hasNext()){
        Integer next = listIterator.next();
        if (next == 3){
            listIterator.remove();
        }
    }
    System.out.println(list);//[3, 2, 4]
    //上述遍历，已经将游标移动到了最后，此时我们使用倒序遍历。
    while (listIterator.hasPrevious()){
        Integer previous = listIterator.previous();
        if (previous == 2){
            listIterator.add(22);
        }
        if (previous == 3){
            listIterator.set(303);
        }
    }
    System.out.println(list);//[303, 22, 2, 4]
}

总结

ArrayList 底层是数组实现的，非同步。即：线程不安全。
默认初始化容量为10，最大容量为 MAX_ARRAY_SIZE = INTEGER.MAX_VALUE - 8 .
1. 当使用无参构造进行实例化时，此时的容量为0，添加第一个元素是，容量为10.
2. 当指定容量时，使用实际指定的数值。
indexOf() 和 lastIndexOf 查找元素，区别null ,如查找元素不存在时，返回-1.
数组进行扩容时，会重新设置容量。newCapacity = oldCapacity + (oldCapacity >> 1) ,即：使用1.5倍进行扩容。
ArrayList的克隆函数，就是将数组复制一份。
从代码看，当ArrayList的容量不足的时候，每次增加元素，都是将原来的数据复制到一个新的数组中，非常消耗时间，所以，当我们在事先可以确定元素的个数的情况下使用ArrayList ,否则建议使用LinkedList.
ArrayList的实现中大量使用了 Arrays.copyof 和 System.arraycofy ，所以前面介绍了两个方法的使用。
ArrayList底层实现是使用的数组，所以在查询的时候支持随机访问，即：查询快，增删慢。而LinkedList底层实现是双向链表，不支持随机访问，仅能顺序访问。即：查询慢，增删快。所以我们在选择集合的时候，需要根据业务逻辑的不同来使用不同的集合。
在查询和删除的时候，都区分了null和非null两种情况，所以ArrayList中可以使用null.与LinkedList一样

本文标题：ArrayList源码分析
本文作者：ouYang
本文链接：https://ooyhao.github.io/2020/04/25/%E5%9F%BA%E7%A1%80/ArrayList/
发布时间：2020-04-25
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

# JavaSE

ArrayList源码分析

ArrayList源码分析

概述

数组复制

方法综述和源码分析

属性

构造方法

Add Element

Remove Element

Get Element

Search Element

To Array

Other

迭代器

集合遍历

普通for循环遍历

foreach 循环遍历

并发修改异常

Iterator迭代器

ListIterator迭代器

总结

评论

目录

链接

分类

标签云

最新文章

归档

标签

Your browser is out-of-date!