容器源码分析之ArrayList(二)
ArrayList的類聲明
首先看一下ArrayList的類聲明
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.SerializableArrayList類主要是繼承AbstractList類并實現(xiàn)了List接口，實現(xiàn)Cloneable，Serializable接口，使得ArrayList具有克隆，序列化功能。
而實現(xiàn)RandomAccess接口使得ArrayList具有快速訪問，即通過下標訪問的功能。
ArrayList的屬性
private static final long serialVersionUID = 8683452581122892189L;transient Object[] elementData; // non-private to simplify nested class access首先我們看到serialVersionUID的聲明，為了保持序列化的兼容性，
參考：Effective Java之謹慎地實現(xiàn)Serializable(七十四)
elementData數(shù)組用來存儲ArrayList中的元素，從這個可以看出，ArrayList是底層是借組于數(shù)組來實現(xiàn)的。為什么聲明為transient呢？
是因為避免默認的序列化帶來的內(nèi)存浪費，參考：Effective Java之考慮自定義的序列化模式(七十五)
有關容器類的序列化問題在后面的容器源碼中就不贅述了，無非就是把默認的序列化不滿足需求，自定義一個序列化。
private int size; private static final int DEFAULT_CAPACITY = 10;size用來記錄ArrayList中存儲的元素的個數(shù)。
DEFAULT_CAPACITY是ArrayList中存儲的元素的默認個數(shù)，默認是10。
private static final Object[] EMPTY_ELEMENTDATA = {};//下面這個是共享空常量數(shù)組private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};這兩個是共享空常量數(shù)組，用于空的實例對象，區(qū)別是DEFAULTCAPACITY_EMPTY_ELEMENTDATA知道如何擴張；
（這里先知道他們的區(qū)別，至于為什么看到后面就知道了）
使用迭代器遍歷的時候，用來檢查列表中的元素是否發(fā)生結構性變化（列表元素數(shù)量發(fā)生改變）了，主要在多線程環(huán)境下需要使用，防止一個線程正在迭代遍歷，另一個線程修改了這個列表的結構，如果這種情況發(fā)生，拋出
ConcurrentModificationException，實現(xiàn)了快速失敗(fail-fast)。
ArrayList的構造函數(shù)
1.無參構造方法
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}源碼上介紹的功能為：構造一個初始容量為 10 的空列表。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA的長度為什么是10呢？在下面的add(E e)函數(shù)源碼的介紹中會給出答案。
2.指定容量構造方法
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}根據(jù)參數(shù)的大小作為容量來實例化底層的數(shù)組對象，其中對參數(shù)的3中情況進行了處理。當參數(shù)小于0時，拋異常。當參數(shù)等于0時，用空的常量數(shù)組對象EMPTY_ELEMENTDATA來初始化底層數(shù)組elementData。
3.容器作為參數(shù)的構造函數(shù)
public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}將容器Collection轉(zhuǎn)化為數(shù)組賦給數(shù)組elementData，還對Collection轉(zhuǎn)化是否轉(zhuǎn)化為了Object[]進行了檢查判斷。如果Collection為空，則就將空的常量數(shù)組對象EMPTY_ELEMENTDATA賦給了elementData；
Add的所有方法
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}既然此函數(shù)中涉及到ensureCapacityInternal函數(shù)，那我們就看一下這個函數(shù)，源碼如下：
private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}繼續(xù)看
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}從源碼可以看出，如果elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA，則就用默認容量10來進行開辟空間。這里的源碼就解釋了DEFAULTCAPACITY_EMPTY_ELEMENTDATA數(shù)組和EMPTY_ELEMENTDATA數(shù)組的區(qū)別之所在。
當我們用無參構造函數(shù)來實例化一個對象時，只需要調(diào)用一次add(E e) 就能構造的一個長度為10的數(shù)組對象。
小小程序看出端倪：
debug看到的兩個對象區(qū)別
當添加的元素數(shù)目大于了數(shù)組elementData，就grow：
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);/*下面兩個if的作用為處理兩種情況：1）第一種情況為：如果newCapacity擴展的過小。則應該至少擴張到所需的空間大小minCapacity2）第二種情況為：newCapacity擴張的過大，如果過大，則用Integer.MAX_VALUE來代替。*/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);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;int newCapacity = oldCapacity + (oldCapacity >> 1);
這段代碼其實就是把elementData的大小擴展成原來的1.5倍，細心的人會發(fā)現(xiàn)，如果是elementData通過無參構造方法賦值為DEFAULTCAPACITY_EMPTY_ELEMENTDATA數(shù)組那么它將從10開始擴張。
EMPTY_ELEMENTDATA的話它將從2開始擴張。
有存在一個小疑點：
elementData = Arrays.copyOf(elementData, newCapacity);
實際上最終調(diào)用到一個系統(tǒng)方法
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);這是因為C在操作內(nèi)存的效率遠高于Java。所以在許多優(yōu)化文檔中都能看見推薦使用arraycopy方法來批量處理數(shù)組。
終于把add方法有了初步的了解，其他帶參數(shù)的add方法其實都一樣，無非就是
- 檢查參數(shù)的有效性
- 添加addmode，并檢查是否需要擴張
添加元素
其他方法
為什么將其他方法放在同一欄中呢？因為so ez
首先get和set方法就不必多言了，不用看都知道怎么做吧？
remove方法需要注意一下，
其實也就是將數(shù)組從index+1位置開始到末尾的元素拷貝到從index開始處)
也并不是什么高明的方法。
另一個remove的重載方法：
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;}fastRemove(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; // clear to let GC do its work}其實區(qū)別不大，區(qū)別是fastRemove函數(shù)沒有對index進行有效性檢查，以及沒有返回移除的舊值，為什么？想想就知道了～
需要注意的地方：
第一點：有3種遍歷數(shù)組的方法，iterator迭代器，用array.get隨機訪問，用for-each循環(huán)，但是使用隨機訪問(即，通過索引序號訪問)效率最高，而使用迭代器的效率最低！
第二點：ArrayList提供了2個toArray()函數(shù)：
Object[] toArray() <T> T[] toArray(T[] contents)調(diào)用 toArray() 函數(shù)會拋出“java.lang.ClassCastException”異常，但是調(diào)用 toArray(T[] contents) 能正常返回 T[]。
toArray() 會拋出異常是因為 toArray() 返回的是 Object[] 數(shù)組，將 Object[] 轉(zhuǎn)換為其它類型(如如，將Object[]轉(zhuǎn)換為的Integer[])則會拋出“java.lang.ClassCastException”異常，因為Java不支持向下轉(zhuǎn)型。
解決該問題的辦法是調(diào)用 T[] toArray(T[] contents) ， 而不是 Object[] toArray()。
public static Integer[] vectorToArray2(ArrayList<Integer> v) {Integer[] newText = (Integer[])v.toArray(new Integer[0]);return newText; }總結
以上是生活随笔為你收集整理的容器源码分析之ArrayList(二)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Effective Java之考虑用序列
- 下一篇： 容器源码分析之LinkedList(三)