ArrayList簡介

　　ArrayList是基于數(shù)組實現(xiàn)的，是一個動態(tài)數(shù)組，其容量能自動增長，類似于C語言中的動態(tài)申請內(nèi)存，動態(tài)增長內(nèi)存。

　　ArrayList不是線程安全的，只能用在單線程環(huán)境下，多線程環(huán)境下可以考慮用Collections.synchronizedList(List l)函數(shù)返回一個線程安全的ArrayList類，也可以使用concurrent并發(fā)包下的CopyOnWriteArrayList類。

　　ArrayList實現(xiàn)了Serializable接口，因此它支持序列化，能夠通過序列化傳輸，實現(xiàn)了RandomAccess接口，支持快速隨機(jī)訪問，實際上就是通過下標(biāo)序號進(jìn)行快速訪問，實現(xiàn)了Cloneable接口，能被克隆。

ArrayList源碼

　　ArrayList的源碼如下（加入了簡單的注釋，版本號為1.56）：

/**@(#)ArrayList.java 1.56 06/04/21* Copyright 2006 Sun Microsystems, Inc. All rights reserved.* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.*/package java.util;/*** @author Josh Bloch* @author Neal Gafter* @version 1.56, 04/21/06* @see Collection* @see List* @see LinkedList* @see Vector* @since 1.2*/public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private static final long serialVersionUID = 8683452581122892189L;//?ArrayList基于該數(shù)組實現(xiàn)，用該數(shù)組保存數(shù)據(jù)private transient Object[] elementData;// 實際大小private int size;// 帶容量大小的構(gòu)造函數(shù)public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];}// 默認(rèn)構(gòu)造函數(shù)public ArrayList() {this(10);}// Collection構(gòu)造函數(shù)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)elementData = Arrays.copyOf(elementData, size, Object[].class);}// 當(dāng)前容量值為實際個數(shù)public void trimToSize() {modCount++;int oldCapacity = elementData.length;if (size < oldCapacity) {elementData = Arrays.copyOf(elementData, size);}}// 確定ArrayList容量// 若容量不足以容納當(dāng)前全部元素，則擴(kuò)容，新的容量=“(原始容量x3)/2?+?1”public void ensureCapacity(int minCapacity) {modCount++;int oldCapacity = elementData.length;if (minCapacity > oldCapacity) {Object oldData[] = elementData;int newCapacity = (oldCapacity * 3)/2 + 1;if (newCapacity < minCapacity)newCapacity = minCapacity;// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}}// 返回實際大小public int size() {return size;}// 清空public boolean isEmpty() {return size == 0;}// 是否包含opublic boolean contains(Object o) {return indexOf(o) >= 0;}// 正向查找，返回o的indexpublic 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;}// 逆向查找，返回o的indexpublic 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;}// 克隆函數(shù)public Object clone() {try {ArrayList<E> v = (ArrayList<E>) super.clone();v.elementData = Arrays.copyOf(elementData, size);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// this shouldn't happen, since we are Cloneablethrow new InternalError();}}// 返回ArrayList的Object數(shù)組public Object[] toArray() {return Arrays.copyOf(elementData, size);}// 返回ArrayList組成的數(shù)組public <T> T[] toArray(T[] a) {if (a.length < size)// Make a new array of a's runtime type, but my contents:return (T[]) Arrays.copyOf(elementData, size, a.getClass());System.arraycopy(elementData, 0, a, 0, size);if (a.length > size)a[size] = null;return a;}// Positional Access Operations// 得到index位置的元素public E get(int index) {RangeCheck(index);return (E) elementData[index];}// 向index插入elementpublic E set(int index, E element) {RangeCheck(index);E oldValue = (E) elementData[index];elementData[index] = element;return oldValue;}// 添加epublic boolean add(E e) {ensureCapacity(size + 1); // Increments modCount!!elementData[size++] = e;return true;}// 向index插入elementpublic void add(int index, E element) {if (index > size || index < 0)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);ensureCapacity(size+1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}// 移除index位置的元素public E remove(int index) {RangeCheck(index);modCount++;E oldValue = (E) elementData[index];int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // Let gc do its workreturn oldValue;}// 移除opublic 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;}// 快速移除index位置的元素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; // Let gc do its work}// 清空public void clear() {modCount++;// Let gc do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}// 添加Collectionpublic boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacity(size + numNew); // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}// 在index添加Collectionpublic boolean addAll(int index, Collection<? extends E> c) {if (index > size || index < 0)throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);Object[] a = c.toArray();int numNew = a.length;ensureCapacity(size + numNew); // Increments modCountint 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);// Let gc do its workint newSize = size - (toIndex-fromIndex);while (size != newSize)elementData[--size] = null;}// 移除index位置的元素private void RangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);}// java.io.Serializable的寫入函數(shù),將ArrayList的“容量，所有的元素值”都寫入到輸出流中private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount = modCount;s.defaultWriteObject();// Write out array lengths.writeInt(elementData.length);// 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();}}// java.io.Serializable的讀取函數(shù)：根據(jù)寫入方式讀出,先將ArrayList的“容量”讀出，然后將“所有的元素值”讀出private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in size, and any hidden stuffs.defaultReadObject();// Read in array length and allocate arrayint arrayLength = s.readInt();Object[] a = elementData = new Object[arrayLength];// Read in all elements in the proper order.for (int i=0; i<size; i++)a[i] = s.readObject();} }

