Java2源碼解讀：java.util.ArrayList

2019-11-18 11:19:11

字體：大中小

來源：轉載

供稿：網友

　　ArrayList是List接口的一個可變長數組實現。實現了所有List接口的操作，并答應存儲null值。除了沒有進行同步，ArrayList基本等同于Vector。在Vector中幾乎對所有的方法都進行了同步，但ArrayList僅對writeObject和readObject進行了同步，其它比如add(Object)、remove(int)等都沒有同步。
　　
　　1.存儲
　　ArrayList使用一個Object的數組存儲元素。
　　PRivate transient Object elementData[];
　　ArrayList實現了java.io.Serializable接口，這兒的transient標示這個屬性不需要自動序列化。下面會在writeObject()方法中具體講解為什么要這樣作。
　　
　　2.add和remove
　　
　　　　public boolean add(Object o) {
　　　　ensureCapacity(size + 1);　// Increments modCount!!
　　　　elementData[size++] = o;
　　　　return true;
　　　　}
　　
　　注重這兒的ensureCapacity()方法，它的作用是保證elementData數組的長度可以容納一個新元素。在“自動變長機制”中將具體講解。
　　　　public Object remove(int index) {
　　　　RangeCheck(index);
　　　　modCount++;
　　　　Object oldValue = 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 work
　　　　return oldValue;
　　　　}
　　
　　RangeCheck()的作用是進行邊界檢查。由于ArrayList采用一個對象數組存儲元素，所以在刪除一個元素時需要把后面的元素前移。刪除一個元素時只是把該元素在elementData數組中的引用置為null，具體的對象的銷毀由垃圾收集器負責。
　　modCount的作用將在下面的“iterator()中的同步”中說明。
　　注：在前移時使用了System提供的一個實用方法：arraycopy()，在本例中可以看出System.arraycopy()方法可以對同一個數組進行操作，這個方法是一個native方法，假如對同一個數組進行操作時，會首先把從源部分拷貝到一個臨時數組，在把臨時數組的元素拷貝到目標位置。
　　
　　3.自動變長機制
　　在實例化一個ArrayList時，你可以指定一個初始容量。這個容量就是elementData數組的初始長度。假如你使用：
　　　　ArrayList list = new ArrayList();
　　
　　則使用缺省的容量：10。
　　　　public ArrayList() {
　　　　this(10);
　　　　}
　　
　　ArrayList提供了四種add()方法，
　　
　　public boolean add(Object o)
　　
　　public void add(int index, Object element)
　　
　　public boolean addAll(Collection c)
　　
　　public boolean addAll(int index, Collection c)
　　
　　在每一種add()方法中，都首先調用了一個ensureCapacity(int miniCapacity)方法，這個方法保證elementData數組的長度不小于miniCapacity。ArrayList的自動變長機制就是在這個方法中實現的。
　　　　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;
　　　　　　elementData = new Object[newCapacity];
　　　　　　System.arraycopy(oldData, 0, elementData, 0, size);
　　　　}
　　　　}
　　
　　從這個方法實現中可以看出ArrayList每次擴容，都擴大到原來大小的1.5倍。
　　每種add()方法的實現都大同小異，下面給出add(Object)方法的實現：
　　　　public boolean add(Object o) {
　　　　ensureCapacity(size + 1);　// Increments modCount!!
　　　　elementData[size++] = o;
　　　　return true;
　　　　}
　　
　　
　　4.iterator()中的同步
　　在父類AbstractList中定義了一個int型的屬性：modCount，記錄了ArrayList結構性變化的次數。
　　　　protected transient int modCount = 0;
　　
　　在ArrayList的所有涉及結構變化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。這些方法每調用一次，modCount的值就加1。
　　注：add()及addAll()方法的modCount的值是在其中調用的ensureCapacity()方法中增加的。
　　
　　AbstractList中的iterator()方法（ArrayList直接繼續了這個方法）使用了一個私有內部成員類Itr，生成一個Itr對象（Iterator接口）返回：
　　　　public Iterator iterator() {
　　　　return new Itr();
　　　　}
　　
　　Itr實現了Iterator()接口，其中也定義了一個int型的屬性：eXPectedModCount，這個屬性在Itr類初始化時被賦予ArrayList對象的modCount屬性的值。
　　　　int expectedModCount = modCount;
　　
　　注：內部成員類Itr也是ArrayList類的一個成員，它可以訪問所有的AbstractList的屬性和方法。理解了這一點，Itr類的實現就輕易理解了。
　　
　　在Itr.hasNext()方法中：
　　　　public boolean hasNext() {
　　　　　　return cursor != size();
　　　　}
　　
　　調用了AbstractList的size()方法，比較當前光標位置是否越界。
　　
　　在Itr.next()方法中，Itr也調用了定義在AbstractList中的get(int)方法，返回當前光標處的元素：
　　　　public Object next() {
　　　　　　try {
　　　　　　Object next = get(cursor);
　　　　　　checkForComodification();
　　　　　　lastRet = cursor++;
　　　　　　return next;
　　　　　　} catch(IndexOutOfBoundsException e) {
　　　　　　checkForComodification();
　　　　　　throw new NoSUChElementException();
　　　　　　}
　　　　}
　　
　　注重，在next()方法中調用了checkForComodification()方法，進行對修改的同步檢查：
　　　　final void checkForComodification() {
　　　　　　if (modCount != expectedModCount)
　　　　　　throw new ConcurrentModificationException();
　　　　}
　　
　　現在對modCount和expectedModCount的作用應該非常清楚了。在對一個集合對象進行跌代操作的同時，并不限制對集合對象的元素進行操作，這些操作包括一些可能引起跌代錯誤的add()或remove()等危險操作。在AbstractList中，使用了一個簡單的機制來規避這些風險。這就是modCount和expectedModCount的作用所在。
　　
　　5.序列化支持
　　ArrayList實現了java.io.Serializable接口，所以ArrayList對象可以序列化到持久存儲介質中。ArrayList的主要屬性定義如下：
　　
　　private static final long serialVersionUID = 8683452581122892189L;
　　
　　private transient Object elementData[];
　　
　　private int size;
　　
　　可以看出serialVersionUID和size都將自動序列化到介質中，但elementData數組對象卻定義為transient了。也就是說ArrayList中的所有這些元素都不會自動系列化到介質中。為什么要這樣實現？因為elementData數組中存儲的“元素”其實僅是對這些元素的一個引用，并不是真正的對象，序列化一個對象的引用是毫無意義的，因為序列化是為了反序列化，當你反序列化時，這些對象的引用已經不可能指向原來的對象了。所以在這兒需要手工的對ArrayList的元素進行序列化操作。這就是writeObject()的作用。
　　　　private synchronized void writeObject(java.io.ObjectOutputStream s)
　　　　　　throws java.io.IOException{
　　　　// Write out element count, and any hidden stuff
　　　　s.defaultWriteObject();
　　　 // Write out array length
　　　　s.writeInt(elementData.length);
　　　　// Write out all elements in the proper order.
　　　　for (int i=0; i　　　　　　　　s.writeObject(elementData[i]);
　　　　}
　　
　　這樣元素數組elementData中的所以元素對象就可以正確地序列化到存儲介質了。
　　對應的readObject()也按照writeObject()方法的順序從輸入流中讀?。?br />　　　　private synchronized void readObject(java.io.ObjectInputStream s)
　　　　　　throws java.io.IOException, ClassNotFoundException {
　　　　// Read in size, and any hidden stuff
　　　　s.defaultReadObject();
　　　　// Read in array length and allocate array
　　　　int arrayLength = s.readInt();
　　　　elementData = new Object[arrayLength];
　　　　// Read in all elements in the proper order.
　　　　for (int i=0; i　　　　　　　　elementData[i] = s.readObject();
　　　　}

上一篇：垃圾自動收集系統指導(2)

下一篇：Sun用AppServer8.0反擊對手