我們知道 ArrayList 中有一個批量刪除的集合的方法：removeAll(Collection<?> c)毛嫉，該方法中涉及了高效保存兩個集合公有元素的算法徘郭，這里特地拿出來分析一下未蝌，學(xué)習(xí)源碼中的優(yōu)秀設(shè)計(jì)思想油吭。
下面先給出批量刪除代碼的片段：
/**這里先假設(shè)elementData(ArryList內(nèi)部維護(hù)的一個Object[]數(shù)組)和
集合c的交集是A：
當(dāng) complement == true 時斩祭，elementData最終只會存儲A
當(dāng) complement == false 時已烤，elementData最終刪除A。
在對elementData的元素進(jìn)行篩選的時候苛坚，這里使用了r比被、w兩個游標(biāo)，
從而避免從新開辟一個新的數(shù)組進(jìn)行存儲泼舱。
**/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//當(dāng)調(diào)用removeAll(Collection<?> c)時等缀，complement == false,
//此時elementData數(shù)組中存儲的是去掉A的部分
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//出現(xiàn)異常會導(dǎo)致 r !=size , 則將出現(xiàn)異常處后面的數(shù)據(jù)全部
//復(fù)制覆蓋到數(shù)組里。
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
我們先分析正常情況娇昙，即 r == size:
注意到只有 elementData和都為空或者c的元素都不在elementData中的情況下尺迂，才會出現(xiàn) w == size,因?yàn)槎紴榭栈蛘邲]有相同元素，所以不存在刪除的情況冒掌。
所以只用分析 w != size的情況
當(dāng) w != size 時噪裕，一旦出現(xiàn)elementData中有，但是c中沒有的元素的時候股毫，就會存放在elementData[w]中膳音，也就是說0~（w-1）位置一定是
elementData包含但是c中沒有的元素，然后將w~（size-1）位置的元素置空铃诬，交給GC去回收祭陷，這樣一來，elementData中就只剩下除去和c中相同元素的數(shù)組了趣席，它的size為w兵志。
接下來再說說異常情況：即 r != size：
因?yàn)檫@個時候已經(jīng)出現(xiàn)了異常，所以把從r位置開始的（size-r）個元素復(fù)制到從w開始的到（w+size-r-1）位置宣肚，此時 w = size - r想罕，這樣就可以保證在出現(xiàn)異常之前已經(jīng)遍歷的c和elementData中的相同元素已經(jīng)被覆蓋了，同時也保證了從r位置開始的（size-r）個元素向左移動了（r-w）位霉涨，保證數(shù)組元素的完整性按价。然后在將w~（size-1）位置的元素置空惭适，交給GC去回收。這樣即使發(fā)生了異常俘枫，也不會導(dǎo)致刪除錯誤腥沽。
至此，ArrayList的批量刪除算法就分析完了鸠蚪，可能看起來有點(diǎn)繞今阳，但是靜下心來，用筆在紙上畫一畫這個過程茅信，你就會豁然開朗盾舌。
