1、ArrayList源碼解析 源碼解析: 如下源碼來自JDK8:。 (以上所有內容皆為個人筆記,如有錯誤之處還望指正。) ...
1、ArrayList源碼解析
源碼解析:
- 如下源碼來自JDK8(如需查看ArrayList擴容源碼解析請跳轉至《Java中的容器(集合)》第十條):。
package java.util; import java.util.function.Consumer; import java.util.function.Predicate; import java.util.function.UnaryOperator; import sun.misc.SharedSecrets; //其中實現了RandomAccess介面表示支持隨機訪問 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //序列號 private static final long serialVersionUID = 8683452581122892189L; /** * 預設初始容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 共用的空數組實例(用於空實例) * 當ArrayList(int initialCapacity),ArrayList(Collection<? extends E> c)中的容量等於0的時候使用 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 共用的空數組實例(用於預設大小的空實例) * 將其與EMPTY_ELEMENTDATA區分開來,主要是為了知道第一次添加元素的時候需要擴容多少 * 用於ArrayList()構造器 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * ArrayList保存有序元素的數組 * ArraylList容量為數組容量 * 任何空數組都使用 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * 當第一次添加元素的時候其容量將會擴容至 DEFAULT_CAPACITY(10) */ transient Object[] elementData; // non-private to simplify nested class access /** * ArrayList的大小(包含元素的數量) * @serial */ private int size; /** * 帶指定容量參數的構造器,如果元素數量較大的話,可以使用此構造器,防止頻繁擴容造成的性能損失 */ public ArrayList(int initialCapacity) { //如果傳入值大於0,則創建一個該容量大小的數組。 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //否則如果傳入值等於0,則創建預設空數組 this.elementData = EMPTY_ELEMENTDATA; } else { //如果小於0則拋出異常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 預設構造函數,其初始容量為10(註意,這裡一開始其實是一個空數組,只是當add時才會進行擴容至10的操作,一定程度上減小了記憶體消耗。) */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 構造一個包含指定集合元素的列表,元素順序由集合的迭代器所返回。 */ public ArrayList(Collection<? extends E> c) { //集合轉數組 elementData = c.toArray(); //指定集合含有元素 if ((size = elementData.length) != 0) { // c.toArray可能不會返回Object[] (see 6260652) //使用反射進行運行時判斷elementData是否屬於Object[] if (elementData.getClass() != Object[].class) //拷貝數組 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 由空數組代替 this.elementData = EMPTY_ELEMENTDATA; } } /** * 修改ArrayList容量為list的當前大小 * 一個應用可以使用此操作來最小化一個ArrayList的存儲 */ public void trimToSize() { modCount++; //如果當前數組元素個數小於數組容量 if (size < elementData.length) { //沒有元素返回空數組,否則返回元素個數的數組。 elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } /** * 如果有必要去增加ArrayList的容量,請確保它至少可以容納由最小容量參數指定的元素數量 * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { //預設最小容量,空數組以及預設大小10 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; //如果傳入容量大於最小容量,則進行擴容 if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果elementData為預設空數組,則比較傳入值與預設值(10),返回兩者中的較大值 //elementData為預設空數組指的是通過ArrayList()這個構造器創建的ArrayList對象 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } //返回傳入值 return minCapacity; } private void ensureCapacityInternal(int minCapacity) { //先通過calculateCapacity方法計算最終容量,以確認實際容量 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code //如果最終確認容量大於數組容量,則進行grow()擴容 if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 可分配數組最大大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 增加ArrayList的容量,以確保它至少可以容納由最小容量參數指定的元素數量 * @param minCapacity 所需的最小容量 */ private void grow(int minCapacity) { // overflow-conscious code //oldCapacity表示舊容量 int oldCapacity = elementData.length; //newCapacity表示新容量,計算規則為舊容量+舊容量的0.5,即舊容量的1.5倍。如果超過int的最大值會返回一個負數。 //oldCapacity >> 1表示右移一位,對應除以2的1次方。 int newCapacity = oldCapacity + (oldCapacity >> 1); //如果新容量小於最小容量,則將最小容量賦值給新容量(有時手動擴容可能也會返回<0,對應方法為ensureCapacity()) if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果新容量大於MAX_ARRAY_SIZE,則執行hugeCapacity(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); } private static int hugeCapacity(int minCapacity) { //如果最小容量超過了int的最大值,minCapacity會是一個負數,此時拋出記憶體溢出錯誤 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //比較最小容量是否大於MAX_ARRAY_SIZE,如果是則返回Integer.MAX_VALUE,否則返回MAX_ARRAY_SIZE return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } /** * 返回列表元素數 */ public int size() { return size; } /** * 如果列表不包含元素,返回true */ public boolean isEmpty() { return size == 0; } /** * 如果列表包含指定元素,返回true */ public boolean contains(Object o) { //返回此列表中指定元素第一次出現的索引,如果列表中不包含指定元素,則為-1 return indexOf(o) >= 0; } /** * 返回此列表中指定元素第一次出現的索引,如果列表中不包含指定元素,則為-1 */ 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; } /** * 返回此列表中指定元素最後一次出現的索引,如果列表中不包含指定元素,則為-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; } /** * 返回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); } } /** * 以正確的順序(從第一個到最後一個元素)返回一個包含此列表中所有元素的數組。 * 返回的數組將是“安全的”,因為該列表不保留對它的引用。 (換句話說,這個方法必須分配一個新的數組)。 * 因此,調用者可以自由地修改返回的數組。 此方法充當基於陣列和基於集合的API之間的橋梁。 */ public Object[] toArray() { return Arrays.copyOf(elementData, size); } /** * 以正確的順序返回一個包含此列表中所有元素的數組(從第一個到最後一個元素); * 返回的數組的運行時類型是指定數組的運行時類型。 如果列表適合指定的數組,則返回其中。 * 否則,將為指定數組的運行時類型和此列表的大小分配一個新數組。 * 如果列表適用於指定的數組,其餘空間(即數組的列表數量多於此元素),則緊跟在集合結束後的數組中的元素設置為null 。 *(這僅在調用者知道列表不包含任何空元素的情況下才能確定列表的長度。) */ @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) //創建一個新的運行時類型數組,內容為ArrayList數組的 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } // 位置訪問操作 @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } /** * 返回此列表中指定位置的元素 */ public E get(int index) { //檢查索引是否越界 rangeCheck(index); return elementData(index); } /** * 用指定元素替換列表中的指定位置的元素 */ public E set(int index, E element) { //檢查索引是否越界 rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } /** * 將指定元素追加到數組末尾 */ public boolean add(E e) { //添加之前先確認是否需要擴容 ensureCapacityInternal(size + 1); // Increments modCount!! //新加入的元素是添加在了數組的末尾,隨後數組size自增。 elementData[size++] = e; return true; } /** * 插入指定元素到此列表中的指定位置 * 先調用 rangeCheckForAdd 對index進行界限檢查;然後調用 ensureCapacityInternal 方法保證capacity足夠大; * 再將從index開始之後的所有成員後移一個位置;將element插入index位置;最後size加1。 */ 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++; } /** * 將列表中指定位置的元素移除,後續所有元素移到左端(從他們的索引中減去一個) */ 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; // 清理工作交給GC return oldValue; } /** * 從列表中移除第一次出現的指定元素,如果不存在,則不更改 */ 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 remove method that skips bounds checking and does not * return the value removed. */ 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 } /** * 移除列表中的所有元素,之後會返回一個空數組 */ public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } /** * 將指定集合中的元素以Iterator返回的順序,追加到列表末尾 */ public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } /** * 將指定集合中的元素以Iterator返回的順序,插入到指定位置 */ 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; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; } /** * 移除[fromIndex,toIndex)之間的元素,後續元素移到左端 */ protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } /** *檢查給定索引是否在界限內。 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * add and addAll使用的rangeCheck */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 返回 an IndexOutOfBoundsException 的細節信息 */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } /** * 從列表中移除指定集合包含的所有元素 */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } /** * 保留此列表中指定集合的所有元素 */ public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } //批量移除 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) 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; } /** * 保存ArrayList狀態到一個流中(即序列化) */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } /** * 從一個流中讀取ArrayList(即反序列化) */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); } } } /** * 從列表中的指定位置開始,返回之後所有元素的列表迭代器(按正確的順序) * 指定的索引表示初始調用將返回的第一個元素為next 。 初始調用previous將返回指定索引減1的元素。 * 返回的列表迭代器是fail-fast 。 */ public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } /** * 返回列表中的包含所有元素的列表迭代器(按正確的順序)。 * 返回的列表迭代器是fail-fast 。 */ public ListIterator<E> listIterator() { return new ListItr(0); } /** * 以正確的順序返回列表中的包含所有元素的迭代器。 * 返回的迭代器是fail-fast 。 */ public Iterator<E> iterator() { return new Itr(); } @Override public void forEach(Consumer<? super E> action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } @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; } @Override @SuppressWarnings("unchecked") public void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { elementData[i] = operator.apply((E) elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } @Override @SuppressWarnings("unchecked") public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } }
(以上所有內容皆為個人筆記,如有錯誤之處還望指正。)