Java集合ArrayList

ArrayList Java 中的动态数组实现，默认容量为10，最大容量为Integer.MAX_VALUE

基于数组实现，所以拥有数组的特点：数据连续，随机访问速度快（实现了RandomAccess标记接口，表明了随机读取的能力）；同样的，因为Java中的数组是不可变的，所以每次的增删数组都涉及到了数组的扩容和拷贝，速度上会较慢（ArrayList如果不考虑扩容的情况，效率和LinkedList不会有太大差别）；

扩容

在添加元素时，考虑到容量的因素，需要按情况进行扩容，默认的扩容方案如下：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //扩容判断  size+1即为minCapacity，可满足add操作的最小容量
    elementData[size++] = e;//在末尾追加元素
    return true;
}

/**
 * 可分配的最大数组长度
 * 一些虚拟机会在数组中保留头文字
 * 去分配一个更大长度的数组可能会导致内存溢出的错误：请求的数组大小超过虚拟机的限制
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) { //如果列表为空（没有元素）
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//比较设定的最小容量和默认容量，取其中大最大值为最小容量；即minCapacity不满10，按10处理
    }
    ensureExplicitCapacity(minCapacity);//扩容判断
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//修改次数加1，这个字段继承自AbstractList，用于在add  set等操作时进行ConcurrentModificationException异常判断

    if (minCapacity - elementData.length > 0)//判断最小容量和当前列表的大小，注意是elementData.length而不是size
        grow(minCapacity);//当前容量不足，扩容
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;//原有的容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量  原有的容量的1.5倍左右  >> 移位操作  即 1111右移1位变为0111 15->7
    // int newCapacity = (oldCapacity * 3)/2 + 1;  //JDK1.6的源码
    if (newCapacity - minCapacity < 0) //如果扩容后的容量比所需的最小容量还小  溢出？？
        newCapacity = minCapacity; //设置最小容量为新的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) //再判断新容量是否超出所允许的最大长度  MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 为什么是这个数？？？ 没搞清楚
        newCapacity = hugeCapacity(minCapacity); //如果新容量超出最大长度，重新扩容
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);//数组拷贝，新数组长度为新容量的大小，扩容完毕
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();//溢出  抛异常  感觉不会出现这种情况
    return (minCapacity > MAX_ARRAY_SIZE) ? //如果最小容量超出所允许的最大长度，新容量就用Integer.MAX_VALUE,否则的话就用MAX_ARRAY_SIZE
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

在扩容的过程中涉及到了modCount字段，ArrayList的修改次数，Java中的fail-fast机制，每次去检查修改次数，如果和期望的修改次数不一致，会出现ConcurrentModificationException异常

fail-fast，快速失败，Java集合中的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出ConcurrentModificationException异常，从而产生fail-fast机制

除了在添加元素时，自动的扩容之外，ArrayList也可以显式的进行扩容，直接指定ArrayList的最小容量

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != EMPTY_ELEMENTDATA)
        // 如果elementData不是空数组，则证明数组已有数据，minExpand为0
        ? 0
        // 等于空数组的话，则默认大小为DEFAULT_CAPACITY 10
        : DEFAULT_CAPACITY;
	
    if (minCapacity > minExpand) {//如果需要的最小容量大于minExpand
        ensureExplicitCapacity(minCapacity);//对数组进行扩容
    }
}

构造器

ArrayList三个构造器，其中两个是根据Collection实现类的标准定义的，另一个public ArrayList(int initialCapacity)用来指定初始化的容量，这个方法是为了在可以预估大概数据量的情况下，指定ArrayList的默认长度，避免扩容和数组拷贝，可以提高插入效率

  /**
   * 构造器
   * @param  数组的大小
   * 如果传入的参数小于0的话，抛出IllegalArgumentException异常
   */
  public ArrayList(int initialCapacity) {
      super();
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
      this.elementData = new Object[initialCapacity]; //初始化一个Object数组
  }
	
  /**
   * 无参构造器，初始化一个空数组
   */
  public ArrayList() {
      super();
      this.elementData = EMPTY_ELEMENTDATA; 
  }
	
  /**
   * 
   * 构造器
   * @param c 集合类，该集合中的元素必须是ArrayList的泛型的本类或子类
   */
  public ArrayList(Collection<? extends E> c) {
      elementData = c.toArray(); //转换为Object数组
      size = elementData.length; //设置size
// c.toArray可能不返回Object数组 详见http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
      if (elementData.getClass() != Object[].class) 
             //如果elementData中的元素不是Object类型的，则将其复制到Object数组中，并重新赋值给elementData
          elementData = Arrays.copyOf(elementData, size, Object[].class);
  }

ArrayList是Collection的实现类，所有通用的Collection实现类（通常通过它的一个子接口间接实现Collection，如List、Queue和Set）应该提供两个“标准”的构造方法：
1.无参构造方法，用于创建空的collection
2.带有Collection类型单参数的构造方法，用于创建一个具有与其参数相同元素的新collection，如：public ArrayList(Collection<? extends Ec)
这两个标准不强制必须遵守，但是目前JDK中所有集合实现类都遵守了这两个标准

其他方法

去除无用空间

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

列表中是否包含某个元素

其实就是 o==null ? e==null : o.equals(e)；

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

获取某个元素的索引值

返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1

public int indexOf(Object o) {
    if (o == null) {//如果传入的参数是null，则循环遍历数组，找到第一个为null的值，返回它的索引
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {//否则，遍历数组，查看两个对象是否相等；比对时需要注意equals方法有没有被重写
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;//如果数组中找不到该值，则返回-1
}

返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1

public int lastIndexOf(Object 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

重写Clone方法，虽然实现了Cloneable接口，但是Cloneable中并没有clone方法；如果不重写clone()方法，当ArrayList对象调用clone()方法时，将抛出CloneNotSupportedException异常

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        //因为ArrayList已经实现了Cloneable，所以这个异常不会发生，
        //如果发生了，就抛出InternalError错误：Java虚拟机中发生了意外的内部错误
        throw new InternalError(e);
    }
}

List转数组

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

转化为对象数组，数组中元素顺序和在列表中时一致；重写分配了内存空间，修改该数组不影响原列表；

需要注意的是，这里仍为浅拷贝，修改元素的内容，会影响原列表中元素的内容

@SuppressWarnings("unchecked")
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;
}

按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组

获取指定位置的元素

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

public E get(int index) {
    rangeCheck(index);//检查传入的索引参数是否超出列表的最大长度，如果超出，抛出越界异常IndexOutOfBoundsException
	
    return elementData(index);
}

设值

public E set(int index, E element) {
    rangeCheck(index);
	
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

设置某个位置的元素为element，该方法返回列表中被替换的值，即原值

添加元素

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!! 保证容量，可能会触发扩容操作
    elementData[size++] = e;
    return true;
}

列表末尾添加元素，此方法可能会涉及到列表扩容和数组拷贝。

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

在列表中指定位置插入元素，列表中该位置前的元素不动，后面的元素向后移动一位

删除元素

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

从列表中指定位置移除某个元素，列表的capacity容量不变，但是size减1

该方法返回移除的元素

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

移除列表中第一个对象o，成功返回true

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
}

私有删除方法，跳过边界检查，并且不返回删除的值。可参考remove(int index)的方法

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

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

移除列表中索引在fromIndex、toIndex之间的元素

清空列表

public void clear() {
    modCount++;

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

    size = 0;
}

清空列表元素，执行该方法后，容量不变，但是size变为0

添加集合到列表中

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

将集合中的元素都添加到列表中，需要注意的是，集合元素的类型必须是列表中元素类型或者其子类

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

把集合中的元素都存入到列表中的指定位置，起始位置由index决定

边界检查

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

检查传入的索引参数是否超出列表的最大长度，如果超出，抛出越界异常

该方法不检查index是否为负数，所以虽然get(i)在传入负值时仍会抛出IndexOutOfBoundsException异常，但是该异常信息是elementData[index]时数组越界产生的，不是ArrayList的rangeCheck方法抛出的，这点需要注意

ArrayList的IndexOutOfBoundsException会调用outOfBoundsMsg方法，显示【”Index: “+index+”, Size: “+size】

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

在add和addAll方法中使用，避免index出现越界问题

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

List越界异常触发时，异常信息详情

交集、差集

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

从列表中移除集合中的所有元素，相当于数学中的差集

如果集合中元素类型和列表中元素类型不匹配，则会抛出ClassCastException

如果列表中包含null值，但是集合中不允许null，则会抛出NullPointerException

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

列表取列表和集合的交集

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++)
            if (c.contains(elementData[r]) == complement) //该方法取交集或差集
                elementData[w++] = elementData[r];
    } finally {
        // 保留与AbstractCollection的行为兼容性，即使c.contains()抛出异常也会进行部分交集/差集操作。
        if (r != size) {//列表没有遍历完就抛出异常
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;//取交集/差集后，列表应有的长度
        }
        if (w != size) {//多余的索引位置置空，快速GC
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;//列表长度发生了改变，则证明进行了交集/差集操作，返回true，代表成功，哪怕抛出了异常
        }
    }
    return modified;
}

删除/保留列表中的元素（在集合中存在的元素）

complement是boolean类型的，为 true 则保留，即取交集，为false 删除，即取差集

序列化

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) { //防止在ArrayList对象序列化期间修改了ArrayList
        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();
        }
    }
}