ArrayList源码分析

版本说明：jdk1.7.0_79

ArrayList

属性

//默认的初始容量大小，为10
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};

//用来存放元素的数组。
private transient Object[] elementData;

//存放的元素个数
private int size;

构造方法

public ArrayList(int initialCapacity)
public ArrayList()
public ArrayList(Collection<? extends E> c)

创建ArrayList时，可以指定初始容量值。如果没有指定初始容量，则使用默认的容量值DEFAULT_CAPACITY=10。

也可以用其它容器填充的方式来创建ArrayList,其容量值就其它容器的size值(存放元素的个数)。【刚好装满】

但是初始容量既不能设置过大，也不能过小。如果过大，但元素增长过慢，则导致内存浪费。如果过小，造成频繁的扩容(内部元素移动)，影响效率。

参考博客：关于ArrayList的初始容量以及扩容的效率问题

add方法

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

该方法是将元素添加到列表尾部

get方法

    public E get(int index) {
        //先检查index是否越界
        rangeCheck(index);
 
        return elementData(index);
    }

remove方法

删除指定index处的元素

  public E remove(int index) {
    //检查index是否越界
            rangeCheck(index);
   
    modCount++;
            //暂存要删除的元素
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
            //如果删除位置不是末尾，进行元素的移动
    if (numMoved > 0)
      System.arraycopy(elementData, index+1, elementData, index, numMoved);//index之后的所有元素都往前挪动。
    
            //将末位置设为null。size值减1
            elementData[--size] = null; // 【clear to let GC do its work】

            //返回删除的元素
    return oldValue;
  }

如果删除的是末尾的元素，直接删除即可。如果是其它位置，则需要将删除位后面的所有元素往前移动。

elementData[--size] = null这段代码有两层意思。

1.删除元素后，末位元素已经没有存在的意义了，所以将其设为null。

2.如果该元素是某个对象的引用，且不存在其它对该对象的引用，则设为null之后，该对象就成为了垃圾，垃圾回收机制开始工作(不保证进行回收)

注意：如果是复杂类型，容器中存放的是对象的引用，所以删除时仅仅删除的是引用，真实的对象并未删除。

remove(Object o)

删除第一个出现在ArrayList中的元素

    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自动扩容机制

我们知道ArrayList优于数组之处在于它具有自动扩容机制，也就是当ArrayList中存放的元素个数达到了其容量之后，继续向其中添加元素，它会帮我们自动扩充容量。ArrayList在添加元素时先会确保内部容量可用,会调用ensureCapacityInternal(size + 1);

查看源码可知，有两个确保容量的方法。

• public void ensureCapacity(int minCapacity)
• private void ensureCapacityInternal(int minCapacity)

公有的扩容方法说明，我们可以手动的对ArrayList进行扩容。

私有的那个方法名后面有个internal(内部的),说明该方法仅供ArrayList内部使用。我们重点关注这个私有的扩容方法。

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);//***
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//***
    }
    private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);//>>表示右移一位，相当于除以2
  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:
  lementData = Arrays.copyOf(elementData, newCapacity);
  }

int newCapacity = oldCapacity + (oldCapacity >> 1)，从而可以知道ArrayList扩容到原容量的1.5倍(约等于)
而在JDK6中扩容实现如下

int newCapacity = (oldCapacity * 3)/2 + 1;

也就是说，如果初始容量为10，JDK7扩容至15，而JDK6扩容至16，但大约都是原来的1.5倍。

为什么jdk7会换了个写法，其实原因很简单。oldCapacity直接乘以3(暴增)，很可能会造成int溢出，而jdk6中的写法则是缓慢的增加，相比要安全的多。

更多关于ArrayList和Vector扩容1.5倍的讨论请参阅：

Why does ensureCapacity() in Java ArrayList extend the capacity with a const 1.5 or (oldCapacity * 3)/2 + 1?

Logic used in ensureCapacity method in ArrayList

快速失败机制

请移步到fail-fast(快速失败/报错机制)-ConcurrentModificationException

总结

ArrayList底层使用数组实现。随机访问速度快，插入和移除操作速度慢。

ArrayList具有自动扩容机制。

ArrayList是非线程安全的。

ArrayList和Vector的比较请看Vector和ArrayList的比较