java jdk是如何實現(xiàn)ArrayList的第献？
ArrayList的實現(xiàn)很簡單钢坦，總的來說，就是arraylist內(nèi)置了一個Object類型的數(shù)組比搭，當(dāng)插入或刪除數(shù)據(jù)時冠跷，都操作這個內(nèi)置數(shù)組array。當(dāng)用戶想new的ArrayList大于內(nèi)置數(shù)組時敢辩，會在后面串一個數(shù)組蔽莱，具體數(shù)組怎么遞增看下文。
1. ArrayList中的屬性
//數(shù)組每次增加長度時最小增量（具體每次增加時戚长，增量不一定是MIN_CAPACITY_INCREMENT盗冷，有一定的策略）
private static final int MIN_CAPACITY_INCREMENT = 12;
//ArrayList的長度
int size;
//數(shù)組
transient Object[] array;
2. 構(gòu)造函數(shù)
我們先來看看構(gòu)造函數(shù)怎么實現(xiàn)的。
2.1 不指定大小
像這樣定義：
ArrayList arrayList = new ArrayList();
直接創(chuàng)建一個大小為0的ArrayList實例同廉。
public ArrayList() {
array = EmptyArray.OBJECT;
}
2.2 指定int類型的大幸翘恰（容量）
像這樣定義：
ArrayList arrayList = new ArrayList(10);
如果指定的容量大小capacity為0，則只創(chuàng)建一個容量為0的ArrayList實例迫肖，否則锅劝，直接new一個指定大小的Object類型的數(shù)組。
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
2.3 創(chuàng)建一個包含指定Collection的list
像這樣定義：
ArrayList arrayList = new ArrayList(Collection collection);
直接把Collection轉(zhuǎn)換為數(shù)組蟆湖，并復(fù)制給ArrayList的數(shù)組array故爵。具體實現(xiàn)如下：
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
3 增量的確定
3.1 插入數(shù)據(jù)時，ArrayList內(nèi)置數(shù)組增量的確定
ArrayList插入涉及到數(shù)組增量的問題隅津，即插入一個數(shù)或一組數(shù)時诬垂，ArrayList內(nèi)置的數(shù)組該如何增長劲室？如果頻繁增長，既浪費時間又會使內(nèi)存碎片化结窘；可如果每次增量很大很洋，如每插入數(shù)據(jù)內(nèi)置數(shù)組就增加很大的容量值，那么會導(dǎo)致很多空間浪費隧枫。 jdk有一個方法提供了具體策略：
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
如果指定增量currentCapacity小于12/2=6喉磁，則增量為12；否則增量為currentCapacity/2.
注：currentCapacity >> 1 即為currentCapacity/2.如：
0000 0111（7）>> 1 右移一位變?yōu)?0000 0011（3）官脓。
0000 1100（12）>> 1 右移一位變?yōu)?0000 0110（6）协怒。
3.2 在index位置插入一個數(shù)object
我們來看一下方法，add(int index, E object),在index位置插入一個Object類型的數(shù)卑笨。
@Override
public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
//父類AbstractList的一個屬性斤讥，記錄list改變了幾項
modCount++;
}
其實就是
先根據(jù)newCapacity方法獲取到數(shù)組增量，
然后new一個臨時數(shù)組newArray湾趾，先把當(dāng)前數(shù)組array從[0,index]都copy給newArray的[0,index]，
然后把array從 [index,s]（數(shù)組末尾）copy給newArray的[index+1,s+1]派草，這樣全部數(shù)組就復(fù)制過來了搀缠，然后把newArray copy給array；
最后令array[index+1]為新插入的值object近迁，size+1艺普。
3.3 在index位置插入一個collection
這種情況下增量是多少呢？
注意：ArrayList并不是直接增加collection.length()的長度鉴竭，而是通過newCapacity方法來計算增量歧譬，傳入的參數(shù)是 當(dāng)前數(shù)組的長度(size+newSize).
其中 newSize為新數(shù)組newArray(collection.toArray())的長度.
前面我們說過，如果一次增量過小搏存，會造成頻繁增加數(shù)組瑰步，這樣既浪費時間，又會損耗性能璧眠。
代碼如下：
@Override
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}
4. remove方法
4.1 remove(int index)
先把index后面的值全部向前移一位缩焦，然后把最后一位a[s]置為空。
@Override
public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
//核心代碼
//把數(shù)組a[index+1,s]復(fù)制給數(shù)組a[index,s-1]
System.arraycop
y(a, index + 1, a, index, --s - index);
//數(shù)組最后以為置空
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}
4.2 clean方法
把數(shù)組全部置空责静。
@Override public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
}
public static void fill(Object[] array, int start, int end, Object value) {
Arrays.checkStartAndEnd(array.length, start, end);
for (int i = start; i < end; i++) {
array[i] = value;
}
}