ArrayList簡介
ArrayList實現(xiàn)了List接口，繼承了AbstractList，底層是數(shù)組實現(xiàn)的。它是非線程安全的，一般多用于單線程環(huán)境下(與Vector最大的區(qū)別就是，Vector是線程安全的，所以ArrayList 性能相對Vector 會好些)，它實現(xiàn)了Serializable接口，因此它支持序列化，能夠通過序列化傳輸(實際上java類庫中的大部分類都是實現(xiàn)了這個接口的)，實現(xiàn)了RandomAccess接口，支持快速隨機訪問(只是個標(biāo)注接口，并沒有實際的方法),這里主要表現(xiàn)為可以通過下標(biāo)直接訪問(底層是數(shù)組實現(xiàn)的，所以直接用數(shù)組下標(biāo)來索引)，實現(xiàn)了Cloneable接口，能被克隆。
ArrayList的主要成員變量
private static final int DEFAULT_CAPACITY = 10;//默認(rèn)初始容量；
private static final Object[] EMPTY_ELEMENTDATA = {};//定義一個空的數(shù)組實例以供其他需要用到空數(shù)組的地方調(diào)用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//定義一個空數(shù)組，跟前面的區(qū)別就是這個空數(shù)組是用來判斷ArrayList第一添加數(shù)據(jù)的時候要擴容多少。默認(rèn)的構(gòu)造器情況下返回這個空數(shù)組
transient Object[] elementData;//數(shù)據(jù)存的地方它的容量就是這個數(shù)組的長度，同時只要是使用默認(rèn)構(gòu)造器（DEFAULTCAPACITY_EMPTY_ELEMENTDATA ）第一次添加數(shù)據(jù)的時候容量擴容為DEFAULT_CAPACITY = 10
private int size;//當(dāng)前數(shù)組的長度
ArrayList初始化
ArrayList提供了三種方式
public ArrayList();//
public ArrayList(int initialCapacity);//
public ArrayList(Collection<? extends E> c);//
下面將逐一分析以上三種初始化方式
首先分析無參構(gòu)造方法的源碼：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
按注釋描述無參構(gòu)造方法將創(chuàng)建一個初始容量為10的空數(shù)組，但是從代碼可以看出此時只是將elementData指向一個空數(shù)組而已。
再看看帶初始容量參數(shù)的構(gòu)造方法：
/**
* 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);
}
}
從源碼可以看出：程序首先會對傳進來的參數(shù)initialCapacit進行判斷，如果初始容量小于0則拋出異常，如果初始容量等于0則將**elementData **指向一個空數(shù)組，如果初始容量大于0則創(chuàng)建一個大小為初始容量的數(shù)組。
最后分析帶參數(shù)的構(gòu)造方法：
/**
* 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;
}
}
這個構(gòu)造方法是直接將一個collection作為參數(shù)，不難看出程序直接將collection轉(zhuǎn)化為數(shù)組賦值給elementData，如果elementData的size為0，則將elementData初始化為空數(shù)組，size為elementData的長度。這里size是ArrayList的一個int型私有變量，用于記錄該list集合中當(dāng)前元素的數(shù)量，注意不是容量。
ArrayList的Add方法
前面分析ArrayList的構(gòu)造函數(shù)時，有一個小小的疑問，注釋說創(chuàng)建的是一個默認(rèn)大小為10的空數(shù)組，但是代碼實現(xiàn)里面看到的只是將elementData賦值為一個空數(shù)組。其實這些都是在add方法里面實現(xiàn)的，下面我們分析add方法到底是如何實現(xiàn)的。
/**
* 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;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
從源碼里面可以看出，當(dāng)調(diào)用add方法時首先會調(diào)用ensureCapacityInternal方法，從方法名可以看出，該方法是用于確保容量的。通過分析ensureCapacityInternal可看到如下邏輯：
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
通過這一步來判斷，當(dāng)前elementData是否為空數(shù)組(即初始化容量為0或者調(diào)用了無參構(gòu)造函數(shù)后的結(jié)果)，如果是，則使用
Math.max(DEFAULT_CAPACITY, minCapacity)進行選擇一個較大的，其中，DEFAULT_CAPACITY是ArrayList定義的靜態(tài)常量10：可以看出，這里如果minCapacity小于10的話(如果elementData為空的話，size+1即minCapacity一般為1)，返回的是10，所以如果沒有指定大小的話，默認(rèn)是初始化一個容量為10的數(shù)組。然后在調(diào)用ensureExplicitCapacity方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
在這個方法里進行判斷，新增元素后的大小minCapacity是否超過當(dāng)前集合的容量elementData.length，如果超過，則調(diào)用grow方法進行擴容。我們進入該方法進行查看:
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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:
elementData = Arrays.copyOf(elementData, newCapacity);
}
在這里可以很清楚的看到擴容容量的計算:int newCapacity = oldCapacity + (oldCapacity >> 1),其中oldCapacity是原來的容量大小，oldCapacity >> 1 為位運算的右移操作，右移一位相當(dāng)于除以2，所以這句代碼就等于int newCapacity = oldCapacity + oldCapacity / 2；即容量擴大為原來的1.5倍，獲取newCapacity后再對newCapacity的大小進行判斷，如果仍然小于minCapacity，則直接讓newCapacity 等于minCapacity，而不再計算1.5倍的擴容。然后還要再進行一步判斷，即判斷當(dāng)前新容量是否超過最大的容量 if (newCapacity - MAX_ARRAY_SIZE > 0)，如果超過，則調(diào)用hugeCapacity方法，傳進去的是minCapacity，即新增元素后需要的最小容量：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
如果minCapacity大于MAX_ARRAY_SIZE，則返回Integer的最大值。否則返回MAX_ARRAY_SIZE。然后回到grow方法，調(diào)用Arrays.copyof方法，即復(fù)制原數(shù)組內(nèi)容到一個新容量的大數(shù)組里。這里Arrays.copyof方法實際是調(diào)用System.arraycopy方法。到這里，應(yīng)該可以很清楚的知道ArrayList底層擴容的原理了。與Vector不同的是，Vector每次擴容容量是翻倍，即為原來的2倍，而ArrayList是1.5倍。
ArrayLIst的get方法
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
上面是對代碼的分析得出的結(jié)論，下面將驗證分析的結(jié)論是否正確
public class testArrayList {
public static void main(String[] args){
ArrayList list = new ArrayList<>();
System.out.print("size = "+list.size());
System.out.println(" Capacity = "+getCapacity(list));
for (int i = 0; i < 20; i++) {
list.add(i);
System.out.print("size = "+list.size());
System.out.println(" Capacity = "+getCapacity(list));
}
}
public static int getCapacity(ArrayList list){
int length = 0;
Class clazz = list.getClass();
Field field;
try{
field = clazz.getDeclaredField("elementData");
field.setAccessible(true);
Object[] objects = (Object[])field.get(list);
length = objects.length;
}catch (Exception e){
e.printStackTrace();
}finally {
return length;
}
}
}
測試代碼中先創(chuàng)建一個ArrayList，然后輸出剛創(chuàng)建時list的size和capacity，然后向list中添加元素，同時打印出list的size和capacity，結(jié)果如下：
size = 0 Capacity = 0
size = 1 Capacity = 10
size = 2 Capacity = 10
size = 3 Capacity = 10
size = 4 Capacity = 10
size = 5 Capacity = 10
size = 6 Capacity = 10
size = 7 Capacity = 10
size = 8 Capacity = 10
size = 9 Capacity = 10
size = 10 Capacity = 10
size = 11 Capacity = 15
size = 12 Capacity = 15
size = 13 Capacity = 15
size = 14 Capacity = 15
size = 15 Capacity = 15
size = 16 Capacity = 22
size = 17 Capacity = 22
size = 18 Capacity = 22
size = 19 Capacity = 22
size = 20 Capacity = 22
可以看出剛創(chuàng)建的時候list的capacity和size的大小都是為0，而添加第一個元素時，size = 0 capacity = 10，不難看出list是在調(diào)用add方法時才capacity 才為10；當(dāng)添加到第11個元素時，因為size>capacity ，所以此時list會擴容，擴容后大小為15，即capacity的1.5倍。
總結(jié)
ArrayList默認(rèn)容量是10，如果初始化時一開始指定了容量，或者通過集合作為元素，則容量為指定的大小或參數(shù)集合的大小。每次擴容為原來的1.5倍，如果新增后超過這個容量，則容量為新增后所需的最小容量。如果增加0.5倍后的新容量超過限制的容量，則用所需的最小容量與限制的容量進行判斷，超過則指定為Integer的最大值，否則指定為限制容量大小。然后通過數(shù)組的復(fù)制將原數(shù)據(jù)復(fù)制到一個更大(新的容量大小)的數(shù)組。
