ArrayList相信大家都用過撒妈，那么今天就來聊聊ArrayList缕棵。
概述
ArrayList是一個相對來說比較簡單的數(shù)據(jù)結(jié)構(gòu)瘩绒，底層是用數(shù)組實現(xiàn)的困肩，它和數(shù)組最大的區(qū)別就是可以自動擴(kuò)容，即我們可以認(rèn)為ArrayList就是一個動態(tài)數(shù)組拗窃。
ArrayList 允許空值和重復(fù)元素瞎领，ArrayList 是非線程安全類，并發(fā)環(huán)境下随夸，多個線程同時操作 ArrayList九默，會引發(fā)不可預(yù)知的錯誤。
源碼分析
構(gòu)造方法
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//transient 修飾宾毒，不參與序列化
transient Object[] elementData;
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
ArrayList 有兩種構(gòu)造方法驼修，一種有參，一種無參诈铛。邏輯都很簡單乙各，目的就是初始化底層的數(shù)組elementData。默認(rèn)的構(gòu)造方法會初始化一個空的數(shù)組癌瘾。
增加元素
public boolean add(E e) {
//檢查是否需要擴(kuò)容
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++;
}
add方法有兩種觅丰，一種是直接添加元素到末尾，一種是添加到指定位置妨退。兩種步驟差不多妇萄，就是第二種會有一個將元素整體位移的操作。（第二種效率肯定較低咬荷，在大集合中應(yīng)該盡量避免調(diào)用）
從上面代碼中不難看出冠句，擴(kuò)容的操作是在ensureCapacityInternal方法中完成的，那么我們來看看擴(kuò)容的具體過程幸乒。
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//邊界檢查懦底，保證最小容量 >10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴(kuò)容的核心方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//擴(kuò)容為原來的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//仍然不夠就直接擴(kuò)容為需求值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果最小容量超過 MAX_ARRAY_SIZE，則將數(shù)組容量擴(kuò)容至 Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//產(chǎn)生新的數(shù)組罕扎，并復(fù)制原有數(shù)組到新數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
代碼雖然不短聚唐，但是大部分操作都是邊界檢查。擴(kuò)容的核心方法是grow方法腔召。它計算出新的容器大懈瞬椤（即newCapacity），并確保了newCapacity不會比minCapacity小臀蛛，最后調(diào)用Arrays.copyOf()創(chuàng)建一個新的數(shù)組并將數(shù)據(jù)拷貝到新數(shù)組中亲桦，最后讓elementData進(jìn)行引用崖蜜。默認(rèn)的擴(kuò)容大小是當(dāng)前數(shù)組大小的一半，即擴(kuò)容至當(dāng)前容量的1.5倍客峭。
刪除元素
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;
}
刪除操作也不是很復(fù)雜豫领，就直接將刪除元素后面的所有元素向前移一位，這樣目標(biāo)元素就會被覆蓋舔琅，然后把最后的那個元素置空等恐，同時將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;
}
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方法還有另一種搏明，用要刪除的Object作為參數(shù)鼠锈。這種就是從前往后遍歷整個數(shù)組，找到第一個和目標(biāo)相等的對象星著，然后執(zhí)行刪除操作，刪除的過程和指定位置刪除沒有區(qū)別粗悯。如果刪除了元素會返回true虚循，該元素不存在則返回false。
查詢及修改
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
get方法样傍，直接返回目標(biāo)元素横缔。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set方法，直接修改目標(biāo)元素衫哥。
總結(jié)
ArrayList是我們常用的集合類型茎刚，底層由數(shù)組實現(xiàn)，方法都非常簡單撤逢。在用無參構(gòu)造方法創(chuàng)建時會創(chuàng)建一個空數(shù)組膛锭，直到有元素放入后才會擴(kuò)容為10。默認(rèn)擴(kuò)容為原來的1.5倍蚊荣，如果1.5倍仍不夠初狰，則會直接擴(kuò)容到目標(biāo)值。由于擴(kuò)容操作會將原數(shù)組拷貝到創(chuàng)建出的新數(shù)組中互例，因此開銷較大奢入，應(yīng)盡量在初始化時設(shè)置好數(shù)組的容量。
由于底層為數(shù)組實現(xiàn)媳叨，隨機(jī)讀寫開銷小腥光，因此ArrayList適用于存儲訪問頻繁，但增刪較少的數(shù)據(jù)糊秆。
