Java源码分析1-ArrayList

以下内容基于JDK1.8

概述

• 用大小可变数组存储数据的方式实现了List接口
• 实现了所有List相关的操作
• 接收所有类型元素,包括Null
• 提供了非同步,类似Vector的方法来操作内部数组(用于存储列表)的大小

继承关系图

继承关系图

相关属性

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

    /**
     * 空数组，如果传入的容量为0或传入集合元素个数为0时使用
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 空数据,当调用new ArrayList()构造函数时使用
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储元素数据,以下简称存储数组
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 集合中元素个数
     * @serial
     */
    private int size;

---

1. 存储数组Object[] elementData

• 用于存储放入到ArrayList的元素,所有的增,删,查,改都是基于这个数组进行的
• 每次新增元素时都会检查数据的容量是否够用,若不够用则将存储数据的长度扩容至1.5倍数组长度
• 每次扩容需要对整个数组中的元素进行复制

比较特殊的是修饰符transient,这个之前未接触过,有必要了解下

• 1.1 transient修饰符
  transient作用是让被修饰的成员在对象进行序列化操作时不被序列化
  但作为ArrayList的核心elementData,其不被序列化那反序列化的的时候数据不就丢失了吗?
  其原因是ArrayList重写了writeObject方法,其在对象实例被序列化时调用

• 1.2 将对象实例写入流中writeObject(java.io.ObjectOutputStream s)

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    //写入非transient修饰的成员变量
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    //将大小写为与克隆行为兼容的容量
    s.writeInt(size);

    // Write out all elements in the proper order.
    //将存储数组中的元素写入
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    //判断对象实例是否被篡改
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

这么做的目的是因为存储数组的长度不是真实的元素个数,size才是.
如果不声明elementData为transient,那么在存储数组中(elementData.length-size)个空间是未被使用的,
所以需要将其声明为transient并重写writeObject方法,进而节省存储空间

• 1.3 从流中读取对象实例readObject(java.io.ObjectInputStream s)

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
   
   //默认存储数组为空数组
   elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    //读取ArrayList对应的大小等其他属性
    s.defaultReadObject();

    // Read in capacity
    //读取容量
    s.readInt(); // ignored
    
    if (size > 0) {
        //与clone（）类似，根据大小而不是容量分配数组
        //确保容量最终,肯定会发送扩容
        ensureCapacityInternal(size);
        
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            //将流中的元素依次写入到存储数组中
            a[i] = s.readObject();
        }
    }
}

还有个问题,writeObject和readObject方法都是私有的,在ArrayList或者整个rt.jar都没有找到调用记录,那么在序列化的时候是如何被调用到的呢?

public class ArrayListTest4 {

    public static void main(String[] args) throws IOException, ClassNotFoundException {
    
        List<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
    
        //将对象序列化到字节数组中
        ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
        ObjectOutputStream objectOutputStream = new ObjectOutputStream(byteArrayOutputStream);
        objectOutputStream.writeObject(list2);
        byte[] byteArray = byteArrayOutputStream.toByteArray();
    
    
        //从字节数组中反序列化对象
        ObjectInputStream inputStream = new ObjectInputStream(new ByteArrayInputStream(byteArray));
        Object o = inputStream.readObject();
        System.out.println(o.toString());
    }
}

通过调试上述代码可知,将对象序列化时的调用顺序为:
oos---ObjectOutputStream
osc---ObjectStreamClass
oos.writeObject--->oos.writeObject0--->osc.lookup--->oos.writeOrdinaryObject--->oos.writeSerialData--->osc.invokeWriteObject->ArrayList.writeObject
其中,ArrayList.writeObject是通过反射的方式调用的
而为什么能找到writeObject这个方法呢?答案就在ObjectOutputStream的私有构造方法中,上代码

