ArrayList / Vector 分析

ArrayList

ArrayList.png

ArrayList实现了Cloneable、List、RandomAccess、Serializable等, 可以进行clone、插入空数据、随机访问、支持序列化等。

相关属性

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

• elementData 用于存储数据的数组
• size 用于记录当前数组的长度
• modCount 继承自List 记录ArrayList 被修改的次数

构造方法

一、无参构造方法

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

将elementData 初始化为默认大小的空数组，此时的数组长度为1，size为0，在进行第一次add的时候，elementData会变成默认的大小10

二、一个参数 initialCapacity 的构造方法

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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, elementData 为空数组
初始化容量输入大于0，new 一个指定大小的数组，复制给elementData
其他容量抛出IllegalArgumentException

三、传入Collection对象的构造方法

/**
  * Constructs a list containing the elements of the specified
  * collection, in the order they are returned by the collection's
  * iterator.
  *
  * @param c the collection whose elements are to be placed into this list
  * @throws NullPointerException if the specified collection is null
  */
 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;
     }
 }

1. 将collection.toArray() 赋值给elementData, 此时为浅拷贝数组对象
   2）更新size 如果size 为0 则给elementData 赋值为空数组
   3）size 大于零的话判断传入的collection是否为Object[] 原型对象，如果不为原型对象则需要对对象进行Arrays.copyOf() 进行深拷贝

主要方法

一、add 方法

add 的方法有两个，一个函数签名为add(E e)

/**
  * Appends the specified element to the end of this list.
  *
  * @param e element to be appended to this list
  * @return <tt>true</tt> (as specified by {@link Collection#add})
  */
 public boolean add(E e) {
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     elementData[size++] = e;
     return true;
 }

函数的作用是将element添加到数组的最后面。

首先会调用ensureCapacityInternal判断新增element后当前数组的size是否会越界，如果超出当前数组的大小会对当前数组进行扩容，每次扩容的大小为当前的1.5倍（int newCapacity = oldCapacity + (oldCapacity >> 1);）,如果说容量超出了设定值MAX_ARRAY_SIZE 为 Integer.MAX_VALUE - 8 需要进行hugeCapacity 也就是进行大容量的扩容到Integer.MaxValue，同时每次add的时候会修改modCount，扩容check之后再进行数据的拷贝

另一个方法add(int index, E element)

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

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

这个方法是根据数组下标对elementData 进行插入，首先也会对数组进行扩容
然后调用jni的方法System.arrayCopy()将index下标之后的所有元素彤通通往后挪一位，再将数据拷贝到index的位置

System.arrayCopy方法：

| 参数 | 说明 |
| - | :-: | -: |
| src | 原数组|
| srcPos | 原数组起始位置 |
| dest | 目标数组 |
| destPos | 目标数组的起始位置 |
| length | 要复制的数组元素的数目 |

二、get 方法

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

    return elementData(index);
}

返回指定位置的元素

三、set方法

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

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

将指定位置的元素替换为新的element

四、remove方法

1）传入数组下标

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

将remove位置后的元素调用System.arraycopy往前挪动一位

2. 传入元素

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

foreach 遍历数组，发现传入元素相同的数组便调用System.arrayCopy 进行移除

五、subList

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

SubList 是ArrayList 的一个内部类，构造方法里面传入的第一个参数是this，实际上是返回了当前ArrayList 的部分视图，实际上是jvm中的同一份区域，如果说两者之间有任何一个进行了改变都会导致另一者的改变。

六、Iterator 方法

public Iterator<E> iterator() {
   return new Itr();
}

同样是构建一个Itr() 的内部类，通常的做法是使用next 指针进行遍历，在遍历的时候，可能会引发ConcurrentModificationException，当modCount 与 expectedCount 不一致的时候可能会引发改异常:

public E next() {
   checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

checkForCoModification():

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

序列化

由于ArrayList 是使用动态数组实现的，并不是所有的空间都被使用。因此elementData 使用了transient进行修饰, 可以防止序列化的时候没有被使用的空间被序列化。

transient Object[] elementData;

自定义的序列化与反序列化:

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    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();
    }
}

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        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 方法，使用这个替代默认的序列化

Vector

Vector 和 ArrayList 一样也是实现了List 接口，底层的数据结构也是同样的一个动态数组。区别是在add() 方法的时候使用synchronized进行同步写数据，但是开销较大，所以Vector 并不是一个并发容器

public synchronized boolean add(E e) {
   modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}