住阳台的猫

V1

2022/04/20阅读:27主题:默认主题

Java集合-ArrayList源码学习

1. 继承与实现

public class ArrayList<Eextends AbstractList<E>
        implements List<E>, RandomAccessCloneablejava.io.Serializable 
{
    /* */
}

ArrayList实现了四个接口:List<E>, RandomAccess, Cloneable, java.io.Serializable

  • List<E>:List相关接口
  • List<RandomAccess>:支持快速随机访问
  • List<Cloneable>:支持对象克隆
  • List<Serializable>:支持序列化

ArrayList还继承了AbstractList,这个类中有一些List的公共方法

2. 字段

//默认的初始容量
private static final int DEFAULT_CAPACITY = 10;
//共享使用的空实例,这个空实例是没有容量的空实例 
private static final Object[] EMPTY_ELEMENTDATA = {};
//共享使用的空实例,这个空实例可被扩容到初始容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList中保存元素的缓冲数组,DEFAULTCAPACITY_EMPTY_ELEMENTDATA标识的空数组在第一个添加元素时会被扩容到10个大小。 
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList集合中包含的元素数量 
private int size;
//集合的容量最大值为Integer的最大值-8,一些虚拟机会在数组中保存一些头信息,这些信息是区别于使用者添加的元素之外的存在,如果最大为Integer的最大值,当头信息添加之后,再添加元素就有可能会造成内存溢出,这里减8只是为了兼容所有虚拟机,你要是非要添加元素也是可以加的
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

需要注意的点

  1. EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    1. 两个都是空数组,不同点在DEFAULTCAPACITY_EMPTY_ELEMENTDATA是可以扩容的,当有元素被添加到数组中时,DEFAULTCAPACITY_EMPTY_ELEMENTDATA会扩容到DEFAULT_CAPACITY定义的大小
    2. ArrayList初始化时可以选择传入初始大小,不传的话就会使用默认的DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    3. 数组扩容时,如果使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA容量会一次扩大10,使用的是EMPTY_ELEMENTDATA会扩大到原来的1.5倍
  2. elementData上加了transient,所以添加了writeObject和readObject方法,用来序列化和反序列化数组中的元素

3. 构造方法

/**
 * 构造一个空数组,容量为传入的值
 */

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

/**
 * 构造一个空数组,容量为10
 */

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 构造一个包含指定collection的元素的数组,元素的顺序是collection的迭代器返回的顺序
 */

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData 
= Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

实际使用过程中我们最常用的是无参的构造方法,但是如果可以预估出数组的大小,也可以传入一个预估的值,减少扩容的时间和内存消耗,具体参考添加元素

一个已被修复的bug

https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652

表现:Arrays.asList().toArray()返回的类型是不是Object[]

原因:Arrays的toArray方法返回的ArrayList是它的内部类Arrays.ArrayList,而List<> list = new ArrayList<>();返回的是java.util.ArrayList

4. 添加元素

添加元素的逻辑都一样,都是先判断剩余空间是否足够,不够的话进行扩容,再把元素添加进来

4.1. 在数组末尾添加元素

public boolean add(E e) {
    // 空间校验
    ensureCapacityInternal(size + 1);
    // 把要添加的元素加进来,放到size+1的位置,数组大小加一
    elementData[size++] = e;
 return true;
}

4.2. 在指定位置插入元素

public void add(int index, E element) {
    // 校验元素插入的位置
    rangeCheckForAdd(index);
    // 空间校验
    ensureCapacityInternal(size + 1);
    // 执行一个本地方法,System.arraycopy方法用于将指定位置及其后面的所有元素整个通过复制迁移到从index+1开始的位置,即整体后移一位,将index位空出来用于保存新元素。
    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));
}

4.3. 在数组末尾添加指定集合中的元素

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    // 空间校验
    ensureCapacityInternal(size + numNew);
    // 把a中从0开始的newNew个元素添加到elementData的size处
    System.arraycopy(a, 0, elementData, size, numNew);
    // 数组大小增加添加的元素个数
    size += numNew;
    return numNew != 0;
}

