源码篇-ArrayList

一、主要的成员变量

/**
 * 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 = {};

/**
 * 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.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

protected transient int modCount = 0;

• DEFAULT_CAPACITY 表示初始的list容量大小
• EMPTY_ELEMENTDATA 表示空的list集合
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA 表示带有默认容量的空的数值集合，与EMPTY_ELEMENTDATA区分是为了第一次添加元素时如何去扩容
• elementData表示list对象
• size表示list大小
• modCount 表示集合修改次数，防止并发造成数据不一致问题

二、创建ArrayList

1、空构造函数

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

• 这里是将elementData赋予DEFAULTCAPACITY_EMPTY_ELEMENTDATA

2、带集合参数的构造函数

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

• 将collection转为集合elementData
• 如果elementData 的长度为0，那么将elementData 赋予EMPTY_ELEMENTDATA，这里要与空构造函数赋值进行区别
• 如果elementData的长读不为0，赋值size；如果elementData对象不是Object[].class类型，转换为Object[].class类型

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

• 如果初始容量大于0，创建对应容量的数值对象，并赋给elementData
• 如果初始容量等于0，将EMPTY_ELEMENTDATA赋给elementData

三、添加元素

1、在list末尾添加单个元素

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

• modCount++表示修改次数加1
• add执行元素添加

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

• 如果添加元素的数量与数组的长度相等，开始扩容
• 如果添加元素的数量与数组的长度不相等，向数组的末尾添加元素，元素的总数量加1

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

• newCapacity(minCapacity)，传入最小的扩容大小，最后返回实际的扩容大小
• Arrays.copyOf会根据原数组，返回指定大小的数值

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

• 将容量扩大0.5倍，如果扩大后的容量newCapacity 小于最小扩容量minCapacity，若elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则返回DEFAULT_CAPACITY与minCapacity之间的最大值，否则返回minCapacity
• 如果扩大后的容量大于最小扩容量，若扩大后的容量小于最大允许容量MAX_ARRAY_SIZE ，则返回扩大后的容量newCapacity，否则根据hugeCapacity(minCapacity)进一步判断需要扩大的容量

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

• 若最小的扩容量minCapacity大于最大允许扩容量MAX_ARRAY_SIZE，则返回Integer的最大值，否则返回MAX_ARRAY_SIZE

2、指定位置添加单个元素

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

• 检查索引值index
• 修改次数加1
• 判断是否需要扩容
• System.arraycopy复制元素，System.arraycopy是本地方法，用的是浅拷贝
• 在指定位置添加元素
• 元素数量加1

3、在末尾添加集合

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

• 将集合转为Object数组
• 修改次数加1
• 获取要添加集合的长度
• 判断是否需要扩容
• 利用System.arraycopy将集合添加至末尾
• 元素数量加numNew

4、在指定位置添加集合

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);

    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size = s + numNew;
    return true;
}

• 前面主要是对index的验证，获取要添加集合的长度以及判断是否需要扩容
• 第一次System.arraycopy主要是将原index之后的数据移动到index+numNew
• 第二次System.arraycopy是将集合数据添加到原list列表中
• list元素的数量加numNew

四、查找元素

1、获取元素的索引值

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

• 分两种情况，如果元素为null，遍历elementData，返回第一个未null元素的索引值

• 如果元素不为null，遍历elementData，根据元素实现的equals方法去判断是否相等，返回第一个相等元素索引值

• 如果没有查到，返回-1

2、根据索引值获取元素

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

• 直接根据索引值从数值中获取元素

五、删除元素

1、根据索引值删除元素

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

• 获取该索引值
• 修改次数加1，元素数量减1，利用System.arraycopy对数据移动，将末尾值改为null
• 返回被删除的值

2、删除指定元素

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

• 主要是遍历获取元素的索引值，最后根据索引值，调用fastRemove进行删除操作

3、批量删除

public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false, 0, size);
}

boolean batchRemove(Collection<?> c, boolean complement,
                    final int from, final int end) {
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r;
    // Optimize for initial run of survivors
    for (r = from;; r++) {
        if (r == end)
            return false;
        if (c.contains(es[r]) != complement)
            break;
    }
    int w = r++;
    try {
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement)
                es[w++] = e;
    } catch (Throwable ex) {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        throw ex;
    } finally {
        modCount += end - w;
        shiftTailOverGap(es, w, end);
    }
    return true;
}

• batchRemove有个参数complement，若为false，则删除与参数c匹配的元素，本次删除是false；若为true，则保留与c匹配的元素，retainAll函数传入的值就是true
• 首先遍历elementData，如果c包含该元素，则跳出，此时已经获取第一个需要重写的位置
• 再次遍历elementData，如果c包含该元素，则继续遍历；如果不包含，则将该元素写入到es
• 更改修改次数
• 调用shiftTailOverGap修改元素个数，已经剩下位置的元素置为null

4、条件批量删除

public boolean removeIf(Predicate<? super E> filter) {
    return removeIf(filter, 0, size);
}

boolean removeIf(Predicate<? super E> filter, int i, final int end) {
    Objects.requireNonNull(filter);
    int expectedModCount = modCount;
    final Object[] es = elementData;
    // Optimize for initial run of survivors
    for (; i < end && !filter.test(elementAt(es, i)); i++)
        ;
    // Tolerate predicates that reentrantly access the collection for
    // read (but writers still get CME), so traverse once to find
    // elements to delete, a second pass to physically expunge.
    if (i < end) {
        final int beg = i;
        final long[] deathRow = nBits(end - beg);
        deathRow[0] = 1L;   // set bit 0
        for (i = beg + 1; i < end; i++)
            if (filter.test(elementAt(es, i)))
                setBit(deathRow, i - beg);
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        modCount++;
        int w = beg;
        for (i = beg; i < end; i++)
            if (isClear(deathRow, i - beg))
                es[w++] = es[i];
        shiftTailOverGap(es, w, end);
        return true;
    } else {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        return false;
    }
}

• filter.test函数判断是否匹配，匹配返回真，不匹配返回false
• 获取第一个匹配的索引值
• 定义deathRow，若符合条件则相应的元素位置置为1
• isClear判断是否需要清除，若为0，返回为真，不需要清除，那么赋值给es
• shiftTailOverGap将剩下的位置元素置为null

5、删除索引区间的元素

protected void removeRange(int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
        throw new IndexOutOfBoundsException(
                outOfBoundsMsg(fromIndex, toIndex));
    }
    modCount++;
    shiftTailOverGap(elementData, fromIndex, toIndex);
}


private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, size - hi);
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}

• System.arraycopy将数值元素迁移
• 将剩下的位置元素置为null

六、改变元素

@Override
public void replaceAll(UnaryOperator<E> operator) {
    replaceAllRange(operator, 0, size);
    modCount++;
}

private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
    Objects.requireNonNull(operator);
    final int expectedModCount = modCount;
    final Object[] es = elementData;
    for (; modCount == expectedModCount && i < end; i++)
        es[i] = operator.apply(elementAt(es, i));
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

• 遍历elementData，对每个元素执行operator.apply，最相应的更改