昨天听一个十年经验的dl讲源码,感觉非常牛逼,对着ArrayList直接往下balabala地讲,逻辑清晰还不带停的。虽然这部分源码挺简单的(?),而且之前也读过几遍,但是这样听下来感觉,我还是有很多不知道的东西。。。不愧是带着实战经验讲源码。

1. 下面代码段会扩容几次?new ArrayList<>(0)

public static void testGrowTime(){
    List<String> list = new ArrayList<>(0);
    list.add("a");list.add("b");list.add("c");list.add("d");
    list.add("e");list.add("f");list.add("g");list.add("h");
    list.add("i");list.add("j");
}

进入了7次grow方法。下面解析一下具体流程。

首先看这个构造函数

new ArrayList<>(0);

它是特意传了一个0进来,会走下面第5行的赋值。

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

看看ArrayList里面的成员变量吧:

// 底层数组
transient Object[] elementData;
// 空数组,即构造函数传0的时候被赋值的
private static final Object[] EMPTY_ELEMENTDATA = {};
// 同样是空数组,即无参构造函数时被赋值的。在第一次扩容的时候,会被赋值成10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

因此,上面的代码一开始的时候会被赋值成EMPTY_ELEMENTDATA,然后等待add的时候扩容。

看第一次add("a")

public boolean add(E e) {
    // 对容量进行检验
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 传入的minCapacity为0+1=1
private void ensureCapacityInternal(int minCapacity) {
    // 确定明确的容量
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算容量 
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 使用无参构造创建的时候,才会赋容量为10(即DEFAULT_CAPACITY),否则返回你所传入的容量大小,这里为1
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
	// 1-0>0成立,走扩容函数
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新数组容量为原数组容量的1.5倍,不足即向下取整,这是右移操作
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 第一次进来,可知newCapacity仍为0,因此容量会被赋为minCapacity,也就是1,从0-->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);
}

// 泛型,处理类型转换问题
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    // 创建新数组 ?
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    // 真正的复制数据的操作,效率高
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

此后的操作再debug一下即可,可以发现它执行了多次的扩容

0 --> 1

1 --> 2

2 --> 3

3 --> 4

4 --> 6

6 --> 9

9 --> 13

这是多么费时的操作,如果知道它只用于存储小容量的元素的时候,可以这样做,不然就会在初始时候耗时较大的时间在扩容操作中。

2. 看看这类空集合:Arrays.asList()和Collections.emptyList()

public static void testEmpty(){
    List<String> list1 = Arrays.asList();
    list1.add("a");
    List<String> list2 = Collections.emptyList();
    list2.add("a");
}

先说结论,这两个集合都非常神奇,它不是我们平常见到的ArrayList,而是一些自定义的静态内部类,并且都是不可以修改的。

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

看着非常神奇,这个是我们用的ArrayList吗?其实不是,这是Arrays工具类中自己定义的一个ArrayList,只是重名了而已。看看源码。

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable
{
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }

    @Override
    public int size() {
        return a.length;
    }

    @Override
    public Object[] toArray() {
        return a.clone();
    }

    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size)
            return Arrays.copyOf(this.a, size,
                                 (Class<? extends T[]>) a.getClass());
        System.arraycopy(this.a, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    @Override
    public E get(int index) {
        return a[index];
    }

    @Override
    public E set(int index, E element) {
        E oldValue = a[index];
        a[index] = element;
        return oldValue;
    }

    @Override
    public int indexOf(Object o) {
        E[] a = this.a;
        if (o == null) {
            for (int i = 0; i < a.length; i++)
                if (a[i] == null)
                    return i;
        } else {
            for (int i = 0; i < a.length; i++)
                if (o.equals(a[i]))
                    return i;
        }
        return -1;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(a, Spliterator.ORDERED);
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        for (E e : a) {
            action.accept(e);
        }
    }

    @Override
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        E[] a = this.a;
        for (int i = 0; i < a.length; i++) {
            a[i] = operator.apply(a[i]);
        }
    }

    @Override
    public void sort(Comparator<? super E> c) {
        Arrays.sort(a, c);
    }
}

但发现它并没有add()方法呀?原来它继承了一个extends AbstractList<E>,实现了与java.util.ArrayList相同的抽象类。