?

ArrayList詳細(xì)分析

1.構(gòu)造函數(shù)

ArrayList有三個構(gòu)造函數(shù)，如下(英文注釋全部刪掉，默認(rèn)代碼折疊，太占地方了)：

private transient Object[] elementData;private int size;public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];}public ArrayList() {this(10);}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)elementData = Arrays.copyOf(elementData, size, Object[].class);}

　　從第一句話可以看到，ArrayList本質(zhì)上是一個Object類型的數(shù)組，前面加入了transient關(guān)鍵字，在序列化的時候忽略，但是在最后自己重寫了writeObject和readObject這兩個函數(shù)，第一個是構(gòu)造傳入固定大小的ArrayList，第二個是默認(rèn)大小為10，第三個是將傳入的Collection轉(zhuǎn)成ArrayList。

　　序列化有2種方式：?

　　A、只是實現(xiàn)了Serializable接口。?

　　　　序列化時，調(diào)用java.io.ObjectOutputStream的defaultWriteObject方法，將對象序列化。?

　　　　注意：此時transient修飾的字段，不會被序列化。?

　　B、實現(xiàn)了Serializable接口，同時提供了writeObject方法。?

　　　　序列化時，會調(diào)用該類的writeObject方法。而不是java.io.ObjectOutputStream的defaultWriteObject方法。?

　　　　注意：此時transient修飾的字段，是否會被序列化，取決于writeObject

2.自動擴(kuò)容函數(shù)

public void ensureCapacity(int minCapacity) {modCount++;int oldCapacity = elementData.length;if (minCapacity > oldCapacity) {Object oldData[] = elementData;int newCapacity = (oldCapacity * 3)/2 + 1;if (newCapacity < minCapacity)newCapacity = minCapacity;// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}}

　　關(guān)鍵在這里int newCapacity = (oldCapacity * 3)/2 + 1;新的數(shù)組大小是舊的數(shù)組大小的二分之三加一，然后調(diào)用Arrays.copyOf(elementData, newCapacity);得到新的elementData對象。說到這里我默默的翻看了一下jdk1.7的源碼，發(fā)現(xiàn)在jdk1.7當(dāng)中，擴(kuò)容效率有了本質(zhì)上的提高，請看下面的代碼：（出自jdk1.7）

public void ensureCapacity(int minCapacity) {if (minCapacity > 0)ensureCapacityInternal(minCapacity);}private void ensureCapacityInternal(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);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);}

　　1.7相比較1.6，自動擴(kuò)容增加了兩個方法，增加了數(shù)組擴(kuò)容時的判斷，最重要的是這句話：int newCapacity = oldCapacity + (oldCapacity >> 1);沒有再用*3再/2這種低端的玩法，直接采用了移位運算，我不是太懂十進(jìn)制數(shù)的移位運算，經(jīng)過幾次自己的測試發(fā)現(xiàn)如果是偶數(shù)，這個移位運算正好是一半，如果是奇數(shù)，則是向下取整。

?

3.存儲

　　第一判斷ensureSize，如果夠直接插入，否則按照policy擴(kuò)展，復(fù)制，重建數(shù)組。

　　第二步插入元素。

　　ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)這些添加元素的方法。

　　3.1. set(int index, E element),取代，而非插入，返回被取代的元素

public E set(int index, E element) {RangeCheck(index);E oldValue = (E) elementData[index];elementData[index] = element;return oldValue;}

　　3.2.add(E e) 增加元素到末尾，如果size不溢出，自動增長

public boolean add(E e) {ensureCapacity(size + 1); // Increments modCount!!elementData[size++] = e;return true;}

　　3.3.add(int index, E element) 增加元素到某個位置，該索引之后的元素都后移一位

public void add(int index, E element) {if (index > size || index < 0)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);ensureCapacity(size+1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}

　　3.4.后面兩個方法都是把集合轉(zhuǎn)換為數(shù)組利用c.toArray，然后利用Arrays.copyOF 方法

public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacity(size + numNew); // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}public boolean addAll(int index, Collection<? extends E> c) {if (index > size || index < 0)throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);Object[] a = c.toArray();int numNew = a.length;ensureCapacity(size + numNew); // Increments modCountint 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;}

4.刪除

一種是按索引刪除，不用查詢，索引之后的element順序左移一位，并將最后一個element設(shè)為null，由gc負(fù)責(zé)回收。

?

public E remove(int index) {RangeCheck(index);modCount++;E oldValue = (E) elementData[index];int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // Let gc do its workreturn oldValue;}

5.Arrays.copyOf

　　源碼如下：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {T[] copy = ((Object)newType == (Object)Object[].class)? (T[]) new Object[newLength]: (T[]) Array.newInstance(newType.getComponentType(), newLength);System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));return copy;}

