顺序存储结构之ArrayList源码分析

顺序存储结构之ArrayList源码分析

• 顺序存储结构的优缺点

优点：查询很快
缺点：插入和删除效率慢

在Java中，我们常见具有代表性的顺序存储结构有很多，这里我们以ArrayList为例，进行分析，看看它内部是如何实现顺序存储结构的。

public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {

    //最小容量值 ，默认为12，java中默认为10
    private static final int MIN_CAPACITY_INCREMENT = 12;

    //当前列表中的元素个数
    int size;

    //ArrayList是基于数组的方式实现的，此为初始化创建的Object数组，transient是用来反序列化的
    transient Object[] array;

    /**
     * 创建一个指定带容量大小的ArrayList
     */
    public ArrayList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity < 0: " + capacity);
        }
        array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
    }

    /**
     * 创建一个无参构造的ArrayList
     */
    public ArrayList() {
        array = EmptyArray.OBJECT;
    }

    /**
     * 创建一个包含collection的ArrayList
     */
    public ArrayList(Collection<? extends E> collection) {
        if (collection == null) {
            throw new NullPointerException("collection == null");
        }

        //将集合转成Object[]
        Object[] a = collection.toArray();
        //判断数组的类型
        if (a.getClass() != Object[].class) {
            //如果原数组不是Object类型的数组,定义一个新的、同样长度的Object[]
            Object[] newArray = new Object[a.length];
            //将原数组a的内容从位置0开始拷贝到新的数组newArray位置0,拷贝长度为原数组长度a,即将原数组所以内容拷贝到新数组
            System.arraycopy(a, 0, newArray, 0, a.length);
            //将新数组赋值给原数组a
            a = newArray;
        }
        //记录下数组、元素个数
        array = a;
        size = a.length;
    }

    /**
     * 添加方法，添加到列表的尾部
     */
    @Override public boolean add(E object) {
        Object[] a = array;//将array赋值给一个局部Object数组
        int s = size;// 用局部的s获取长度
        if (s == a.length) {// 如果现在的长度等于数组array的长度，那么空间满了，需要声明一个新数组
            Object[] newArray = new Object[s +
                    (s < (MIN_CAPACITY_INCREMENT / 2) ?
                            MIN_CAPACITY_INCREMENT : s >> 1)];// s<6?12:6
            System.arraycopy(a, 0, newArray, 0, s);// 把原来的数组拷贝到新的数组中来
            array = a = newArray;//赋值并记录
        }
        a[s] = object;//s位置赋值
        size = s + 1;// 长度+1
        modCount++;// 计量器，只要数组中元素动一下，它就+1
        return true;
    }

    /**
     * 添加方法，添加到指定位置
     */
    @Override public void add(int index, E object) {
        Object[] a = array;//将array赋值给一个局部Object数组
        int s = size;// 用局部的s获取长度
        if (index > s || index < 0) {
            throwIndexOutOfBoundsException(index, s);
        }

        if (s < a.length) {// 当数组长度容量足够时，执行System.arraycopy方法实现数组的复制(index~lastIndex  ====>>(拷贝)  (index+1)~(lastIndex+1))
            System.arraycopy(a, index, a, index + 1, s - index);
        } else {// 当数组容量不足时，进行扩容
            // assert s == a.length;
            // 创建新数组，newCapacity为新数组长度，扩容方式和上面的add方法相同
            Object[] newArray = new Object[newCapacity(s)];
            //将数据拷贝到新数组中
            System.arraycopy(a, 0, newArray, 0, index);
            //(index~lastIndex  ====>>(拷贝)  (index+1)~(lastIndex+1))
            System.arraycopy(a, index, newArray, index + 1, s - index);
            array = a = newArray;
        }
        a[index] = object;//index位置赋值
        size = s + 1;// 长度+1
        modCount++;// 计量器，只要数组中元素动一下，它就+1
    }

    /**
     * 扩容大小计算
     */
    private static int newCapacity(int currentCapacity) {
        int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
                MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
        return currentCapacity + increment;
    }

    /**
     * 添加方法，将容器中所有元素添加到此列表的尾部
     */
    @Override public boolean addAll(Collection<? extends E> collection) {
        Object[] newPart = collection.toArray();//将要插入的集合转成数组并赋值给一个局部Object数组
        int newPartSize = newPart.length;//局部newPartSize记录插入数组的长度
        if (newPartSize == 0) {
            return false;
        }
        Object[] a = array;//将array赋值给一个局部Object数组
        int s = size;// 用局部的s获取长度
        int newSize = s + newPartSize; //计算添加后，数组的长度
        if (newSize > a.length) {//如果当前数组的长度不够，则需要进行扩容
            //创建一个新的扩容数组
            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
            Object[] newArray = new Object[newCapacity];
            //将数组拷贝到新的数组
            System.arraycopy(a, 0, newArray, 0, s);
            //将新数组赋值给原数组
            array = a = newArray;
        }
        //将要插入的数组newPart,插入到原数组a的尾部。
        System.arraycopy(newPart, 0, a, s, newPartSize);
        size = newSize;//赋值当前数组的长度
        modCount++;// 计量器，只要数组中元素动一下，它就+1
        return true;
    }

    /**
     * 添加方法，将容器中所有元素添加到此列表的指定位置
     */
    @Override
    public boolean addAll(int index, Collection<? extends E> collection) {
        int s = size;
        if (index > s || index < 0) {
            throwIndexOutOfBoundsException(index, s);
        }
        Object[] newPart = collection.toArray();
        int newPartSize = newPart.length;
        if (newPartSize == 0) {
            return false;
        }
        Object[] a = array;
        int newSize = s + newPartSize; // If add overflows, arraycopy will fail
        if (newSize <= a.length) {
            System.arraycopy(a, index, a, index + newPartSize, s - index);
        } else {
            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(a, 0, newArray, 0, index);
            System.arraycopy(a, index, newArray, index + newPartSize, s-index);
            array = a = newArray;
        }
        System.arraycopy(newPart, 0, a, index, newPartSize);
        size = newSize;
        modCount++;
        return true;
    }

    /**
     * This method was extracted to encourage VM to inline callers.
     * TODO: when we have a VM that can actually inline, move the test in here too!
     */
    static IndexOutOfBoundsException throwIndexOutOfBoundsException(int index, int size) {
        throw new IndexOutOfBoundsException("Invalid index " + index + ", size is " + size);
    }

    /**
     * 清空ArrayList集合中所有元素，使用Arrays.fill方法，将其填充为null
     */
    @Override public void clear() {
        if (size != 0) {
            Arrays.fill(array, 0, size, null);
            size = 0;
            modCount++;
        }
    }

    /**
     * 克隆方法，由于ArrayList实现了Cloneable接口，所以能被克隆
     */
    @Override public Object clone() {
        try {
            ArrayList<?> result = (ArrayList<?>) super.clone();
            result.array = array.clone();
            return result;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError();
        }
    }

    /**
     * Ensures that after this operation the {@code ArrayList} can hold the
     * specified number of elements without further growing.
     *
     * @param minimumCapacity
     *            the minimum capacity asked for.
     */
    public void ensureCapacity(int minimumCapacity) {
        Object[] a = array;
        if (a.length < minimumCapacity) {
            Object[] newArray = new Object[minimumCapacity];
            System.arraycopy(a, 0, newArray, 0, size);
            array = newArray;
            modCount++;
        }
    }

    @SuppressWarnings("unchecked") @Override public E get(int index) {
        if (index >= size) {
            throwIndexOutOfBoundsException(index, size);
        }
        return (E) array[index];
    }

    /**
     * Returns the number of elements in this {@code ArrayList}.
     *
     * @return the number of elements in this {@code ArrayList}.
     */
    @Override public int size() {
        return size;
    }

    /**
     * 判断是否为空
     * @return
     */
    @Override public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 查找是否包含某个元素
     */
    @Override public boolean contains(Object object) {
        Object[] a = array;
        int s = size;
        if (object != null) {
            for (int i = 0; i < s; i++) {
                if (object.equals(a[i])) {
                    return true;
                }
            }
        } else {
            for (int i = 0; i < s; i++) {
                if (a[i] == null) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 从前向后查找元素所在的索引（如果查找的元素为null,则查找第一个为null的元素位置）。找不到返回－1
     */
    @Override public int indexOf(Object object) {
        Object[] a = array;
        int s = size;
        if (object != null) {
            for (int i = 0; i < s; i++) {
                if (object.equals(a[i])) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < s; i++) {
                if (a[i] == null) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 从后向前查找元素所在的索引。（如果查找的元素为null,则查找第一个为null的元素位置）。找不到返回－1
     * @param object
     * @return
     */
    @Override public int lastIndexOf(Object object) {
        Object[] a = array;
        if (object != null) {
            for (int i = size - 1; i >= 0; i--) {
                if (object.equals(a[i])) {
                    return i;
                }
            }
        } else {
            for (int i = size - 1; i >= 0; i--) {
                if (a[i] == null) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 删除列表中指定位置上的元素
     */
    @Override public E remove(int index) {
        Object[] a = array;
        int s = size;
        if (index >= s) {
            throwIndexOutOfBoundsException(index, s);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        // 将删除位置之后的元素拷贝并向前并挪动一个位置
        System.arraycopy(a, index + 1, a, index, --s - index);
        // 将数组末尾置空
        a[s] = null;  // Prevent memory leak
        size = s;
        modCount++;
        return result;
    }

    /**
     * 删除列表中首次出现的指定元素
     */
    @Override public boolean remove(Object object) {
        Object[] a = array;
        int s = size;
        if (object != null) {//如果指定查找的元素不为null
            for (int i = 0; i < s; i++) {//遍历查找
                if (object.equals(a[i])) {//如果找到
                    //将将该元素位置之后的元素拷贝并向前并挪动一个位置
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // 将数组末尾置空
                    size = s;
                    modCount++;
                    return true;
                }
            }
        } else {//如果指定查找的元素为null
            for (int i = 0; i < s; i++) {//遍历查找
                if (a[i] == null) {//如果第一个为null的元素
                    //将该为空的元素位置之后的元素，拷贝并向前并挪动一个位置
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;// 将数组末尾置空
                    size = s;
                    modCount++;
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 移除指定范围的元素
     * @param fromIndex
     * @param toIndex
     */
    @Override protected void removeRange(int fromIndex, int toIndex) {
        if (fromIndex == toIndex) {
            return;
        }
        Object[] a = array;
        int s = size;
        if (fromIndex >= s) {
            throw new IndexOutOfBoundsException("fromIndex " + fromIndex
                    + " >= size " + size);
        }
        if (toIndex > s) {
            throw new IndexOutOfBoundsException("toIndex " + toIndex
                    + " > size " + size);
        }
        if (fromIndex > toIndex) {
            throw new IndexOutOfBoundsException("fromIndex " + fromIndex
                    + " > toIndex " + toIndex);
        }

        System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
        int rangeSize = toIndex - fromIndex;
        Arrays.fill(a, s - rangeSize, s, null);
        size = s - rangeSize;
        modCount++;
    }

    /**
     * 修改方法
     */
    @Override public E set(int index, E object) {
        Object[] a = array;
        if (index >= size) {
            throwIndexOutOfBoundsException(index, size);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        a[index] = object;//修改index位置的数组元素
        return result;
    }

    /**
     * 创建一个新的Object数组，把array中的元素拷贝到数组中，然后返回
     */
    @Override public Object[] toArray() {
        int s = size;
        Object[] result = new Object[s];
        System.arraycopy(array, 0, result, 0, s);
        return result;
    }

    /**
     * 把array中的元素拷贝到传入的数组中，然后返回
     */
    @Override public <T> T[] toArray(T[] contents) {
        int s = size;
        if (contents.length < s) {
            @SuppressWarnings("unchecked") T[] newArray
                    = (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
            contents = newArray;
        }
        System.arraycopy(this.array, 0, contents, 0, s);
        if (contents.length > s) {
            contents[s] = null;
        }
        return contents;
    }

    /**
     * Sets the capacity of this {@code ArrayList} to be the same as the current
     * size.
     *
     * @see #size
     */
    public void trimToSize() {
        int s = size;
        if (s == array.length) {
            return;
        }
        if (s == 0) {
            array = EmptyArray.OBJECT;
        } else {
            Object[] newArray = new Object[s];
            System.arraycopy(array, 0, newArray, 0, s);
            array = newArray;
        }
        modCount++;
    }

    @Override public Iterator<E> iterator() {
        return new ArrayListIterator();
    }

    /**
     * 每个List都会有一个迭代器，里面包含hasNext方法，remove方法，next方法
     */
    private class ArrayListIterator implements Iterator<E> {
        /** Number of elements remaining in this iteration */
        private int remaining = size;// 剩余的数量

        /** Index of element that remove() would remove, or -1 if no such elt */
        private int removalIndex = -1;

        /** The expected modCount value */
        private int expectedModCount = modCount;

        public boolean hasNext() {// 下面是否还有元素
            return remaining != 0;
        }

        @SuppressWarnings("unchecked") public E next() {
            ArrayList<E> ourList = ArrayList.this;
            int rem = remaining;
            if (ourList.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (rem == 0) {
                throw new NoSuchElementException();
            }
            remaining = rem - 1;//剩余数量减一
            return (E) ourList.array[removalIndex = ourList.size - rem];
        }

        public void remove() {// 用迭代器进行删除，实际上创建一个新数组，删除然后进行copy
            Object[] a = array;
            int removalIdx = removalIndex;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (removalIdx < 0) {
                throw new IllegalStateException();
            }
            System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
            a[--size] = null;  // Prevent memory leak
            removalIndex = -1;
            expectedModCount = ++modCount;
        }
    }

    @Override public int hashCode() {
        Object[] a = array;
        int hashCode = 1;
        for (int i = 0, s = size; i < s; i++) {
            Object e = a[i];
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }

    @Override public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (!(o instanceof List)) {
            return false;
        }
        List<?> that = (List<?>) o;
        int s = size;
        if (that.size() != s) {
            return false;
        }
        Object[] a = array;
        if (that instanceof RandomAccess) {
            for (int i = 0; i < s; i++) {
                Object eThis = a[i];
                Object ethat = that.get(i);
                if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
                    return false;
                }
            }
        } else {  // Argument list is not random access; use its iterator
            Iterator<?> it = that.iterator();
            for (int i = 0; i < s; i++) {
                Object eThis = a[i];
                Object eThat = it.next();
                if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
                    return false;
                }
            }
        }
        return true;
    }

    private static final long serialVersionUID = 8683452581122892189L;

    private void writeObject(ObjectOutputStream stream) throws IOException {
        stream.defaultWriteObject();
        stream.writeInt(array.length);
        for (int i = 0; i < size; i++) {
            stream.writeObject(array[i]);
        }
    }

    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
        stream.defaultReadObject();
        int cap = stream.readInt();
        if (cap < size) {
            throw new InvalidObjectException(
                    "Capacity: " + cap + " < size: " + size);
        }
        array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]);
        for (int i = 0; i < size; i++) {
            array[i] = stream.readObject();
        }
    }
}

通过源码分析，我们可以看出ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长；我们可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，因此插入删除元素的效率低。