private ObjectStreamClass(final Class<?> cl) {
    this.cl = cl;
    name = cl.getName();
    isProxy = Proxy.isProxyClass(cl);
    isEnum = Enum.class.isAssignableFrom(cl);
    serializable = Serializable.class.isAssignableFrom(cl);
    externalizable = Externalizable.class.isAssignableFrom(cl);

    Class<?> superCl = cl.getSuperclass();
    superDesc = (superCl != null) ? lookup(superCl, false) : null;
    localDesc = this;

    if (serializable) {
        AccessController.doPrivileged(new PrivilegedAction<Void>() {
            public Void run() {
                if (isEnum) {
                    suid = Long.valueOf(0);
                    fields = NO_FIELDS;
                    return null;
                }
                if (cl.isArray()) {
                    fields = NO_FIELDS;
                    return null;
                }

                suid = getDeclaredSUID(cl);
                try {
                    fields = getSerialFields(cl);
                    computeFieldOffsets();
                } catch (InvalidClassException e) {
                    serializeEx = deserializeEx =
                        new ExceptionInfo(e.classname, e.getMessage());
                    fields = NO_FIELDS;
                }

                if (externalizable) {
                    cons = getExternalizableConstructor(cl);
                } else {
                    cons = getSerializableConstructor(cl);
                    //通过'writeObject'获取到类重写的序列化方法
                    writeObjectMethod = getPrivateMethod(cl, "writeObject",
                        new Class<?>[] { ObjectOutputStream.class },
                        Void.TYPE);
                    //通过'readObject'获取到类重写的反序列化方法
                    readObjectMethod = getPrivateMethod(cl, "readObject",
                        new Class<?>[] { ObjectInputStream.class },
                        Void.TYPE);
                    readObjectNoDataMethod = getPrivateMethod(
                        cl, "readObjectNoData", null, Void.TYPE);
                    hasWriteObjectData = (writeObjectMethod != null);
                }
                writeReplaceMethod = getInheritableMethod(
                    cl, "writeReplace", null, Object.class);
                readResolveMethod = getInheritableMethod(
                    cl, "readResolve", null, Object.class);
                return null;
            }
        });
    } else {
        suid = Long.valueOf(0);
        fields = NO_FIELDS;
    }

    try {
        fieldRefl = getReflector(fields, this);
    } catch (InvalidClassException ex) {
        // field mismatches impossible when matching local fields vs. self
        throw new InternalError(ex);
    }

    if (deserializeEx == null) {
        if (isEnum) {
            deserializeEx = new ExceptionInfo(name, "enum type");
        } else if (cons == null) {
            deserializeEx = new ExceptionInfo(name, "no valid constructor");
        }
    }
    for (int i = 0; i < fields.length; i++) {
        if (fields[i].getField() == null) {
            defaultSerializeEx = new ExceptionInfo(
                name, "unmatched serializable field(s) declared");
        }
    }
    initialized = true;
}

---

构造函数

1. 无参构造函数

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

此时的操作有:

• 设置存储元素数组初始值为空数组
• 元素初始容量为10

2. 指定数组容量构造函数

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

此时的操作有:

• 当传入容量大于0时,初始化存储数组的大小为传入容量
• 当传入容量为0时,初始化存储数组的大小为空数组
• 当传入容量小于0时,抛出参数异常IllegalArgumentException

3. 传入参数为Collection子类的构造函数

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方法转为数据后赋值给存储数组
• 若存储数组的长度为0,则用EMPTY_ELEMENTDATA空数组的值替换掉存储数组
• 若存储数组的长度不为0,则判断存储数组对应的Class类是否为Object[].class即[Ljava.lang.Object,如果不是,则调用Arrays.copyOf方法将传入数组复制对应的Class类的数组后再赋值给存储数组
  此处有两个疑问
  1).为什么要elementData.getClass() != Object[].class)这个判断呢?
  已知的就有一种情形,如下示例

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArrayListTest1 {

    public static void main(String[] args) {
        List<String> list1 = Arrays.asList("test", "s");
        System.out.println(list1.getClass() 
            +" toArray.getClass="+ list1.toArray().getClass());

        List<String> list2 = new ArrayList<>();
        list2.add("test");
        System.out.println(list2.getClass() 
            +" toArray.getClass="+ list2.toArray().getClass());
    }
}

执行结果