而这个静态内部类ArrayList并没有重写add()方法,它原始的方法会抛出异常。

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

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

同理,我们也来看看,Collections的空集合。

public static final List EMPTY_LIST = new EmptyList<>();

public static final <T> List<T> emptyList() {
    return (List<T>) EMPTY_LIST;
}

好家伙,又实现了一个不认识的EmptyList,看源码,它同样是继承了AbstractList,且没有重写add()方法,因此会和上面的抛出一样的异常。

private static class EmptyList<E>
    extends AbstractList<E>
    implements RandomAccess, Serializable {
    private static final long serialVersionUID = 8842843931221139166L;

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

    public int size() {return 0;}
    public boolean isEmpty() {return true;}

    public boolean contains(Object obj) {return false;}
    public boolean containsAll(Collection<?> c) { return c.isEmpty(); }

    public Object[] toArray() { return new Object[0]; }

    public <T> T[] toArray(T[] a) {
        if (a.length > 0)
            a[0] = null;
        return a;
    }

    public E get(int index) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }

    public boolean equals(Object o) {
        return (o instanceof List) && ((List<?>)o).isEmpty();
    }

    public int hashCode() { return 1; }

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        return false;
    }
    @Override
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
    }
    @Override
    public void sort(Comparator<? super E> c) {
    }

    // Override default methods in Collection
    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
    }

    @Override
    public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }

    // Preserves singleton property
    private Object readResolve() {
        return EMPTY_LIST;
    }
}

但是课上,这段代码的RandomAccess接口却被喷了【x】,里面都没有元素,为什么要用这个接口呢。这个是一个空接口,表明如果你遇到这类的集合,建议使用for+index下标查找元素,否则可以考虑采用迭代器。

3. public ArrayList(Collection<? extends E> c)

下面就开始一个一个地读源码了,几乎把ArrayList所有的代码都读了一遍,不带停的。

我一开始还想着,这段代码我都看了好多遍了,看完之后,我还是太年经。。。

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

第一行,c.toArray(),因为这个ArrayList底层是Object[] elementData,所以要把传入的集合转成数组,才方便后续的数组值的复制。

// 这里看ArrayList的toArray(),根据不同的Collection看不同的toArray()实现
// 这里就很明显,如果传入的c是ArrayList,那就是把它的elementData复制一份,并返回
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    // 根据类型来判断,如果是Object就直接创建,不然就根据给定的类型创建对应的数组
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
} 

// 这是一个本地方法
public static Object newInstance(Class<?> componentType, int length)
    throws NegativeArraySizeException {
    return newArray(componentType, length);
}    
private static native Object newArray(Class<?> componentType, int length)
        throws NegativeArraySizeException;

接下来判断一下是否有元素,如果没有就返回一个空集合(非常熟悉的EMPTY_ELEMENTDATA,它就是调用入参为0的构造函数时创建ArrayList的情况)

如果有元素,就看看它的类型,如果是ArrayList,就直接把复制出来的数组给elementData,如果不是,就要执行数组元素的复制。

4. public void trimToSize()

作用就是缩减空间,我们知道它的扩容其实是按1.5倍进行,后面会有不少的空元素,使用这个方法可以让底层的elementData按照实际的元素容量进行存储。

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

如果空间为0,就直接给它空数组,不然就复制元素,让集合更“紧凑”

5. public void ensureCapacity(int minCapacity)

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

为数不多的public的方法,主要作用是提前扩容。

它第一个比较。。有点鸡肋?看不懂,是要判断一下是否需要扩容吗?总觉得有点鸡肋

6. public int indexOf(Object o)

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

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

可以与RandomAccess接口相映衬,可以看到,这种是直接用下标寻址效率更高。

我一开始还傻傻地有个疑问,为什么不直接都用equals进行判断,即使是空也能判断啊?

问题是,如果是找空的元素,那说明equals左右两边都是空,但是空对象没有equals方法,会报空指针异常。

7. public Object 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);
    }
}

浅克隆。

相当于创建一个新的对象了,它把elementData复制了一份,并且清空了modCount。

下面会再说到这个modCount,每一次操作都会使之加一,即使是批量操作也是如此。

8. public E get(int index)

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}	

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

获取一个元素,先检查范围,然后再获取元素。

不懂为什么要这样写两个方法,是因为方便复用吗,后面看到确实是有些用到这样的,但是。。

