转载

ArrayList源码阅读分析

ArrayList是最常用的一种集合类型。今天通过阅读源码的方式来加深对它的学习和理解。 ##实现接口

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
复制代码

通过源码可以看到ArrayList继承自AbstractList,实现了List接口、RandomAccess接口、Cloneable接口、Serializable接口。说明它具备以下特点：

浅拷贝
序列化

常量

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
复制代码

DEFAULT_CAPACITY 表示默认的容量是10个元素。

成员变量

transient Object[] elementData;
private int size;
复制代码

elementData为实际存储元素的数组，这里可以看到ArrayList的底层实际是一个数组。因此它具有数组的特点，随机读写快，插入删除慢。 transient关键字说明底层数组不能被序列化。？？

构造函数

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
复制代码

无参构造函数，构造一个空的数组。

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);
        }
    }
复制代码

指定容量构造，构造一个指定初始容量大小的数组。

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;
        }
    }
复制代码

通过另外一个集合来构造。

添加元素方法

追加

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
复制代码

这里可以看到add方法是线程不安全的，因为size++操作并非原子操作。因此也说明ArrayList类是线程不安全的类。 ensureCapacityInternal()方法保证数组容量可以容纳新增的这个元素，不会出现数组越界的情况。

插入

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++;
    }
复制代码

指定index位置插入元素，其逻辑如下：

校验index是否有效范围，否则抛出数组越界异常.
扩容确保能有效插入。
将原数组index位置之后的元素全部后移一个位置。
将index位置设置为待插入元素。

添加集合方法

追加集合

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;
    }
复制代码

和追加单个元素的原理类似，不同之处在于追加方式在于使用System.arraycopy方法。

插入集合

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

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
复制代码

和插入单个元素的原理类似，不同之处在于index之后的元素往后移的位置为插入集合的长度。

移除元素方法

根据索引移除

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);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
复制代码

逻辑如下：

校验index是否合法，否则抛出数组越界异常
将index+1及以后的元素往前移一个位置
将最后一个元素置为null，同时size减一
返回删除的元素值。

删除元素

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;
    }
复制代码

原理简单，就是通过遍历的方式。但是需要注意的是，只会移除第一个找到的元素。 fastRemove方法和remove(index) 方法作用相同，只是去掉了边界校验和返回值。

查询

通过索引获取元素

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

        return elementData(index);
    }
复制代码

原理就是通过数组获取指定index的元素。

从前往后查找第一个出现的元素

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;
    }
复制代码

集合运算

并集

并集就是addAll方法

交集

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

差集

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

交集和差集都调用了batchRemove方法，通过一个boolean标记来表示要留下的是相同的一部分还是不同的一部分。 batchRemove方法的写法还是值得学习。

batchRemove

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)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            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;
    }
复制代码

双指针的思路，一个读指针，一个写指针。读指针每次往前增加一个位置，写指针遇到要保留的元素时，再往前移动一个位置。最后，如果读指针没走到最后就异常了，那把剩下读指针剩下的元素拷贝到写指针之后。如果写指针没到最后，说明写指针后面的元素都需要剔除，手动置为null，否则会内存泄露。如果写指针走到了最后，说明一个元素都没有移除掉，所以返回false。

原文 https://juejin.im/post/5ce509736fb9a07ea420544d

正文到此结束