class java.util.Arrays$ArrayList toArray.getClass=class [Ljava.lang.String;
class java.util.ArrayList toArray.getClass=class [Ljava.lang.Object;

通过Arrays.asList生成的List虽然也叫ArrayList但却是Arrays.java里面的一个内部类,且通过其toArray()方法返回的数组对应的Class类为[Ljava.lang.String

2).为什么要调用Arrays.copyOf方法覆盖原存储数组呢,查了下旁边的注释c.toArray might (incorrectly) not return Object[] (see 6260652),正是由于ArrayList是通过数组存储数据,当数组中元素在进行向下转型时由于不安全而抛出异常的bug
如下所示

public class ArrayListTest2 {

    public static void main(String[] args) {

        Object[] objects = new Object[2];
        System.out.println(objects.getClass());

        SubObject[] subObjects = new SubObject[2];
        System.out.println(subObjects.getClass());

        objects = subObjects;
        objects[0] = new Object();
    }
}
class SubObject{}

执行结果

class [Ljava.lang.Object;
class [Lcom.learn.list.SubObject;
Exception in thread "main" java.lang.ArrayStoreException: java.lang.Object
at com.learn.list.ArrayListTest2.main(ArrayListTest2.java:21)

综上可知,代码

if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);

是为了避免在通过传入Collection子类构造出的ArrayList实例在新增元素时,由于传入元素是存储数组类型父类而发生向下转型而抛出异常

常用方法

1. 在末尾添加单个元素add(E e)方法

public boolean add(E e) {
    //在元素个数+1的情况下确保容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //将元素添加存储数组索引为size+1出,且数组元素个数+1
    elementData[size++] = e;
    return true;
}

重点都在ensureCapacityInternal方法中,那么就重点分析下吧

• 1.1 ensureCapacityInternal(int minCapacity)方法

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //当存储数组为空数组时,从默认初试容量DEFAULT_CAPACITY和传入容量minCapacity中取最大值
        //赋给传入容量
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //确保明确的容量
    ensureExplicitCapacity(minCapacity);
}

继续分析ensureExplicitCapacity方法

• 1.2 ensureExplicitCapacity(int minCapacity)方法
  该方法主要作用是比较传入容量和存储数组长度,如果大于则调用扩容方法

private void ensureExplicitCapacity(int minCapacity) {
    //定义于ArrayList的父类AbstractList，用于存储结构修改次数
    modCount++;

    //判断是否需要扩容
    if (minCapacity - elementData.length > 0){
        //如果传入容量大于存储数组长度,则扩容
        grow(minCapacity);
    }   
}

接着分析grow扩容方法

• 1.3 grow(int minCapacity)扩容方法

private void grow(int minCapacity) {
    //存储数组长度
    int oldCapacity = elementData.length;
    //新容量=存储数组长度+存储数组长度由移一位(/2),及新容量=1.5倍存储数组长度
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0){
        //如果传入容量大于新容量,则新容量=传入容量
        newCapacity = minCapacity;
    }
    if (newCapacity - MAX_ARRAY_SIZE > 0){
        //如果新容量大于Integer.MAX_VALUE - 8,则获取最大容量
        newCapacity = hugeCapacity(minCapacity);
    }
        
    //将原存储数组中的数据复制到新数组(长度=新容量)中后赋给存储数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 1.4 hugeCapacity(int minCapacity)获取超大容量方法

private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0){
      //此时传入容量小于0说明超过Integer的最大值,即内存溢出
      throw new OutOfMemoryError();
  }
  //你懂的
  return (minCapacity > MAX_ARRAY_SIZE) ?
      Integer.MAX_VALUE :
      MAX_ARRAY_SIZE;
}

通过分析完add(E e),可以得到的结论是

• 如果存储数组中存储元素较多时,频繁的扩宽会影响添加元素的性能
• 在创建ArrayList实例时,如果已知元素个数,最好通过new ArrayList(int initialCapacity)构造函数来创建,既不浪费空间,又不影响性能
• 该方法是非线程安全的,并发添加的时候存在元素被覆盖的情况,即元素个数<调用add()方法次数

---

2. 在指定位置添加单个元素add(int index, E element)方法

