Java 源码--ArrayList

ArrayList类继承了AbstractList抽象类，AbstractList抽象类对于一些通用的方法提供了默认实现。ArrayList类实现了接口List、RandomAccess、Cloneable和Serializable。后三者都是语义标志接口，不提供任何实现，标记这个类具有某种功能。RandomAccess标记类具有随机访问的功能，Cloneable标记类具有克隆功能，Serializable标记类具有序列化功能。

ArrayList类底层是由数组实现的，使用一个 []类型的变量来保存这个list的值。这个值不参与序列化，类中重写了write ()和read ()方法来序列化该值。

transient  [] elementData;

变量size记录值的大小。

private int size;

ArrayList有两个构造方法——有参构造方法和无参构造方法。

无参构造时，将数组列表的值赋为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

private static final  [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

有参构造时，指定容量大于0，就构造一个指定容量大小的数组，如果指定容量为0，就将值赋为EMPTY_ELEMENTDATA。

private static final  [] EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new  [initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException(\"Illegal Capacity: \"+
                                           initialCapacity);
    }
}

也可以根据一个集合构造一个数组集合，将集合转为数组直接赋值给elementData。当值大小为0时，就将值赋为EMPTY_ELEMENTDATA。

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

那么，无参构造和有参构造产生的空值有什么区别呢？从表面上看来是一样的，在变量elementData上有这样一句注释，“ 添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。”

DEFAULT_CAPACITY指定为10。

private static final int DEFAULT_CAPACITY = 10;

注释的意思是说，无参构造产生的空值在第一次添加元素时，将容量扩展至10。那么我们来看下add方法。

add方法首先将数组容量加1，这就涉及到了ArrayList的扩容机制，我们一步步来看。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

首先，判断目前数组的值是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即该数组是不是无参构造出的空数组。如果是，就取DEFAULT_CAPACITY和minCapacity的最大值，否则就扩展至指定的容量。第一次添加元素时，minCapacity为1，也就是说将数组扩展至10，如果是有参构造的空数组，就扩展至1。

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

接下来要判断扩展的容量是否足够存放数组的值，足够存放就开始扩容工作。第一次添加元素时，数组长度为0，可以进入扩容工作。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow方法是ArrayList扩容机制的核心，可以看出，扩容的机制是扩展原来容量的0.5倍。如果扩容至1.5倍之后依旧无法达到指定容量大小或者大小超出了int类型的大小，就使用指定容量进行扩容。如果扩容容量大于数组最大容量，就扩容至Integer类型的最大值。最后重新申请一个数组，并进行数组的复制完成扩容工作。当第一次添加元素时，就数组的容量为0，扩容至1或10。

这里有一个疑问，既然ArrayList是数组来保存值的，数组的容量最大是Integer.MAX_VALUE - 8（查资料说是需要空间来保存一些头部信息），那么为什么ArrayList的容量还可以扩大至Integer.MAX_VALUE呢？

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

由此可以看出，EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是为了区分有参构造和无参构造的空数组，从而使用不同的扩容规则。

我们可以注意到，上面方法中有一个modCount变量加1的操作。这个变量是从父类AbstractList中继承来的，它标记一个list被修改的次数。它主要是为了在迭代器中判断list是否被其他操作改变，进入迭代器会保存一个modCount值的副本，如果modCount的值变了，就抛出异常。

protected transient int modCount = 0;

方法trimToSize将数组中多余容量释放。当使用容量小于数组容量时，如果使用容量为0，将数组设为空值，否则重新生成一个长度为size的数组。

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

size方法可以获取list的大小。

public int size() {
    return size;
}

isEmpty方法判断list是否为空，即size是否为0.

public boolean isEmpty() {
    return size == 0;
}

contains方法判断数组是否包含参数。如果参数o在数组的位置不小于0，就说明数组中存在参数。

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

indexOf方法判断参数在数组中的位置。如果参数o为null，那么在数组中找到一个null值的位置就好，不为空就是用equals方法找到数组中o的位置，找不到就返回-1。

public int indexOf(  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;
}

lastIndexOf方法从后往前遍历，判断参数在数组中的位置。

public int lastIndexOf(  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方法克隆一个list。注意，该克隆是浅克隆，数组元素并没有复制。

public   clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

toArray方法将list转为数组。如果参数a的长度不够容纳list元素，就重新生成一个数组，否则就直接复制元素。a中有空余位置的话将size位置置为null。

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

@SuppressWarnings(\"unchecked\")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

get方法返回指定位置的元素。首先检查index是否越界，然后返回数组index位置的元素。

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

    return elementData(index);
}

@SuppressWarnings(\"unchecked\")
E elementData(int index) {
    return (E) elementData[index];
}

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

set方法设置指定位置的元素。首先检查index是否越界，然后拿到index位置的旧值，将index位置的值设为新值，最后返回旧值。

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

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

add方法向list中添加元素。不指定元素添加位置时默认添加到数组末尾，首先确保数组的容量，然后在数组后面添加一个元素，最后返回true。指定元素添加位置时，首先检查指定位置是否越界，然后确保数组的容量，然后将index以及之后的元素向后移动一位，将index位置设为指定元素，最后返回true。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

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

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

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

remove方法移除指定位置的元素或移除指定元素。当指定的是元素位置时，先检查指定位置是否越界，然后获取指定位置的旧值，将指定位置之后的元素向前移动一个位置，然后将最后一位设为null，最后返回旧值。当指定的是元素时，就先判断元素的位置，移除那个位置元素，最后返回布尔值。

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

public boolean remove(  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方法清除list中的元素。将数组中的每个元素设为null，并将大小设为0。

public void clear() {
    modCount++;

    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

addAll方法向list中添加集合。不指定位置时，默认向末尾添加集合元素。

public boolean addAll(Collection<? extends E> c) {
     [] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

     [] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  

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

removeAll方法移除指定集合中的所有元素，retainAll方法保留指定集合中的所有元素。这两个方法类似，只是逻辑是反的，Java设计者很巧妙的运用了一个boolean类型的参数来区分两种逻辑，以便使同一个方法。在try中的for循环就已经将需要留下的元素放到了数组的前一部分，即w位置之前。注释说contains方法可能会有异常，当异常发生，就将没有遍历到的元素全部留下，这个逻辑我也不太明白。最后将w位置之后的元素设为null，返回布尔值。

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

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

private boolean batchRemove(Collection<?> c, boolean complement) {
    final  [] 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 {
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

forEach方法可以使用lambda表达对每一个元素进行相同的操作。在操作之前，会先拿到数组修改的次数，然后重新申请一个与list数组元素相同的数组进行操作。注意，此复制是浅复制，两个数组共用一套元素。最后判断list是否被其他操作改变了，如果被改变了就抛出异常。

@Override
public void forEach(Consumer<? super E> action) {
     s.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings(\"unchecked\")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    

					

						
继续阅读与本文标签相同的文章
						

														无标签