java源码赏析--java.util.ArrayList

作者: faris_shi | 来源:发表于2018-02-07 22:03 被阅读42次

1. 简介

ArrayList 是可以动态增长和缩减的索引序列，它是基于数组实现的 List 类。

该类封装了一个动态再分配的 Object[] 数组，每一个类对象都有一个 capacity 属性，表示它们所封装的 Object[] 数组的长度，当向 ArrayList 中添加元素时，该属性值会自动增加。如果向 ArrayList 中添加大量元素，可使用 ensureCapacity 方法一次性增加 capacity ，可以减少增加重分配的次数提高性能。

ArrayList 的用法和 Vector 相类似，但是 Vector 是一个较老的集合，具有很多缺点，不建议使用。另外，ArrayList 和 Vector 的区别是：ArrayList 是线程不安全的，当多条线程访问同一个 ArrayList 集合时，程序需要手动保证该集合的同步性，而 Vector 则是线程安全的。

size、isEmpty、get、set、iterator和listIterator操作的运行时间是常量。add操作对于添加n个元素，需要O(n)的时间。其他的操作需要线性时间。

1.1 继承关系

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

继承 AbstractList 抽象父类，AbstractList提供了List接口的默认实现（个别方法为抽象方法）。
实现了 List 接口（规定了 List 的操作规范），List接口（extends Collection）定义了列表必须实现的方法。
RandomAccess（可随机访问），是一个标记接口，用来标记可适用与随机访问算法的类。
Cloneable（可拷贝），可以调用Object.clone方法返回该对象的浅拷贝。
Serializable（可序列化）。

2. 源码分析

2.1 属性

//默认初始容量  
private static final int DEFAULT_CAPACITY = 10;
  
//空数组  
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认空数组   
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 不会被序列化  
transient Object[] elementData;  
  
//ArrayList实际元素容量
private int size;

//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList的默认容量DEFAULT_CAPACITY为10。
数据存放在elementData中，且访问级别为包内私有，是为了使内部类能够访问到其中的元素。并且被标记为transient，也就意味着在序列化的时候，此字段是不会被序列化的。
size表示数组中元素的个数
EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了在构造函数中初始化elementData使用的。
MAX_ARRAY_SIZE为ArrayList最大分配容量。

2.2 构造函数

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

无参构造函数，elementData中没有元素，size为0，且elementData的长度也为0。使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA为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);
    }
}

elementData中没有元素，size为0，不过elementData的长度有可能不同。使用EMPTY_ELEMENTDATA为elementData赋值。

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

首先将集合c转化为数组，然后检查转化的类型，如果不是 Object[] 类型，使用 Arrays 类中的 copyOf 方法进行复制；同时，如果 c 中没有元素，使用 EMPTY_ELEMENTDATA 初始化。

2.3 主要方法

2.3.1 `boolean add(E e)`

确保容量足够后，在尾部添加一个元素

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

动态扩容

ensureCapacityInternal 在 Arraylist 中多次使用，着重理解。

private void ensureCapacityInternal(int minCapacity) {
    
    //第一次添加元素时，如果是无参构造函数构造而来，那么所需最小容量为DEFAULT_CAPACITY
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

上面代码中if判断为了区分对象是由哪一种构造函数构造而来。第一次添加元素时需要确定最小扩容容量。而DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA用来区分三个构造函数。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //列表修改次数加1

    //如果所需最小容量大于数组长度时，才许真正扩容。
    if (minCapacity - elementData.length > 0){
        grow(minCapacity);
    }
}

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);
    }
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

一般正常情况下，新的容量一般为旧容量的1.5倍(oldCapacity + (oldCapacity >> 1))。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) {// 这种情况，如何出现？
        throw new OutOfMemoryError();
    }
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :  MAX_ARRAY_SIZE;
}

minCapacity 在超出最大限制时允许达到 Integer.MAX_VALUE，而不仅仅是Integer.MAX_VALUE - 8

2.3.2 `void ensureCapacity(int minCapacity)`

供外部调用的扩容方法。

在大致了解List大小时，可用此方法一次性增加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);
    }
}