public void add(int index, E element) {
      //检查传入索引是否越界
      rangeCheckForAdd(index);

      //在元素个数+1的情况下确保容量足够,见1.1
      ensureCapacityInternal(size + 1);  // Increments modCount!!
     //数组复制方法,即将存储元素中的元素从index开始后移一位,给新增元素腾位置
      System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
      
      //将传入元素的值放入数组中的指定位置
      elementData[index] = element;
      size++;
  }

先来看看rangeCheckForAdd方法

• 2.1 rangeCheckForAdd(index)索引校验

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0){
        //若传入索引是否大于当前元素个数或者小于0,则抛出数组越界异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

• 2.2 System.arraycopy数组复制方法
  这是Java提供的native方法,具体实现细节不可见,但是可以从其注释中了解其作用
  将src[srcPos]至src[srcPos+length]间的元素复制到dest[destPos]至dest[destPos+length]间

/***
* src-源数组
* srcPos-原数组复制起始位置
* dest-目标数据
* destPos-目标数组存放起始位置
* length-复制元素个数
*/
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

通过分析完add(int index, E element),可以得到的结论是

• 当存储数组中存储元素较多且在指定位置越靠前,添加元素的性能将越低,因为需要将之后的元素通通往后挪一个位置,这与频繁调用扩容方法是一个意思
• 该方法是非线程安全的,并发调用该方法,可能会导致数据被覆盖而丢失数据

---

3. 在末尾添加Collection子类 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;
}

由此可见,
该方法也是非线程安全的,并发操作存在数据缺失的问题

---

4. 删除指定元素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);
     }
     //将存储数据末尾元素置为null,尽快让其被GC回收释放空间     
     elementData[--size] = null; // clear to let GC do its work

     return oldValue;
}

同理

• 若移除元素越靠前,效率越低
  -该方法也是非线程安全的,并发操作时存在数据丢失的情形

---

5. 通过对象引用删除数据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 {
        //如果对象引用不为空,则通过其equals比较是否,若为true,则删除
      for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {
            fastRemove(index);
            return true;
        }
    }
    return false;
}

5.1 快速删除fastRemove(int index)方法

private void fastRemove(int index) {
     modCount++;
     //计算需要移动格式
     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
}

综上可知

• 每执行一次删除,其后的所有元素都要向前挪动一位
• 执行为一次删除,至少需要对存储数据中的元素进行一次迭代
• 当对象引用在存储数据中的位置越靠前,效率越低

---

6. 通过Collection子类删除元素removeAll(Collection<?> c)方法

public boolean removeAll(Collection<?> c) {
    //判断请求是否为空
    Objects.requireNonNull(c);
    //匹配删除方法
    return batchRemove(c, false);
}

6.1 匹配删除batchRemove(Collection<?> c, boolean complement)方法

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        //迭代存储数据
        for (; r < size; r++){
            //判断传入Collection子类对象实例中是否未包含存储元素对应的值,
            //由于complement=false,即从存储数组中找出与Collection子类对象实例中不一致的值
            //那么当迭代完后,索引小于w的数据是不匹配的,不需要删除,而>=w的则需要删除,好巧妙啊
            if (c.contains(elementData[r]) == complement){
                elementData[w++] = elementData[r];
            }
        }     
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //当上述迭代完成后,r=size,除非c.contains()发生异常,否则不可能出现r != size
        if (r != size) {
            //将未迭代的元素向前挪动r-w个位置,与之前不匹配的合成一个完成的存储数组
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            //说明传入实例中的元素与存储数组中的元素不全匹配
            // clear to let GC do its work
            for (int i = w; i < size; i++){
                //将大于等会w之后的元素清空,好让GC尽快回收
                elementData[i] = null;
            }
            
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

7. 删除指定区间元素removeRange(int fromIndex, int toIndex)方法
   其策略是现将索引为toIndex之后的元素移到fromIndex之后,然后再将索引为size - (toIndex-fromIndex)及之后的元素删除

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    //计算需要移动元素个数
    int numMoved = size - toIndex;
    //将索引为toIndex及之后的元素移动到fromIndex之后
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    //计算删除后的存储元素个数newSize
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        //将newSize-size之间的元素删除
        elementData[i] = null;
    }
    size = newSize;
}