9. public E set(int index, E element)

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

同样是,先检查范围,然后再设置值。

不过这里需要返回旧元素的值,同时也看出,上面重复的两个方法。确实是有复用了,并且看得好看一些。

10. public void add(int index, E element)

public void add(int index, E element) {
    rangeCheckForAdd(index);

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

这里最重要的就是System.arraycopy,它可以帮我们复制底层的元素,让它移动到合适的位置。

然后把留下来的空位放置新的元素中。

11. public E remove(int index)

public E remove(int index) {
    // 检查范围
    rangeCheck(index);

    modCount++;
    // 取旧值
    E oldValue = elementData(index);
	// 计算要移动的元素
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 把index后一位的所有元素前移一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

这里最值得学习的地方是,删除了最后一个元素后,你会不会记得把它置为空?

12. public boolean remove(Object o)

上面的方法是删除下标的元素,这里是删除目标对象。这就没办法了,只能全部遍历一遍,找到了就删除它,找不到就算了。。。

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 remove method that skips bounds checking and does not
 * return the value removed.
 * 不用范围检查和返回值,因此它fast!
 * 类似public E remove(int index)
*/
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
}

13. public void clear()

如果要用一个新的对象,那还是用clear比重新new一个比较好。

主要是不用扩容,并且还是保留原数组的大小。

public void clear() {
    modCount++;

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

    size = 0;
}

14. public boolean addAll(Collection<? extends E> c)

这个addAll也是在课堂上被bb的一段代码。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 把c的数组元素复制到elementData的后面
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

主要是它的返回值有问题,numNew != 0判断显得太暴力了。

如果我加入的c是空的,那它的numNew为0,返回false,所以我的方法执行是成功还是失败?

这就很有误解了。

因此,以后开发的时候,如果要依赖addAll的返回值,要小心。

(不过它的注释里面写道,Returns: true if this list changed as a result of the call,我放一个空的集合进去,它确实是没有change。。。)

15. public boolean addAll(int index, Collection<? extends E> c)

这个是在中间插入特定元素,这个显得有点麻烦。

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);
    // 插入c的数组元素
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

16. protected void removeRange(int fromIndex, int toIndex)

首先这个protected,就是只能同包中的类能够使用,或者不同包的子类能用,注意一下语法。

然后,这里的操作是范围删除,注意一下范围,是左闭右开(whose index is between fromIndex, inclusive, and toIndex, exclusive. ),并且左、右相等时,此方法无效。

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

17. private boolean batchRemove(Collection<?> c, boolean complement)

这个也是被喷的一处,主要当入参c为空时,创建了很多额外的变量,且进行多次判断后才有结果。应该在一开始的时候就对空集合进行判断,从而快速获取结果。

还有那个try-finally,没有catch异常,这也很。。

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)
                // w的指针指向需要保留的下标位置,r一直向前跑
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 突然悟了,这是多线程情况下,别的线程把size改了,导致r != size的时候,
        // 把新增加的元素放到后面
        // 或者是,在c.contains出异常的时候,跳转出来执行finally
        // 剩余的元素就不判断了直接放后面
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // w != size说明,w后面的元素都是要删除的
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            // 每删除一个,这个计数器都要加1
            modCount += size - w;
            size = w;
            // 改结果,有删除,才会返回true,否则batchRemove失败
            modified = true;
        }
    }
    return modified;
}

上面的方法是private的,看看真正调它的是哪些方法

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

public static <T> T requireNonNull(T obj) {
    if (obj == null)
        throw new NullPointerException();
    return obj;
}

可以看到,它确实是有提前判断集合c,但是它仅仅判断集合是否为null,不判断集合内是否有元素有元素,应该自己写一个方法来判断,而不是直接用Objects的工具。。

然后第二个参数,其实就是判断是否保留,看回函数中的语句c.contains(elementData[r]) == complement,如果入参是true,就说明是contains的元素,那存在的就要保留,也就是对应retainAll方法;否则就是removeAll,不存在c中的元素就留着,剩下的干掉。

18. 序列化

transient Object[] elementData;

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    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;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

就是,一个一个地把对象读出,无视空元素?写入也同理

剩下的是迭代器,可以不用看了。。ArrayList不需要迭代器,用下标寻址更快。