如果是通过无参构造函数构造且elementData中没有元素，则不需要扩容。
在ensureExplicitCapacity方法中，如果扩容大小小于elementData长度，则不需要扩容。

2.3.3 `void add(int index, E element)`

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

检查 index 是否数组越界。

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

private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

先调用 rangeCheckForAdd 检查索引是否合法。
合法再调用上面讲过的 ensureCapacityInternal 执行扩容。
调用系统的 arraycopy 函数将索引处及其后的元素后移一位。
在 index 处插入该元素。

add(int index, E element)方法太耗时，主要体现在arraycopy上，一般别用。

2.3.4 `boolean addAll(Collection<? extends E> c)`

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

将 c 转换为数组 a。
调用 ensureCapacityInternal 动态扩容。
调用系统函数 arraycopy。
增加 elementData 的 size。
有意思的小细节，numNew != 0，则返回 true。

疑惑点

为什么不从一开始就判断 numNew 的值呢，如果等于0，直接返回，后面的函数也就不用执行了？

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

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

和 add(int index, E element) 一样，先调用 rangeCheckForAdd 检查索引合法性。
将 c 转换为数组 a。
调用 ensureCapacityInternal 扩容。
如果插入位置不是 Arraylist 的末尾，则调用 arraycopy 将索引及其后的元素后移。
将 a 的元素 arraycopy 到 elementData 中。
增加 size。
numNew != 0，则返回true。

2.3.5 `E get(int index)`

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

    return elementData(index);
}

注意和 rangeCheckForAdd的不同之处。

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

检查索引合法性。
返回指定数据。

2.3.6 `void clear()`

public void clear() {
    modCount++;

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

    size = 0;
}

从结构上修改此列表的次数加1；
for循环将每个元素置空；
size 置为0，elementData 的长度并没有修改，如果确定不再修改 list 内容之后最好调用 trimToSize 来释放掉一些空间）。

2.3.7 `void trimToSize()`

返回一个新数组，新数组不含null，数组的 size 和 elementData.length 相等，以节省空间。此函数可避免 size 很小但 elementData.length 很大的情况。

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

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

ArrayList 中可以添加 null，且可以在任意位置。

2.3.9 `boolean contains(Object o)`

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

不建议使用 contains(Object o) 方法。效率极差。原因是通过for循环分别 equals

2.3.10 `boolean containsAll(Collection<?> c)`

继承java.util.AbstractCollection 的 containsAll

public boolean containsAll(Collection<?> c) {
    for (Object e : c) {
        if (!contains(e)) {
            return false;
        }
    }
    return true;
}

不建议使用，效率更差。

2.3.11 `int hashCode()`

继承 java.util.AbstractList 的 hashCode

public int hashCode() {
    int hashCode = 1;
    for (E e : this) {
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    }
    return hashCode;
}

2.3.12 `Object clone()`

返回ArrayList实例的浅拷贝

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

