ArrayList 源码阅读

主要 API

java

//在末尾添加一个元素
boolean add(Object)

//在指定位置添加一个元素,索引从零开始,可以追加到链表末尾
void add(int,Object)

//在末尾添加多个元素
boolean addAll(Collection)

//在指定位置添加多个元素,索引从零开始,可以追加到链表末尾
boolean addAll(int,Collection)


//移除指定位置元素
Object remove(int)

//移除找到的第一个元素
boolean remove(Object)

//移除满足条件的元素
boolean removeIf(Predicate)

//移除多个元素
boolean removeAll(Collection)

//截取成新的子链表(包括头不包括尾)
List subList(int,int)


//覆盖指定位置元素
Object set(int,Object)

//只保留给定的多个元素
boolean retainAll(Collection)

//替换满足
void replaceAll(UnaryOperator)


//获取指定位置元素
Object get(int)

//返回最后一次查找到的元素的索引
int indexOf(Object)

//返回最后一次查找到的元素的索引
int lastIndexOf(Object)

//是否包含指定元素
boolean contains(Object)

//是否包含所有元素
boolean containsAll(Collection)

//是否为空
boolean isEmpty()

//元素个数
int size()

//遍历
void forEach(Consumer) 


//提前确保分配了最小容量
void ensureCapacity(int)

//将容量缩小到和元素个数一样多
void trimToSize()

//浅克隆
Object clone()

//清空
void clear()

//排序
void sort(Comparator)


//转换成数组
Object[] toArray()

//转换成数组并装到给定的数组(如果给定的数组长度足够,否则还是返回会新数组)
Object[] toArray(Object[])

Iterator iterator()

Spliterator spliterator()

ListIterator listIterator(int)

ListIterator listIterator()

Java ArrayList的设计

凡是涉及到索引的操作前都会进行索引检查
凡是涉及添加元素的，添加前都会确保最小容量满足
只会自动扩容，不会自动缩容
扩容都是copy数组后返回一个更大容量的新数组
挪动数组是用native方法System.arraycopy()完成的
是线程不安全的
可以存储 null
添加元素到指定位置时的索引可以是最后一个元素的后面一个，即追加元素
无参构造默认容量为 10 但只有到第一次添加元素时才真正申请空间
默认最大容量为 2³¹ - 1 - 8 实际最大容量为 2³¹ - 1，减8的原因是，有的虚拟机的对象头会多占用八个位使int不能达到最大值 2³¹ - 1
当一次性插入大量元素可以提前使用 ensureCapacity() 扩容来提高性能

六个主要的成员变量

java

//默认容量
private static final int DEFAULT_CAPACITY = 10;


//有参数构造函数且指定容量为0时, 初始化 elementData= EMPTY_ELEMENTDATA
private static final Object[] EMPTY_ELEMENTDATA = {};
//无参数构造函数, 初始化 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//以上两个空数组主要是用来区别第一次添加元素时是扩容到1还是扩容到默认容量(10)

//数组默认最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//存储元素的数组
transient Object[] elementData;
//已存储的元素个数
private int size;

扩容机制流程图

扩容的逻辑

java

//1
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//2
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果 elementData 是无参构造函数构造的
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //从 默认容量10 或者 最小需要容量 中返回两者中大的那一个， 也就是容量至少为10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //如果是有参构造函数构造的，或者不是第一次添加元素了，直接返回需要的最小容量
    return minCapacity;
}

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

    // minCapacity 有可能会溢出
    if (minCapacity - elementData.length > 0)//最小需要容量大于已有容量
        grow(minCapacity);//
}

//4
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //原来的容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 尝试将 新的容量 = 原来的容量 + 原来容量的一半
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;//新的容量还是不能满足我的最小容量， 直接扩容到我需要的最小容量得了
    if (newCapacity - MAX_ARRAY_SIZE > 0)//新得容量超过了最大容量（可能是 原来的容量 + 原来容量的一半 后超过， 也有可能是 minCapacity 直接超过了）
        newCapacity = hugeCapacity(minCapacity); //我不管你怎么超的，你告诉我你想要扩到多少

    // minCapacity is usually close to size, so this is a win:
    // minCapacity 通常接近（稍微大于） size
    elementData = Arrays.copyOf(elementData, newCapacity);
}