4.4. 在数组指定位置插入指定集合中的元素

public boolean addAll(int index, Collection<? extends E> c) {
    // 校验元素插入的位置
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    // 空间校验
    ensureCapacityInternal(size + numNew);
    // 原数组要移动的元素应该移动到的位置
    int numMoved = size - index;
    if (numMoved > 0)
        // 把elementData中从index(插入位置)开始的numNew个元素移动到新的位置,把空间腾出来
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
    // 把要插入的元素放进去
    System.arraycopy(a, 0, elementData, index, numNew);
    // 数组大小增加添加的元素个数
    size += numNew;
    return numNew != 0;
}

基本没有什么东西,都是判断空间,添加元素,在中间插入元素的挪一下位置,很简单,看一下扩容的部分

4.5. 底层扩容逻辑

// 确保能够添加元素校验入口,minCapacity:此次扩容最少需要的大小
private void ensureCapacityInternal(int minCapacity) {
    // 如果ArrayList是通过无参构造函数生成的,第一次添加元素的时候就会直接扩容到10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

// 校验剩余空间大小
private void ensureExplicitCapacity(int minCapacity) {
    // 数组大小有变化,先把modCount加一
    modCount++;
    // 需要的空间超过了现有的空间大小,扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 数组默认扩容一半大小
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩容一半还不够,直接扩容到需要的容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新的大小超过了上限
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 超出上限的处理
private static int hugeCapacity(int minCapacity) {
    // 太大了,直接溢出变负数了,救不了,直接抛异常
    if (minCapacity < 0// overflow
        throw new OutOfMemoryError();
    // 没溢出,但是已经超过默认设置的最大长度了,还要加,那我就不管了,直接把最大容量返给你,想加就加,不管了
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

5. 删除元素

删除元素和添加相比逻辑各不相同,主要还是看代码

5.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);
    // 删除之后数组的最后一位就不需要了,但是还存着值,会占用空间,设成null等着被回收就行
    elementData[--size] = null;
    return oldValue;
}

private void rangeCheck(int index) {
    // 数组就这么长,硬要删范围之外的东西,只能是给你报错了
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

5.2. 删除指定元素

public boolean remove(Object o) {
    // 如果要删除的是null,直接==就可以判断
    if (o == null) {
        // 遍历数组,遇到null就删除掉
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                // 内部使用的删除方法
                fastRemove(index);
                return true;
            }
    } else {
        // 遍历数组,因为要删除的不是null了,所以需要调用equals方法判断是不是相等
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                // 内部使用的删除方法
                fastRemove(index);
                return true;
            }
    }
    return false;
}

// 一个内部使用的删除方法,跳过了位置校验,因为在调用点就已经保证了删除的位置一定是在数组范围内的
private void fastRemove(int index) {
    modCount++;
    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
}

5.3. 清空元素

public void clear() {
    modCount++;
    // 遍历,全部清除
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    // 大小设为0
    size = 0;
}

5.4. 从当前数组中删除存在或不存在指定集合中的元素

// 从当前数组中删除所有存在于集合c中的元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

// 从当前数组中删除所有不存在于集合c中的元素
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

// 内部方法,批量删除,通过complement判断是删除c中存在的元素还是删除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++)
            // 如果集合c中是否包含当前元素和判断条件一致,放到elementData中
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 如果中途出现错误,导致没有遍历完,把剩余的元素都放在elementData最后面
        if (r != size) {
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        // 当elementData大小和原数组不同时,也就是数组中有元素被删除
        if (w != size) {
            // 当前大小为w,把w之后的空间释放
            for (int i = w; i < size; i++)
                elementData[i] = null;
            // 修改次数增加,值为删除的元素个数
            modCount += size - w;
            // 修改新的大小
            size = w;
            // 返回值修改
            modified = true;
        }
    }
    return modified;
}

5.5. 删除所有符合过滤器条件的元素

传入一个过滤器,把所有符合要求的元素都删除掉

