ArrayList源码解析

2018-11-22 本文已影响6人 Duzzi

属性分析

    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * 用于默认大小的空实例的共享空数组实例。
     * 我们将其与EMPTY_ELEMENTDATA区分开来，以便在添加第一个元素时知道要扩展多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区。
     * ArrayList的容量是此数组缓冲区的长度。
     * 添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * 的空ArrayList都将扩展为DEFAULT_CAPACITY。
     */
    // Android-note: Also accessed from java.util.Collections
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * arrayList的元素个数
     */
    private int size;
    /**
     * 要分配的最大数组大小。 
     * 有些VM会在数组中保留一些标题字。
     * 尝试分配更大的数组可能会导致OutOfMemoryError：请求的数组大小超过VM限制
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法

    /**
     * 带参数构造方法
     * @param initialCapacity 初始容量
     */
    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() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 带collection的构造方法
     * @param c
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //c.toArray返回的不一定是Object[],是个bug，参见https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

其他方法

/**
 * 去除空余部分，将数组的大小设置为元素的个数
 */
public void trimToSize() {
    //修改次数加1
    modCount++;
    //如果元素的个数小于数组的长度
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

add相关方法

/**
 * 在list的尾部追加一个元素
 * @param e
 * @return
 */
public boolean add(E e) {
    //判断是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/**
 * 在指定位置插入一个元素
 * @param index
 * @param element
 */
public void add(int index, E element) {
    //判断插入的位置是否正确
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //判断是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //对index之后的元素拷贝到index+1的位置之后
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //对index位置的元素重新赋值
    elementData[index] = element;
    //list的大小+1
    size++;
}

扩容相关方法

/**
 * 确保容量的内部实现
 * @param minCapacity
 */
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //取元素个数和默认容量两者中的最大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

/**
 * 确定明确的容量
 * @param minCapacity
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 溢出考虑
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 增加容量以确保它至少可以保存最小容量参数指定的数量的元素。
 */
private void grow(int minCapacity) {
    // 溢出判断代码
    int oldCapacity = elementData.length;
    //扩容操作，oldCapacity >> 1右移一位即二进制数右移一位，相当于除以2，即扩容为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //这里考虑了可能会溢出，因为Integer.MAX_VALUE 再继续增加会导致对应的补码的符号位数变为负数
    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);
}

/**
 * 取最大容量
 * @param minCapacity
 * @return
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //最多只能是Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

对象是否存在、索引判断

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

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++)
            //注意这里是直接通过equals判断两个对象是否相等，对于特定需求，我们需要重写equals方法
            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;
}

clone（浅拷贝）

/**
 * 返回此实例的浅拷贝。（元素本身不会被拷贝，拷贝是对象的引用）
 * @return
 */
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);
    }
}

深拷贝（重新创建数组）

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

移除

/**
 * 删除此列表中指定位置的元素。将后续元素向左移位（从索引中减去一个）。
 * @param index
 * @return
 */
public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) 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;
}

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

/**
 * 私有删除方法，它跳过边界检查但不返回删除的值。
 * @param 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; // 设置为null确保GC正常回收
}

小结

ArrayList实现了序列化(writeObject)和反序列化(readObject)。
ArrayList基于数组方式实现，无容量的限制（如果可以，会扩容到原来的1.5倍，否在最大为Integer.MAX_VALUE）
添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。
线程不安全
add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）
remove(Object o)需要遍历数组判断是否包含该对象
remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高
contains(E)需要遍历数组判断是否包含该对象
使用iterator遍历可能会引发多线程异常

ArrayList源码解析

猜你喜欢

热点阅读