//5
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow 溢出了
        throw new OutOfMemoryError();

    if((minCapacity > MAX_ARRAY_SIZE)){// 大于 2的31次方 - 1
        return Integer.MAX_VALUE;//返回 2的31次方 - 1
    }else {
        return MAX_ARRAY_SIZE;//否则返回 2的31次方 - 1 - 8
    }
}

ensureCapacity 确保容量的逻辑

java

//无参构造的， 当外部手动确保容量时
//如果小于默认的10， 那么它是不会确保的， 而是等到第一次添加元素时才申请默认的10个空间
//如果大于默认的10，那么他会立即申请空间到要确保的数值
//如果原有容量已经大于要确保的了，那么他会退出

//有参构造的
//只要外部要确保容量的大于原有容量，那么他会立即确保
//如果原有容量已经大于要确保的了，那么他会退出

public void ensureCapacity(int minCapacity) {
    int minExpand;

    //不是无参构造函数初始化的链表
    if(elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
        minExpand= 0; //那么它就不需要最小扩容
    } else {
        minExpand = DEFAULT_CAPACITY;//否则最小扩容就是10
    }

    //有参构造时，minCapacity要大于0，无参构造时minCapacity要大于10，才尝试扩容
    if (minCapacity > minExpand) { 
        ensureExplicitCapacity(minCapacity);
    }
}

batchRemove 批量删除的逻辑

java

/**
    * 这个方法用来给 removeAll(Collection<?> c) 和 retainAll(Collection<?> c) 调用的
    * @param c 集合
    * @param complement 为 true 时，只保留指定集合中的值( retainAll 保留交集 )，为 false 时，删除指定集合中存在的值( removeAll 保留非交集 )
    * @return 只要发生删除就会返回 true
    */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;//w 为要保留的元素个数，r 为已经遍历过的元素个数
    boolean modified = false;
    try {
        // 遍历数组
        for (; r < size; r++){
            //要保留交集或则保留非交集是有 complement 决定的
            //如要保留交集，这时 complement = ture， 只要 c.contains(elementData[r]) 返回 true，那么elementData[r]就被写入到数组前
            //如果要保留非交集， 这时 complement = ture，只要 c.contains(elementData[r]) 返回 false，那么elementData[r]就被写入到数组前
            //最后把 w 后的元素清空即可
            if (c.contains(elementData[r]) == complement){ 
                elementData[w++] = elementData[r]; 
            }
        }         
    } finally {

        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) { // r != size，说明发生异常，循环未执行完成
            System.arraycopy(elementData, r,elementData, w,size - r); // 将 r 之后的元素挪到 w 后面也保留下来
            w += size - r; //要保留的元素(w) = 没出异常前已经确认保留的元素(w) + 加上出异常后挪过去的元素
        }

        // w == size 说明保留全部元素，否则要把 w 之后的元素设为 null
        if (w != size) {

            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;

            modCount += size - w; // 更新 modCount, 修改的次数 = 原来修改次数 + 那些没有保留被设置成 null 的元素个数
            size = w; // 更新元素个数为保留的元素个数
            modified = true;
        }
    }
    return modified;
}

遍历时不能删除元素的原因

这是由于集合的快速失败机制导致的，因为 ArrayList 等集合是不支持同步操作的，当使用迭代器遍历元素的时候使用集合自带的API修改元素，快速失败机制认为你可能在使用多线程操作集合，马上抛出异常，但可以使用迭代器自带的 add() 和 remove() 等修改集合的元素个数。

快速失败机制主要是通过 modCount 和 expectedModCount 这两个变量完成的，遍历开始时初始化 expectedModCount = modCount，以后每遍历一个元素前都检查 modCount 是否等于 expectedModCount，如果不等于，说明集合被外部修了，直接抛异常，可以调用迭代器的 add() 和 remove()这两个方法，是因为迭代器内部可以自己使 modCount 和 expectedModCount 这两个变量的值相同。

但是快速失败机制并不是外部删除元素就百分之百会触发，有时候删除元素之后刚好迭代器遍历结束了，那么没有下一轮遍历，也就不会检测 modCount 和 expectedModCount 是否相等。