public boolean removeIf(Predicate<? super E> filter) {
    // 参数校验
    Objects.requireNonNull(filter);
    // 记录被删除的元素个数
    int removeCount = 0;
    // 一个BitSet用来记录每个位置是否应该被删除,用BitSet节省空间
    final BitSet removeSet = new BitSet(size);
    // 记录ModCount,判断是否并发修改用
    final int expectedModCount = modCount;
    final int size = this.size;
    // BitSet初始化,遍历整个数组,把符合过滤器要求的索引在BitSet中设为true
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    // 校验并发修改
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    // 判断是否有元素被删除
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        // 遍历整个数组
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            // nextClearBit方法的作用是获取BitSet中下一个值为false的下标
            i = removeSet.nextClearBit(i);
            // 第i个元素是不需要删除的,把值赋给第j个元素,j从0开始递增
            elementData[j] = elementData[i];
        }
        // 不需要删除的元素都移到前面了,后面的就都可以清除掉了
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;
        }
        // 变更数组大小,并发修改校验,变更修改次数
        this.size = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
    return anyToRemove;
}

6. 修改元素

6.1. 修改指定位置的元素

public E set(int index, E element) {
    // 位置校验
    rangeCheck(index);
    E oldValue = elementData(index);
    // 直接把新元素放到对应位置上,很简单,没啥可说的
    elementData[index] = element;
    return oldValue;
}

6.2. 批量修改

传入一个操作,对所有元素进行处理

public void replaceAll(UnaryOperator<E> operator) {
    // 参数校验
    Objects.requireNonNull(operator);
    // 记录ModCount,判断是否并发修改用
    final int expectedModCount = modCount;
    final int size = this.size;
    // 遍历,处理每一个元素
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        elementData[i] = operator.apply((E) elementData[i]);
    }
    // 并发修改校验,修改次数增加
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

7. 获取元素

7.1. 获取指定位置的元素

对位置做一下校验,直接拎出来就行,很简单

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

7.2. 获取指定元素第一次/最后一次出现的位置

