復(fù)制一時爽，一直復(fù)制一直爽照棋。
github地址：android_interview
雖然從github復(fù)制的资溃，但自己再寫一遍能更好的理解和加深記憶。此文章僅作為個人學(xué)習(xí)的知識點小結(jié)烈炭，不做任何其他用途溶锭。
1、概括
ArrayList是一個比較簡單的數(shù)據(jù)結(jié)構(gòu)符隙，最重要的一點就是它的自動擴容趴捅，
可以認(rèn)為就是我們常說的“動態(tài)數(shù)組”。
實際上霹疫，ArrayList內(nèi)部就是以數(shù)組實現(xiàn)的驻售，這個數(shù)組有容量限制。超出限制時會增加50%容量更米，用System.arraycopy()復(fù)制到新的數(shù)組欺栗，因此最好能給出數(shù)組大小的預(yù)估值。默認(rèn)第一次插入元素時創(chuàng)建大小為10的數(shù)組征峦。（注意：只是容量為10迟几，不是size為10，有區(qū)別的）
按數(shù)組下標(biāo)訪問元素—get(i)/set(i,e) 的性能很高栏笆，這是數(shù)組的基本優(yōu)勢类腮。直接在數(shù)組末尾加入元素—add(e)的性能也高，但如果按下標(biāo)插入蛉加、刪除元素—add(i,e), remove(i), remove(e)蚜枢，則要用System.arraycopy()來移動部分受影響的元素，性能就變差了针饥，這是基本劣勢厂抽。
2、add函數(shù)
在ArrayList中增加元素丁眼，使用 add 函數(shù)筷凤。他會將元素放到末尾。具體實現(xiàn)如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
可以看到其最核心的內(nèi)容就是 ensureCapacityInternal 方法 苞七。這個函數(shù)其實就是自動擴容機制的核心藐守。然后來看一下他的具體實現(xiàn)：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 溢出代碼
int oldCapacity = elementData.length;
// 擴展為原來的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴為1.5倍還不滿足需求，直接擴為需求值
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);
}
也就是說蹂风，當(dāng)增加數(shù)據(jù)的時候卢厂，如果ArrayList的大小已經(jīng)不滿足需求時，那么就將數(shù)組變?yōu)樵L度的1.5倍惠啄，之后的操作就是把老的數(shù)組拷到新的數(shù)組里面慎恒。例如任内，默認(rèn)的數(shù)組大小是10，也就是說當(dāng)我們 add 10個元素之后巧号，再進行一次add時，就會發(fā)生自動擴容姥闭，數(shù)組長度由10變?yōu)榱?5丹鸿。
3、set和get函數(shù)
Array的set和get函數(shù)比較簡單棚品，先做index檢查靠欢，然后執(zhí)行賦值或訪問操作，其中rangeCheck函數(shù)檢查是否越界問題铜跑，越界就拋出異常门怪，中斷運行：
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
4、remove函數(shù)
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);
}
// 把最后的置null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