2.3.13 `boolean remove(int 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;
}

检查索引合法性
通过 System.arraycopy 挪动数组
size减一，并将elementData最后设为null

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

由于 ArrayList 中可以存储 null，所以需要判断参数 o 是否为空的判断。

直观从代码上看，不建议使用此方法删除对象，性能太差。建议使用 boolean 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
}

需要注意 fastRemove(int index) 与 boolean remove(int index)的区别，仅仅是没有返回值，作者为什么将相同的代码写两遍呢？

2.3.15 `boolean removeAll(Collection<?> c)`

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

判断对象是否为空

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

batchRemove 这个类中最精妙的代码

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;// r 用来遍历整个数组的索引  w 用来标记需要替换的索引
    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) { // 如果 w != size， 则说明 w之后的元素都是需要丢弃掉的。而如果 w == size， 则说明没有发生替换，不需要删除。
            // clear to let GC do its work
            for (int i = w; i < size; i++) {
                elementData[i] = null;
            }
            modCount += size - w; //本次修改次数就应该是 size - w
            size = w; //替换次数 = size
            modified = true;
        }
    }
    return modified;
}

2.3.16 `boolean retainAll(Collection<?> c)`

保留 c 中的元素，与 remoteAll 的区别在于 batchRemove(c, complement)。

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

2.3.17 `E set(int index, E element)`

替换对应索引的元素

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

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

2.3.18 `Object[] toArray()`

浅拷贝

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

2.3.19 `<T> T[] toArray(T[] a)`

public <T> T[] toArray(T[] a) {
    if (a.length < size){
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size){
        a[size] = null;
    }
    return a;
}

2.3.20 `void sort(Comparator<? super E> c)`

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

ConcurrentModificationException 是用来判断在数组排序时是否被修改。

java源码赏析--java.util.ArrayList

1. 简介

1.1 继承关系

2. 源码分析

2.1 属性

2.2 构造函数

2.3 主要方法

2.3.1 `boolean add(E e)`

动态扩容

2.3.2 `void ensureCapacity(int minCapacity)`

2.3.3 `void add(int index, E element)`

2.3.4 `boolean addAll(Collection<? extends E> c)`

2.3.5 `boolean addAll(int index, Collection<? extends E> c)`

2.3.5 `E get(int index)`

2.3.6 `void clear()`

2.3.7 `void trimToSize()`

2.3.8 `int indexOf(Object o)`

2.3.9 `boolean contains(Object o)`

2.3.10 `boolean containsAll(Collection<?> c)`

2.3.11 `int hashCode()`

2.3.12 `Object clone()`

2.3.13 `boolean remove(int index)`

2.3.14 `boolean remove(Object o)`

2.3.15 `boolean removeAll(Collection<?> c)`

2.3.16 `boolean retainAll(Collection<?> c)`

2.3.17 `E set(int index, E element)`

2.3.18 `Object[] toArray()`

2.3.19 `<T> T[] toArray(T[] a)`

2.3.20 `void sort(Comparator<? super E> c)`

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

java源码赏析--java.util.ArrayList

1. 简介

1.1 继承关系

2. 源码分析

2.1 属性

2.2 构造函数

2.3 主要方法

2.3.1 boolean add(E e)

动态扩容

2.3.2 void ensureCapacity(int minCapacity)

2.3.3 void add(int index, E element)

2.3.4 boolean addAll(Collection<? extends E> c)

2.3.5 boolean addAll(int index, Collection<? extends E> c)

2.3.5 E get(int index)

2.3.6 void clear()

2.3.7 void trimToSize()

2.3.8 int indexOf(Object o)

2.3.9 boolean contains(Object o)

2.3.10 boolean containsAll(Collection<?> c)

2.3.11 int hashCode()

2.3.12 Object clone()

2.3.13 boolean remove(int index)

2.3.14 boolean remove(Object o)

2.3.15 boolean removeAll(Collection<?> c)

2.3.16 boolean retainAll(Collection<?> c)

2.3.17 E set(int index, E element)

2.3.18 Object[] toArray()

2.3.19 <T> T[] toArray(T[] a)

2.3.20 void sort(Comparator<? super E> c)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

2.3.1 `boolean add(E e)`

2.3.2 `void ensureCapacity(int minCapacity)`

2.3.3 `void add(int index, E element)`

2.3.4 `boolean addAll(Collection<? extends E> c)`

2.3.5 `boolean addAll(int index, Collection<? extends E> c)`

2.3.5 `E get(int index)`

2.3.6 `void clear()`

2.3.7 `void trimToSize()`

2.3.8 `int indexOf(Object o)`

2.3.9 `boolean contains(Object o)`

2.3.10 `boolean containsAll(Collection<?> c)`

2.3.11 `int hashCode()`

2.3.12 `Object clone()`

2.3.13 `boolean remove(int index)`

2.3.14 `boolean remove(Object o)`

2.3.15 `boolean removeAll(Collection<?> c)`

2.3.16 `boolean retainAll(Collection<?> c)`

2.3.17 `E set(int index, E element)`

2.3.18 `Object[] toArray()`

2.3.19 `<T> T[] toArray(T[] a)`

2.3.20 `void sort(Comparator<? super E> c)`