ArrayList概述
1. ArrayList是可以動态擴容和動态删除備援容量的索引序列，基于數組實作的集合。
2. ArrayList支援随機通路、克隆、序列化，元素有序且可以重複。
3. ArrayList初始預設長度10，超出擴容1.5倍，使用Object[]存儲各種資料類型。
ArrayList資料結構
資料結構是集合的精華所在，資料結構往往也限制了集合的作用和側重點，了解各種資料結構是我們分析源碼的必經之路。
ArrayList的資料結構如下：
ArrayList源碼分析
/*
* 用數組實作的集合，支援随機通路，元素有序且可以重複
* RandomAccess(ArrayList) 支援快速随機通路，使用for循環更加快速
* LinkedList 使用 iterator疊代器更加 快速
* RandomAccess 這是一個标記接口，一般此标記接口用于 List 實作，以表明它們支援快速（通常是恒定時間）的随機通路。
* 該接口的主要目的是允許通用算法改變其行為，以便在應用于随機或順序通路清單時提供良好的性能
* 包含類中的基礎屬性和3個構造方法
*/
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 預設長度 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 預設空的數組
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* ArrayList中的元素 是Object[]類型的數組
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 動态數組的實際大小 ，預設為0
* @serial
*/
private int size;
/**
* 最大數組容量2147483639
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 集合長度構造函數
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 無參構造函數，設定元素數組為空 注意此時初始容量是0，而不是大家以為的 10
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 集合參數構造函數
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); // 轉化為數組
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class) //是否成功轉化為Object類型數組
elementData = Arrays.copyOf(elementData, size, Object[].class); //不為Object數組的話就進行複制
}
ArrayList繼承和實作分析
ArrayList extends AbstractList
AbstractList extends AbstractCollection
java中所有類都繼承Object，是以ArrayList的繼承結構如上圖。
1. AbstractList是一個抽象類，實作了List<E>接口，List<E>定義了一些List通用方法，而AbstractList抽象類中可以有抽象方法，還可以有具體的實作方法，AbstractList實作接口中一些通用的方法，實作了基礎的add/get/indexOf/iterator/subList/RandomAccessSubList方法，ArrayList再繼承AbstractList，拿到通用基礎的方法，然後自己在實作一些自己特有的方法，這樣的好處是：讓代碼更簡潔，繼承結構最底層的類中通用的方法，減少重複代碼。
2.ArrayList實作了List<E>、RandomAccess、Cloneable、Serializable接口
1)List<E>接口，ArrayList既然繼承自AbstractList抽象類，而AbstractList已 經實作了List接口，那麼ArrayList類為何還要再實作List接口呢？我們帶着疑問往下看：
public class Demo1 extends ArrayList {
public static void main(String[] args) {
//傳回[]
System.out.println(Arrays.toString(Demo1.class.getInterfaces()));
}
public class Demo2 implements Serializable {
public static void main(String[] args) {
//傳回[interface java.io.Serializable]
System.out.println(Arrays.toString(Demo2.class.getInterfaces()));
}
public class Test{
public static void main(String[] args) {
Serializable c1 = new Demo1();//未顯示實作接口
Serializable c2 = new Demo2();//顯示實作接口
Serializable proxy2 = createProxy(c2);
proxy2.foo();
Serializable proxy1 = createProxy(c1);
proxy1.foo();
}
private static <T> T createProxy(final T obj) {
final InvocationHandler handler = new InvocationHandler() {
@Override
public Object invoke(Object proxy, Method method, Object[] args)
throws Throwable {
return method.invoke(obj, args);
}
};
//實作接口代理，Demo1報錯，Demo2成功
//java.lang.ClassCastException: $Proxy1 cannot be cast to
//example.Test$Serializable
return (T) Proxy.newProxyInstance(obj.getClass().getClassLoader(), obj
.getClass().getInterfaces(), handler);
} 可以看出這樣這樣設計是有道理的，是以，這并不是一個錯誤，很可能是作者Josh Bloch為了便于實作代理而精心設計的。
參考與：開發collection 的作者Josh說
2)RandomAccess接口，這是一個标記接口，一般此标記接口用于 List 實作，以表明它們支援快速（通常是恒定時間）的随機通路，該接口的主要目的是允許通用算法改變其行為，以便在應用于随機或順序通路清單時提供良好的性能，實作了該接口的話使用普通的for循環來周遊，性能更高，而沒有實作該接口的話，使用Iterator來疊代，這樣性能更高，例如linkedList。是以這個标記性隻是為了讓我們知道我們用什麼樣的方式去擷取資料性能更好
3)Cloneable接口，可以使用Object.Clone()方法。
4)Serializable接口，序列化接口，表明該類可以被序列化，什麼是序列化？簡單的說，就是能夠從類變成位元組流傳輸，反序列化，就是從位元組流變成原來的類
ArrayList核心方法分析
1. add方法(4種重載實作)--增
1)add(E)；//預設直接在末尾添加元素
/**
* 新增元素
*/
public boolean add(E e) {
//指派初始長度 或者擴容,新增元素，目前實際size+1的長度
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加元素
elementData[size++] = e;
return true;
}
/**
* 確定elemenData數組有合适的大小
* 如果元素為空，則複制長度預設為10 或者更大
* @author jiaxiaoxian
* @date 2019年2月12日
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {//如果數組為空，則從size+1的值和預設值10中取最大的
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 確定elemenData數組有合适的大小
* @author jiaxiaoxian
* @date 2019年2月12日
* 如果長度大于元素長度則擴容
*/
private void ensureExplicitCapacity(int minCapacity) {
//記錄修改次數，疊代中不一緻會觸發fail-fast機制,是以在周遊中删除元素的正确做法應該是使用Iterator.remove()
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity); //擴容
}
/**
* 擴容
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length; // 舊容量
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);
}
//如果小于0 就報錯，如果大于最大值 則取最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
} 2)add(int index, E element)；//給指定下标，添加元素
/**
* 給指定下标，添加元素
*/
public void add(int index, E element) {
//判斷下标是否越界
rangeCheckForAdd(index);
//指派初始長度 或者擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
//将源數組中從index位置開始後的size-index個元素統一後移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//指派
elementData[index] = element;
size++;
}
/**
* 判斷下标是否越界
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* src:源數組
* srcPos:源數組要複制的起始位置
* dest:目的數組
* destPos:目的數組放置的起始位置
* length:複制的長度
* 注意：src 和 dest都必須是同類型或者可以進行轉換類型的數組
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length); 3)addAll(Collection<? extends E> c)；//添加Collection類型元素
/**
* 按照指定collection的疊代器所傳回的元素順序，将該collection中的所有元素添加到此清單的尾部
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
//将數組a[0,...,numNew-1]複制到數組elementData[size,...,size+numNew-1]
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
} 4)addAll(int index, Collection<? extends E> c)；//指定位置，添加Collection類型元素
/**
* 從指定的位置開始，将指定collection中的所有元素插入到此清單中，新元素的順序為指定collection的疊代器所傳回的元素順序
*/
public boolean addAll(int index, Collection<? extends E> c) {
//判斷下标是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
//先将數組elementData[index,...,index+numMoved-1]複制到elementData[index+numMoved,...,index+2*numMoved-1]
//即，将源數組中從index位置開始的後numMoved個元素統一後移numNew位
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
} 總結：
正常情況下會擴容1.5倍，特殊情況下（新擴充數組大小已經達到了最大值）則隻取最大值。
2.remove方法(4種重載實作)--删
1)remove(int index); //根據指定下标 删除元素
/**
* 根據指定下标 删除元素
*/
public E remove(int index) {
//判斷索引是否越界
rangeCheck(index);
modCount++;
//擷取舊元素
E oldValue = elementData(index);
//将數組elementData中index位置之後的所有元素向前移一位
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将原數組最後一個位置置為null，由GC清理
elementData[--size] = null; // clear to let GC do its work
return oldValue;
} 2)remove(Object o); //根據指定元素 删除元素
/**
* 移除ArrayList中首次出現的指定元素(如果存在)，ArrayList中允許存放重複的元素
*/
public boolean remove(Object o) {
// 由于ArrayList中允許存放null，是以下面通過兩種情況來分别處理。
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//私有的移除方法，跳過index參數的邊界檢查以及不傳回任何值
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++;
//将數組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
}
/**
* 清空ArrayList，将全部的元素設為null，等待垃圾回收将這個給回收掉，是以叫clear
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
3)removeAll(Collection<?> c); //删除包含在指定容器c中的所有元素
/**
* 删除ArrayList中包含在指定容器c中的所有元素
*/
public boolean removeAll(Collection<?> c) {
//檢查指定的對象c是否為空
Objects.requireNonNull(c);
return batchRemove(c, false);
}
/**
* 删除全部
* @author jiaxiaoxian
* @date 2019年2月12日
*/
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++)
if (c.contains(elementData[r]) == complement) //判斷指定容器c中是否含有elementData[r]元素
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
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;
} 4)removeIf(Predicate<? super E> filter); //按照一定規則過濾(删除)集合中的元素
/**
* 按照一定規則過濾(删除)集合中的元素
* 如：idList.removeIf(id -> id == nul);
* 去掉 List idList 集合中id 為 null 的
* @param filter
* @return
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
} 總結：
remove函數使用者移除指定下标的元素，此時會把指定下标到數組末尾的元素向前移動一個機關，并且會把數組最後一個元素設定為null，這樣是為了友善之後将整個數組不被使用時，會被GC，可以作為小的技巧使用。
3.set方法--改
/**
* 覆寫指定下标元素
*/
public E set(int index, E element) {
//判斷索引是否越界
rangeCheck(index);
//擷取舊元素
E oldValue = elementData(index);
//覆寫為新元素
elementData[index] = element;
//傳回舊元素
return oldValue;
}
/**
* 判斷下标是否越界
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} 4.get方法--查
/**
* 傳回指定索引的值
*/
public E get(int index) {
//判斷索引是否越界
rangeCheck(index);
return elementData(index);
}
/**
* @author jiaxiaoxian
* @date 2019年2月12日
* 傳回下标元素的 值
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
} 5.indexOf方法--查找下标
/**
* 查找下标， 如果為null,直接和null比較，傳回下标
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 查找最後出現的下标，從大往下循環查找
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
} 6.clone方法--克隆
/**
* 複制，傳回此ArrayList 的淺拷貝
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
} 7.trimToSize方法--删除備援容量
/**
* 判斷資料實際容量大小，删除自動增長後備援的容量
* 該方法用于回收多餘的記憶體。也就是說一旦我們确定集合不在添加多餘的元素之後，調用 trimToSize() 方法會将實作集合的數組大小剛好調整為集合元素的大小。
* 注意：該方法會花時間來複制數組元素，是以應該在确定不會添加元素之後在調用
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
} ArrayList總結
1）arrayList可以存放null，本質是Object[]類型的數組。
2）arrayList差別于數組的地方在于能夠自動擴充大小，其中關鍵的方法就是gorw()方法。
3）arrayList由于本質是數組，是以它在資料的查詢方面會很快，而在插入删除這些方面，性能下降很多，有移動很多資料才能達到應有的效果，而LinkedList則相反。
4）arrayList實作了RandomAccess，是以在周遊它的時候推薦使用for循環。
5）初始化數組時推薦給初始長度，反複擴容會增加時耗，影響性能效率。 ©著作權歸作者所有：來自51CTO部落格作者jiazhipeng12的原創作品，如需轉載，請注明出處，否則将追究法律責任