　　這里有所優(yōu)化，如果是Object類型的，直接new Object數(shù)組，如果不是則通過Array.newInstance(newType.getComponentType(), newLength)方法產(chǎn)生相應(yīng)的數(shù)組類型。通過System.arraycopy實現(xiàn)數(shù)組復(fù)制，System是個final類，arraycopy是個native方法。

　　該方法被標(biāo)記了native，調(diào)用了系統(tǒng)的C/C++代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。該函數(shù)實際上最終調(diào)用了C語言的memmove()函數(shù)，因此它可以保證同一個數(shù)組內(nèi)元素的正確復(fù)制和移動，比一般的復(fù)制方法的實現(xiàn)效率要高很多，很適合用來批量處理數(shù)組。Java強(qiáng)烈推薦在復(fù)制大量數(shù)組元素時用該方法，以取得更高的效率。

6.Arrays.newInstance()的意義

　　Java反射技術(shù)除了可以在運行時動態(tài)地決定要創(chuàng)建什么類型的對象，訪問哪些成員變量，方法，還可以動態(tài)地創(chuàng)建各種不同類型，不同維度的數(shù)組。

?

　　動態(tài)創(chuàng)建數(shù)組的步驟如下：
　　　　1.創(chuàng)建Class對象，通過forName(String)方法指定數(shù)組元素的類型
　　　　2.調(diào)用Array.newInstance(Class, length_of_array)動態(tài)創(chuàng)建數(shù)組

?

　　訪問動態(tài)數(shù)組元素的方法和通常有所不同，它的格式如下所示，注意該方法返回的是一個Object對象
　　Array.get(arrayObject, index)

　

　　為動態(tài)數(shù)組元素賦值的方法也和通常的不同，它的格式如下所示， 注意最后的一個參數(shù)必須是Object類型
　　Array.set(arrayObject, index, object)

?

　　動態(tài)數(shù)組Array不單可以創(chuàng)建一維數(shù)組，還可以創(chuàng)建多維數(shù)組。步驟如下：
　　　　1.定義一個整形數(shù)組：例如int[] dims= new int{5, 10, 15};指定一個三維數(shù)組
　　　　2.調(diào)用Array.newInstance(Class, dims);創(chuàng)建指定維數(shù)的數(shù)組

?

　　訪問多維動態(tài)數(shù)組的方法和訪問一維數(shù)組的方式?jīng)]有什么大的不同，只不過要分多次來獲取，每次取出的都是一個Object，直至最后一次，賦值也一樣。

?

　　動態(tài)數(shù)組Array可以轉(zhuǎn)化為普通的數(shù)組，例如:
　　Array arry = Array.newInstance(Integer.TYPE,5);
　　int arrayCast[] = (int[])array;

7.為何要序列化

　　ArrayList 實現(xiàn)了java.io.Serializable接口，在需要序列化的情況下，復(fù)寫writeObjcet和readObject方法提供適合自己的序列化方法。

　　1、序列化是干什么的？

　　　　簡單說就是為了保存在內(nèi)存中的各種對象的狀態(tài)（也就是實例變量，不是方法），并且可以把保存的對象狀態(tài)再讀出來。雖然你可以用你自己的各種各樣的方法來保存object states，但是Java給你提供一種應(yīng)該比你自己好的保存對象狀態(tài)的機(jī)制，那就是序列化。

　　2、什么情況下需要序列化

　　　　a）當(dāng)你想把的內(nèi)存中的對象狀態(tài)保存到一個文件中或者數(shù)據(jù)庫中時候；

　　　　b）當(dāng)你想用套接字在網(wǎng)絡(luò)上傳送對象的時候；

　　　　c）當(dāng)你想通過RMI傳輸對象的時候；

8.總結(jié)

　　8.1.Arraylist基于數(shù)組實現(xiàn)，是自增長的

　　8.2.非線程安全的

　　8.3.插入時可能要擴(kuò)容，刪除時size不會減少，如果需要，可以使用trimToSize方法，在查詢時，遍歷查詢，為null，判斷是否是null， 返回； 如果不是null，用equals判斷，返回

/*** Returns <tt>true</tt> if this list contains the specified element.* More formally, returns <tt>true</tt> if and only if this list contains* at least one element <tt>e</tt> such that* <tt>(o==null???e==null?:?o.equals(e))</tt>.** @param o element whose presence in this list is to be tested* @return <tt>true</tt> if this list contains the specified element*/public boolean contains(Object o) {return indexOf(o) >= 0;}/*** Returns the index of the first occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the lowest index <tt>i</tt> such that* <tt>(o==null???get(i)==null?:?o.equals(get(i)))</tt>,* or -1 if there is no such index.*/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;}

　　8.4. 允許重復(fù)和 null 元素

?————————————————————————————————————————————————————————————

參考資料：

【Java集合源碼剖析】ArrayList源碼剖析

集合類學(xué)習(xí)之Arraylist 源碼分析

轉(zhuǎn)載于:https://www.cnblogs.com/babycomeon/p/5630482.html

總結(jié)

以上是生活随笔為你收集整理的Java集合源码分析（二）ArrayList的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。