// 获取指定元素第一次出现的位置
public int indexOf(Object o) {
    // 如果要找的元素是null,只需要用==判断就行了
    if (o == null) {
        // 遍历
        for (int i = 0; i < size; i++)
            // 找到该元素,直接返回数组下标
            if (elementData[i]==null)
                return i;
    } else {
        // 要找的元素不是null,需要调用equals方法
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -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;
}

8. 遍历

8.1. iterator正向遍历

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E{
    /* */
}

Itr是ArrayList内部的一个实现类,和AbstractList中的Itr相比做了一些修改

8.1.1. AbstractList中的实现

private class Itr implements Iterator<E{
    // 后续调用next方法时会被返回的元素的索引
    int cursor = 0;
    // 上一个返回的元素的索引,调用了删除操作时没有返回,设为-1,默认没有返回也是-1
    int lastRet = -1;
    // 迭代器期望得到的modCount,如果出现了并发修改,最后就会不一致
    int expectedModCount = modCount;

    // 判断迭代器后续是否还有元素,当前索引到达数组长度时就没了
    public boolean hasNext() {
        return cursor != size();
    }

    // 获取下一个元素
    public E next() {
        // 并发校验
        checkForComodification();
        try {
            // 拿到当前索引,把元素取出来,修改lastRet的值,并把索引向后移一位,返回拿到的值
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            // 并发校验过了,还是没拿到数据,看是不是在拿数据的过程中数据被修改了,没被修改就是范围超了
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    // 删除上一个被返回的元素
    public void remove() {
        // 如果上个操作没有返回,指定是删不了的
        if (lastRet < 0)
            throw new IllegalStateException();
        // 并发校验
        checkForComodification();
        
        try {
            // 调内部的删除方法
            AbstractList.this.remove(lastRet);
            // 删除了一个当前索引之前的元素,索引往前移一位
            if (lastRet < cursor)
                cursor--;
            // 删除了元素,lastRet置为-1
            lastRet = -1;
            // 删除操作做了修改,expectedModCount同步成modCount的值
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }

    // 并发校验,如果当前数组的modCount和迭代器不一致,直接抛异常,快速失败
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

8.1.2. ArrayList中的实现

private class Itr implements Iterator<E{
    // 后续调用next方法时会被返回的元素的索引
    int cursor;
    // 上一个返回的元素的索引,调用了删除操作时没有返回,设为-1,默认没有返回也是-1
    int lastRet = -1;
    // 迭代器期望得到的modCount,如果出现了并发修改,最后就会不一致
    int expectedModCount = modCount;

    // 判断迭代器后续是否还有元素,当前索引到达数组长度时就没了
    public boolean hasNext() {
        return cursor != size;
    }

    // 获取下一个元素
    @SuppressWarnings("unchecked")
    public E next() {
        // 并发校验
        checkForComodification();
        int i = cursor;
        // 逻辑做了一点优化,索引超过范围直接就抛NoSuchElementException了,有没有并发都不影响它出去了,还省一次并发校验
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        // 索引超过我数组的长度了,那指定是数组变短了,肯定是有人跟我在并发修改
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 都校验完了,索引移一位,lastRet更新,把元素拿出来返回
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    // 删除上一个被返回的元素
    public void remove() {
        // 和AbstractList里一样
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            // 删除
            ArrayList.this.remove(lastRet);
            // 又是一点小小的修改,没什么必要的判断直接胜利,删除元素之前lastRet肯定是比cursor小1,直接赋值快点
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // java 1.8的新接口,支持传函数式接口了,对迭代器中剩下的元素做处理
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        // 这里i是从cursor开始的,之前已经返回的元素就不会被处理了
        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++]);
        }
        // 更新索引,全部迭代玩更新一次就够了,减少消耗
        cursor = i;
        lastRet = i - 1;
        // 之前出现并发修改只是不操作数据了,并没有给用户提示,最后校验一次,有异常抛异常
        checkForComodification();
    }

    // 并发校验,如果当前数组的modCount和迭代器不一致,直接抛异常,快速失败
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

8.2. listIterator双向遍历

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

// 相较于iterator可以支持传入索引了,一进来就可以从指定位置开始迭代
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

private class ListItr extends Itr implements ListIterator<E{
    /* */
}

listIterator在iterator的基础上,实现了往前遍历,和iterator一样,listIterator也是ArrayList内部实现的

8.2.1. AbstractList中的实现

private class ListItr extends Itr implements ListIterator<E{
    // 带参数的构造方法,初始化cursor
    ListItr(int index) {
        cursor = index;
    }

    // 新加的方法,看前面有没有元素
    public boolean hasPrevious() {
        return cursor != 0;
    }

    // 往前获取一个元素
    public E previous() {
        // 并发校验
        checkForComodification();
        try {
            // 跟next()方法逻辑一样,只有前后的差别
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    // 获取下一个元素的索引
    public int nextIndex() {
        return cursor;
    }

    // 获取前一个元素的索引
    public int previousIndex() {
        return cursor-1;
    }

    // 修改上一个返回的元素
    public void set(E e) {
        // 如果之前没有返回元素,直接抛异常
        if (lastRet < 0)
            throw new IllegalStateException();
        // 并发校验
        checkForComodification();

        try {
            // 调用内部方法修改,expectedModCount同步
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // 在当前位置插入元素
    public void add(E e) {
        // 并发校验
        checkForComodification();

        try {
            int i = cursor;
            // 调用内部方法插入元素
            AbstractList.this.add(i, e);
            lastRet = -1;
            // 插入元素后,插入位置之后的元素整体右移了,当前索引加一
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

8.2.2. ArrayList中的实现

基本都跟AbstractList里的一样,有一点微调

private class ListItr extends Itr implements ListIterator<E{
    // 跟AbstractList里的一样
    ListItr(int index) {
        super();
        cursor = index;
    }

    // 跟AbstractList里的一样
    public boolean hasPrevious() {
        return cursor != 0;
    }

    // 跟AbstractList里的一样
    public int nextIndex() {
        return cursor;
    }

    // 跟AbstractList里的一样
    public int previousIndex() {
        return cursor - 1;
    }

    // 获取前一个元素,跟next()方法一样,有一些逻辑上的微调
    @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 {
            // 删除了一行expectedModCount = modCount,因为ArrayList里的set()并不修改modCount
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // 跟AbstractList里的一样
    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();
        }
    }
}

8.3. Spliterator

分割迭代器,java 1.8的新功能,几乎每个集合都实现了它,它是实现并行遍历的基础。使用这个迭代器,可以实现多线程遍历集合的功能,其中每个线程遍历集合中的一段,因此没有线程安全问题。

public Spliterator<E> spliterator() {
    return new ArrayListSpliterator<>(this0, -10);
}

具体实现

static final class ArrayListSpliterator<Eimplements Spliterator<E{
    // 原数组
    private final ArrayList<E> list;
    // 当前迭代器的索引
    private int index;
    // 当前迭代器的结束索引
    private int fence;
    private int expectedModCount;

    ArrayListSpliterator(ArrayList<E> list, int origin, int fence, int expectedModCount) {
        this.list = list;
        this.index = origin;
        this.fence = fence;
        this.expectedModCount = expectedModCount;
    }

    // 获取分割位置的索引,fence在第一次使用时才会被初始化
    private int getFence() {
        int hi;
        ArrayList<E> lst;
        // 如果fence小于0,才会进行计算,否则直接返回
        if ((hi = fence) < 0) {
            // list为null,那还分割什么,直接给个0结束了
            if ((lst = list) == null)
                hi = fence = 0;
            else {
                // fence初始化,第一次的值为数组长度,代表当前分割迭代器需要遍历到的数组的位置
                expectedModCount = lst.modCount;
                hi = fence = lst.size;
            }
        }
        return hi;
    }

    // 尝试分割
    public ArrayListSpliterator<E> trySplit() {
        // hi:当前分割迭代器的结束索引,也就是当前迭代器的长度,也是当前迭代器中元素的个数
        // lo:当前迭代器的起始索引
        // mid:当前迭代器的中间位置
        int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
        // 如果起始位置大于等于中间位置,那分割的也太小了,就别继续分了;还能分就返回一个新的迭代器,新的迭代器的范围是从数组开头到当前迭代器的中间位置
        return (lo >= mid) ? null : new ArrayListSpliterator<E>(list, lo, index = mid, expectedModCount);
    }

    // 分割迭代器单独遍历的接口,支持对元素一个一个进行操作
    public boolean tryAdvance(Consumer<? super E> action) {
        // 参数校验
        if (action == null)
            throw new NullPointerException();
        // 获取当前迭代器的起始位置和结束位置
        int hi = getFence(), i = index;
        // 如果还在可以遍历的范围之内才处理,不然直接返回false
        if (i < hi) {
            // 操作过程,索引加一,把对应元素取出来,执行action中的操作
            index = i + 1;
            @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
            action.accept(e);
            // 并发校验
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return true;
        }
        return false;
    }

    // 对迭代器中剩下的元素做处理
    public void forEachRemaining(Consumer<? super E> action) {
        // i:当前迭代器的起始位置
        // hi:当前迭代器的结束位置
        // mc:modCoutn
        int i, hi, mc;
        ArrayList<E> lst; Object[] a;
        // 参数校验
        if (action == null)
            throw new NullPointerException();
        // 如果list为null或者list中的元素为null,肯定是有并发修改,抛异常
        if ((lst = list) != null && (a = lst.elementData) != null) {
            // 如果当前迭代器的结束位置小于0,那么是第一次初始化,需要给hi重新赋值,modCount和原数组保持一致,否则modCount和迭代器保持一致
            if ((hi = fence) < 0) {
                mc = lst.modCount;
                hi = lst.size;
            }
            else
                mc = expectedModCount;
            // 判断起始位置大于等于0,结束位置小于等于数组长度,简单的循环条件校验
            if ((i = index) >= 0 && (index = hi) <= a.length) {
                // 循环遍历,对剩下的元素做处理
                for (; i < hi; ++i) {
                    @SuppressWarnings("unchecked") E e = (E) a[i];
                    action.accept(e);
                }
                // 如果modCount没有被修改,直接结束,再往下走就会抛异常
                if (lst.modCount == mc)
                    return;
            }
        }
        throw new ConcurrentModificationException();
    }

    // 获得当前迭代器的大小
    public long estimateSize() {
        return (long) (getFence() - index);
    
    }

    // 返回当前迭代器的特征
    public int characteristics() {
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }
}

分割迭代器特征

// 元素是有序的
public static final int ORDERED    = 0x00000010;
// 元素是去重的
public static final int DISTINCT   = 0x00000001;
// 元素是排好序的
public static final int SORTED     = 0x00000004;
// 元素是有限的,没有增加或删除操作时,estimateSize的大小是确定的
public static final int SIZED      = 0x00000040;
// 元素是非空的
public static final int NONNULL    = 0x00000100;
// 元素不能进行增加、替换或删除
public static final int IMMUTABLE  = 0x00000400;
// 在没有外部线程同步的情况下可以被多个线程同时进行修改(增加、替换或删除)
public static final int CONCURRENT = 0x00001000;
// trySplit返回的子分割迭代器都会是SIZED和SUBSIZED的
public static final int SUBSIZED = 0x00004000;

8.4. foreach

java 1.8的新方法,可以传函数式接口进行遍历,逻辑比较简单,依次对所有元素进行操作,如果modCount被改变了就停止遍历,抛出异常

public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

9. 排序

java中的排序有两种方法可以实现

  1. 实现Comparable接口
  2. 使用Comparator比较器

很明显ArrayList没有实现Comparable接口,只能通过Comparator比较器实现,传一个Comparator进来,调用Arrays.sort()进行排序,底层的排序用的是TimSort,一个结合了归并排序和插入排序的算法,这里先不讲了

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

10. 克隆

ArrayList实现了Cloneable接口,重写了clone方法,这里是一个浅拷贝的实现

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

11. 序列化与反序列化

elementData上加了transient,但是elementData存储的是底层数组,我们序列化要保存的就是它,所以添加了writeObject和readObject方法,手动序列化和反序列化数组中的元素

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;
    // 序列化非静态字段和未被transient修饰的字段
    s.defaultWriteObject();

    // 对老版本jdk的兼容,老版本jdk会序列化数组的长度,新版本为了兼容,只能多序列化一次
    s.writeInt(size);

    // 把数组中所有的元素都序列化
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    // 如果序列化过程中被并发修改了,抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
   
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // 反序列化非静态字段和未被transient修饰的字段
    s.defaultReadObject();

    // 把数组长度读进来,啥也不用做
    s.readInt();

    // 当数组中有内容时,把所有元素都读进来
    if (size > 0) {
        // 分配足够的内存
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // 根据数组大小读取对应个数的对象进来
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

12. sublist

ArrayList的一个内部类,没事儿少用,这里有坑

返回原数组的一部分,从fromIndex到toIndex,左闭右开
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this0, fromIndex, toIndex);
}

// 简单的范围校验,没啥可讲的
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}

代码很长,简单看一下内部的实现,把坑都记住就行

private class SubList extends AbstractList<Eimplements RandomAccess {
    // 原数组
    private final AbstractList<E> parent;
    // 当前子列表在原数组中的起始位置
    private final int parentOffset;
    // 当前子列表在原数组中的结束位置
    private final int offset;
    // 当前子列表的大小
    int size;

    // 构造方法,把信息都保存下来
    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        // 操作的是原数组
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }

    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        // 从原数组中取值
        return ArrayList.this.elementData(offset + index);
    }

    public int size() {
        checkForComodification();
        return this.size;
    }

    public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        // 操作的是原数组
        parent.add(parentOffset + index, e);
        this.modCount = parent.modCount;
        this.size++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        // 操作的是原数组
        E result = parent.remove(parentOffset + index);
        this.modCount = parent.modCount;
        this.size--;
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        // 操作的是原数组
        parent.removeRange(parentOffset + fromIndex,
                parentOffset + toIndex);
        this.modCount = parent.modCount;
        this.size -= toIndex - fromIndex;
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;

        checkForComodification();
        // 操作的是原数组
        parent.addAll(parentOffset + index, c);
        this.modCount = parent.modCount;
        this.size += cSize;
        return true;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);
        final int offset = this.offset;

        return new ListIterator<E>() {
            int cursor = index;
            int lastRet = -1;
            int expectedModCount = ArrayList.this.modCount;

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

            @SuppressWarnings("unchecked")
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= SubList.this.size)
                    throw new NoSuchElementException();
                // 操作的是原数组
                Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[offset + (lastRet = i)];
            }

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

            @SuppressWarnings("unchecked")
            public E previous() {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                // 操作的是原数组
                Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i;
                return (E) elementData[offset + (lastRet = i)];
            }

            @SuppressWarnings("unchecked")
            public void forEachRemaining(Consumer<? super E> consumer) {
                Objects.requireNonNull(consumer);
                final int size = SubList.this.size;
                int i = cursor;
                if (i >= size) {
                    return;
                }
                // 操作的是原数组
                final Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                while (i != size && modCount == expectedModCount) {
                    consumer.accept((E) elementData[offset + (i++)]);
                }
                // update once at end of iteration to reduce heap write traffic
                lastRet = cursor = i;
                checkForComodification();
            }

            public int nextIndex() {
                return cursor;
            }

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

            public void remove() {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    // SUbList没有remove方法,使用的是ArrayList中的remove,操作的是原数组
                    SubList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

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

                try {
                    // SUbList没有set方法,使用的是ArrayList中的set,操作的是原数组
                    ArrayList.this.set(offset + lastRet, e);
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

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

                try {
                    int i = cursor;
                    // SUbList没有sadd方法,使用的是ArrayList中的add,操作的是原数组
                    SubList.this.add(i, e);
                    cursor = i + 1;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            final void checkForComodification() {
                if (expectedModCount != ArrayList.this.modCount)
                    throw new ConcurrentModificationException();
            }
        };
    }

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, offset, fromIndex, toIndex);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+this.size;
    }

    private void checkForComodification() {
        if (ArrayList.this.modCount != this.modCount)
            throw new ConcurrentModificationException();
    }

    public Spliterator<E> spliterator() {
        checkForComodification();
        return new ArrayListSpliterator<E>(ArrayList.this, offset,
                offset + this.size, this.modCount);
    }
}

总的来说就是操作subList中的元素,都会修改原来的ArrayList,这是第一个坑;如果在使用subList的同时对原数组进行了插入或删除操作,modCount并不会同步到SubList中,再对SubList进行操作,就会抛出ConcurrentModificationException,也就是说数据操作的同步是单向的,这是第二个坑

13. 其他方法

13.1. 获取数组大小

public int size() {
    return size;
}

13.2. 校验数组是否为空

public boolean isEmpty() {
    return size == 0;
}

13.3. 校验是否包含某个对象

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

13.4. 缩减内部数组的大小

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        // 把内部数组中没有元素的部分释放掉,减少内存占用
        elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
    }
}

13.5. 扩容

内部使用的是ensureCapacityInternal方法,这个方法是给外部调用的,可以手动跳转内部数组的大小

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

14. 总结

ArrayList的大部分内容都在这儿了,日常使用中其实并不会关心这么多东西,简单概括一下常用的知识点,不踩坑就行

  1. ArrayList底层采用数组实现,拥有快速随机访问能力,但是是非线程安全的集合
  2. ArrayList默认容量为10,要保存新元素时,剩余容量不足会触发扩容,基本规则为扩容到原来的1.5倍
  3. 如果在遍历的时候发生结构性变化(添加或删除元素),会触发ConcurrentModificationException异常

分类:

后端

标签:

Java

作者介绍

住阳台的猫
V1