MENU

Java 集合类 - 源码分析(一)ArrayList

July 6, 2018 • Code

前言:ArrayList 是 Java 中非常重要的集合类,底层结构是数组前面 也分析过其扩容制机制,本文关注除扩容部分外其他比较重要的方法源码。

本文采用的 Java 版本为 1.8。

继承关系

ArrayList 的类层次结构图如下:

常用方法

构造方法

ArrayList 的构造方法有以下三个:

ArrayList():空参

public ArrayList() {
    // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个默认空的 Object 数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(int 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);
    }
}

ArrayList(Collection<? extends E> c):添加集合类元素

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;
    }
}
  • 通过 toArray() 方法获取集合类对应的数组。
  • 判断数组元素是否为空,如果不为空则进行数组类型判断,如果为空则直接赋值默认空对象数组。

需要进行数组类型判断是因为 elementData 引用虽然被声明为 Object[],但实际上数组的类型取决于真实运行时类型,在这里为 toArray() 方法的返回类型。而如果数组实际类型不为 Object[],可能导致元素添加失败,抛出 java.lang.ArrayStoreException 异常。
举个栗子:
Object[] os = new Father[5];
os[0] = new Other();
这一句就会报错,因为 os 实际的类型是 class [LArrayTest$Father。

add 方法

确定容量是否足够:

  • 如果足够,则直接将元素增加入对象数组 elementData 里。
  • 如果不够,则扩容,然后增加元素。
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal 方法

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

ensureExplicitCapacity 方法

如果容量不够这一次 add 操作,即 elementData 数组是全满的状态,则进入扩容操作。关于扩容在 之前的文章 中有详细的介绍,在这里不再赘述。

private void ensureExplicitCapacity(int minCapacity) {
    // 记录对内部结构的修改次数,增加删除元素及扩容操作都需要增加 1 
    modCount++;
    
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

Arrays.copyOf 方法

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

上面调用的 copyOf 方法

判断原来数组的类型是不是 Object:

  • 如果是,直接生成一个新 Object 数组。
  • 如果不是,则 Array.newInstance 方法(底层也是一个 native 方法)生成一个对应类对象类型的数组。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    

   T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    
    // 这个方法是一个 native 方法,
    // 表示从 original 数组的第 0 个位置开始复制到 copy 数组的 第 0 个位置,
    // 复制长度为Math.min(original.length, newLength)
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

remove 方法

remove(Object o):删除指定对象

对传入的对象进行判断:

  • 如果传入的对象为空,则进行遍历,当遇到第一个为空的元素时,进入 fastRemove 方法,而这个方法本质上就是将后面的数组组元素直接向前移动一位
    因为不用返回对象(null)。
  • 传入的对象不空,还是一个遍历,用 equals 方法逐一进行比较,如果相等则进入 fastRemove 方法,并返回 true。
public boolean remove(Object o) {
    // 如果传入的对象为空,则进行遍历,当遇到第一个为空的元素时,
    // 则进入 fastRemove,而这个方法本质上就是将后面的数组组元素直接向前移动一位
    // 因为不用返回对象(null)
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        //传入的对象不空,还是一个遍历,用 equals 方法逐一进行比较,如果相等则进入 fastRemove,并返回 true
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

remove(int index): 删除指定索引位置对象

public E remove(int index) {
    // 检查传入的索引是否大于数组元素的个数
    rangeCheck(index);
    
    // 修改次数 + 1
    modCount++;
    
    // 查询旧值
    E oldValue = elementData(index);
    
    // 元素移动的个数
    int numMoved = size - index - 1;
    // 移动数组后面的元素,即后面的元素向前移动一个单元
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最后的元素置 null,帮助 GC
    elementData[--size] = null; // clear to let GC do its work
    
    return oldValue;
}

rangeCheck 方法检查传入的索引是否大于数组元素的个数,如果大于则抛 IndexOutOfBoundsException。

数组的大小在大多数情况下是大于元素个数的,后面的一部分为 null。

toArray(T[] a): 返回包含所有 list 元素 的数组

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);
    
    // 如果传入的数组空间有剩余的话,则有用元素的后一位置为 null,
    // 这样做是可以帮助使用者判断数组的大小,可以看作是提供一个完结标识
    if (a.length > size)
        a[size] = null;
    return a;
}

小结

通过 ArrayList 的源码对其中一些方法进行分析,主要有:

  • 构造方法
  • 增加元素
  • 删除元素
  • 复制
Last Modified: July 12, 2018
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment