ArrayList源码解读

ArrayList

• 介绍

  ArrayList是基于动态数组的数据结构

  ArrayList 随机访问速度快，中间插入与删除速度慢，尾部插入与删除速度也快。

• 重要属性

//存储元素的数组缓冲区
transient Object[] elementData;
//List的大小
private int size;

• 构造函数一

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

此构造需要传入一个初始化容量initialCapacity；

如果大于0，则创建此大小的数组缓冲区，等于0，则直接使用一个空数组EMPTY_ELEMENTDATA

因此，使用ArrayList的时候如果预先知道其容量，使用此构造方法传入容量，避免内存浪费与add时触发无必要的扩容。

• 构造函数二

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

此构造直接使用一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为数据缓冲区，add时才扩容。

• 构造函数三

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

此构造直接使用传入集合c数组数据作为数据缓冲区。

• get方法

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    return (E) elementData[index];
}

通过index直接从数组缓冲区中获取数据，根据下标取数据快。

• set方法

public E set(int index, E element) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}

直接从数组缓冲区替换指定index的数据，速度快。

• add方法

public boolean add(E e) {
    //确保内部容量够用
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //DEFAULT_CAPACITY = 10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//真正扩容数组缓冲区
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // a >> 1 相当于 a / 2^1 取整
    // a >> 2 相当于 a / 2^2 取整
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    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);
}

举例说明一下扩容：

`假设当前数组缓冲区大小为10，ArrayList.size也为10，`

`=> add(ele)`

    `=> ensureCapacityInternal(11) // size+1 = 11`

        `=> ensureExplicitCapacity(11)`

            `=> grow(minCapacity = 11)`

                `=> oldCapacity = elementData.length = 10`

                     `newCapacity = oldCapacity + (oldCapacity >> 1) = 15`

                     `...这块未影响newCapacity的值`

                     `elementData = Arrays.copyOf(elementData, newCapacity)，此时elementData.length = newCapacity = 15了`

`=>elementData[10] = ele;// size++ 先使后加`    

add如果不触发扩容的话速度非常快，触发扩容需要数组copy，速度会受到影响

• add方法(从指定index add)

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //确保数组容量够用
    ensureCapacityInternal(size + 1);
    //将数组缓冲区中index之后的数据，向后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

此方法相比在上一add方法，多一步数组拷贝过程。

• remove方法(通过index)，返回旧的数据

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    modCount++;
    //取出当前index之前的值，下面作为方法返回值
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    //大于0，说明不是移除最后一个元素，需要将index之后的数据往前移一位
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //最后一个一定没用了，置为空，让gc去管
    elementData[--size] = null;
    return oldValue;
}

如果是移除最后一个元素的话，不涉及数组copy，速度很快；

如果移除非最后一个元素，需要数组copy，速度会受影响。

• remove方法(通过元素)，返回是否移除前是否包含该元素

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

遍历元素，找到与传入元素相等的元素的index，然后移除(过程与上面通过index remove的过程相同)；

注意：如果元素中包含重复的元素，则仅移除前面的那个元素(因为是从前往后找index的);

• addAll方法

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) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(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;
}

addAll 跟上面add方法基本一样。

• removeAll方法

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
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++)
            //complement=false
            //如果c不包含elementData[r],把elementData[r]保留
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 看上面的for循环，没有多线程并发问题的话，r一定是等于size的，
        // 这个if不会命中
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        //如果不是全部移除，w肯定不等于size，
        //这个if命中，把多余的元素置空
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

举例分析以下代码：

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> c = new ArrayList<>(Arrays.asList(1, 3, 5));
list.removeAll(c);
System.out.println(list);// 输出[2, 4, 6, 7]

1.原始数据

1	2	3	4	5	6	7	_	_	_

2.batchRemove == for循环完后=>

2	4	6	7	5	6	7	_	_	_

3.置空多余元素

2	4	6	7	_	_	_	_	_	_

• subList(int fromIndex, int toIndex)

public List<E> subList(int fromIndex, int toIndex) {
    //检查index是否异常
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
private class SubList extends AbstractList<E> implements 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) {
        //......
        ArrayList.this.elementData[offset + index] = e;
        //......
    }

    public E get(int index) {
        //......
        return (E) ArrayList.this.elementData[offset + index];
    }

    public void add(int index, E e) {
        //......
        parent.add(parentOffset + index, e);
        //......
    }

    public E remove(int index) {
        //......
        E result = parent.remove(parentOffset + index);
        //......
    }

    protected void removeRange(int fromIndex, int toIndex) {
        //......
        parent.removeRange(parentOffset + fromIndex, parentOffset + toIndex);
        //......
    }

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

    public boolean addAll(int index, Collection<? extends E> c) {
        //......
        parent.addAll(parentOffset + index, c);
        //......
    }
    
    //......
}

该方法返回的不是ArrayList，而是SubList;

SubList相当于是原ArrayList的一个映射，[fromIndex, toIndex);

子list实际上是修改的父ArrayList。

父list操作后，子list再操作会抛出异常 ConcurrentModificationException，是因为父list操作后不会把modCount同步给子list。

• clear方法

public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

遍历将数组缓冲区全部置空，size置0。