ArrayList扩容机制以及底层实现

 1    private static final int DEFAULT_CAPACITY = 10;  //默认的初始容量为10
 2     
 3     private static final Object[] EMPTY_ELEMENTDATA = {};  //空数组
 4     
 5     /**
 6      *与默认的初始容量DEFAULT_CAPACITY区分开来，
 7      *简单来讲就是第一次添加元素时知道该 elementData 
 8      *从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。
 9      **/
10     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空数组，与EMPTY_ELEMENTDATA空数组区分
11     
12      /**
13     * 存储ArrayList元素的数组缓冲区。
14     * ArrayList的容量是这个数组缓冲区的长度。
15     *任何空的ArrayList 即 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
16     *当添加第一个元素时，将扩展为DEFAULT_CAPACITY。
17      **/
18     transient Object[] elementData; 
19     
20     private int size;  //实际元素个数

1 /**
2      * 构造一个初始容量为10的空ArrayList
3      */
4     public ArrayList() {
5         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
6     }

 1 public ArrayList(int initialCapacity) {
 2     if (initialCapacity > 0) {  //当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object 数组并赋值给 elementData
 3         this.elementData = new Object[initialCapacity];
 4     } else if (initialCapacity == 0) {  //当 initialCapacity 为零时则是把 空数组EMPTY_ELEMENTDATA 赋值给 elementData
 5         this.elementData = EMPTY_ELEMENTDATA;
 6     } else {
 7         throw new IllegalArgumentException("Illegal Capacity: "+
 8                                        initialCapacity);
 9     }
10 }

 1 public ArrayList(Collection<? extends E> c) {
 2     elementData = c.toArray();
 3     if ((size = elementData.length) != 0) {
 4         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 5         if (elementData.getClass() != Object[].class) //判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换
 6         elementData = Arrays.copyOf(elementData, size, Object[].class);//
 7     } else {
 8         // size 为零，则将空数组赋给elementData，相当于new ArrayList(0)
 9         this.elementData = EMPTY_ELEMENTDATA;
10     }
11 }

 1 public boolean add(E e) {
 2     ensureCapacityInternal(size + 1);  //每次添加元素到集合中时都会先确认下集合容量大小
 3     elementData[size++] = e;  //size 自增 +1。
 4     return true;
 5 }
 6     
 7 //确认容量大小
 8 private void ensureCapacityInternal(int minCapacity) {
 9     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
10 }
11 
12 //返回容量大小
13 private static int calculateCapacity(Object[] elementData, int minCapacity) {
14     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
15         return Math.max(DEFAULT_CAPACITY, minCapacity); //这里其实才是真正的开始初始化数组的容量大小为10
16     }
17     return minCapacity;
18 }
19 
20 //根据确认的容量的大小判断是否进行扩容
21 private void ensureExplicitCapacity(int minCapacity) {
22     modCount++;  //记录操作次数
23 
24     // overflow-conscious code
25     if (minCapacity - elementData.length > 0)
26         grow(minCapacity);  //调用扩容方法
27 }

 1 //根据确认的容量的大小判断是否进行扩容
 2 private void ensureExplicitCapacity(int minCapacity) {
 3     modCount++;  //记录操作次数
 4 
 5     // overflow-conscious code
 6     if (minCapacity - elementData.length > 0)
 7         grow(minCapacity);  //调用扩容方法
 8 }
 9 
10 //扩容函数
11 private void grow(int minCapacity) {
12     // overflow-conscious code
13     int oldCapacity = elementData.length;
14     int newCapacity = oldCapacity + (oldCapacity >> 1);  //这里NewCapacity为原来容量的1.5倍
15     if (newCapacity - minCapacity < 0)
16         newCapacity = minCapacity;
17     if (newCapacity - MAX_ARRAY_SIZE > 0)
18         newCapacity = hugeCapacity(minCapacity);
19     // minCapacity is usually close to size, so this is a win:
20     elementData = Arrays.copyOf(elementData, newCapacity);
21 }

1 //扩容过大，或者所需容量过大则调用此方法 
2 private static int hugeCapacity(int minCapacity) {
3         if (minCapacity < 0) // overflow
4             throw new OutOfMemoryError();
5         return (minCapacity > MAX_ARRAY_SIZE) ?
6             Integer.MAX_VALUE :
7             MAX_ARRAY_SIZE;
8     }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }