給jdk寫注釋系列之jdk1.6容器(1)-ArrayList源碼解析

2.底層存儲

顧名思義哈，ArrayList就是用數組實現的List容器，既然是用數組實現，當然底層用數組來保存數據啦。。。

private transient Object[] elementData;
private int size;

/**


 * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 * is, serialize it).
 *
 * @serialData The length of the array backing the <tt>ArrayList </tt>
 *             instance is emitted (int), followed by all of its elements
 *             (each an <tt>Object</tt> ) in the proper order.
 */
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 array length
    s.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();
    }

}

/**
 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 * deserialize it).
 */
private 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();
    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();
}</pre> 

 英語注釋很詳細，也很容易讀懂，就不進行翻譯了。那么想一下為什么要這樣設計呢，豈不是很麻煩。下面簡單進行解釋下： 
  elementData    是一個數據存儲數組，而數組是定長的，它會初始化一個容量，等容量不足時再擴充容量（擴容方式為數據拷貝，后面會詳細解釋），再通俗一點說就是比如  elementData    的長度是10，而里面只保存了3個對象，那么數組中其余的7個元素（null）是沒有意義的，所以也就不需要保存，以節省序列化后的內存容量，好了到這里就明白了這樣設計的初衷和好處，順便好像也明白了長度單獨用一個int變量保存，而不是直接使用 elementData.length的原因。 
 3.構造方法 
/**


 * 構造一個具有指定容量的list
 */
public ArrayList( int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException( "Illegal Capacity: " +
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

/**
 * 構造一個初始容量為10的list
 */
public ArrayList() {
    this(10);
}

/**
 * 構造一個包含指定元素的list，這些元素的是按照Collection的迭代器返回的順序排列的
 */
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);
}</pre> 

 構造方法看完了，想一下指定容量的構造方法的意義，既然默認為10就可以那么為什么還要提供一個可以指定容量大小的構造方法呢？在這里說好像有點太早，那就賣個關子，下面再說 。。 。 
 4.增加 
/**


 * 添加一個元素
 */
public boolean add(E e) {
   // 進行擴容檢查
   ensureCapacity( size + 1);  // Increments modCount
   // 將e增加至list的數據尾部，容量+1
    elementData[size ++] = e;
    return true;
}

/**
 * 在指定位置添加一個元素
 */
public void add(int index, E element) {
    // 判斷索引是否越界，這里會拋出多么熟悉的異常。。。
    if (index > size || index < 0)
       throw new IndexOutOfBoundsException(
           "Index: "+index+", Size: " +size);

   // 進行擴容檢查
   ensureCapacity( size+1);  // Increments modCount  
   // 對數組進行復制處理，目的就是空出index的位置插入element，并將index后的元素位移一個位置
   System. arraycopy(elementData, index, elementData, index + 1,
                  size - index);
   // 將指定的index位置賦值為element
    elementData[index] = element;
   // list容量+1
    size++;
}
/**
 * 增加一個集合元素
 */
public boolean addAll(Collection<? extends E> c) {
   //將c轉換為數組
   Object[] a = c.toArray();
    int numNew = a.length ;
   //擴容檢查
   ensureCapacity( size + numNew);  // Increments modCount
   //將c添加至list的數據尾部
    System. 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 modCount

   // 計算需要移動的長度（index之后的元素個數）
    int numMoved = size - index;
   // 數組復制，空出第index到index+numNum的位置，即將數組index后的元素向右移動numNum個位置
    if (numMoved > 0)
       System. arraycopy(elementData, index, elementData, index + numNew,
                      numMoved);

   // 將要插入的集合元素復制到數組空出的位置中
    System. arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

/**
 * 數組容量檢查，不夠時則進行擴容
 */

public void ensureCapacity( int minCapacity) {
        modCount++;
       // 當前數組的長度
        int oldCapacity = elementData .length;
       // 最小需要的容量大于當前數組的長度則進行擴容
        if (minCapacity > oldCapacity) {
           Object oldData[] = elementData;
          // 新擴容的數組長度為舊容量的1.5倍+1
           int newCapacity = (oldCapacity * 3)/2 + 1;
          // 如果新擴容的數組長度還是比最小需要的容量小，則以最小需要的容量為長度進行擴容
           if (newCapacity < minCapacity)
              newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            // 進行數據拷貝，Arrays.copyOf底層實現是System.arrayCopy()
            elementData = Arrays.copyOf( elementData, newCapacity);
       }
    }</pre> 
  
 5.刪除 

/**


 * 根據索引位置刪除元素
 */
public E remove( int index) {
  // 數組越界檢查
   RangeCheck(index);

    modCount++;
  // 取出要刪除位置的元素，供返回使用
   E oldValue = (E) elementData[index];
   // 計算數組要復制的數量
    int numMoved = size - index - 1;
   // 數組復制，就是將index之后的元素往前移動一個位置
    if (numMoved > 0)
       System. arraycopy(elementData, index+1, elementData, index,
                      numMoved);
   // 將數組最后一個元素置空（因為刪除了一個元素，然后index后面的元素都向前移動了，所以最后一個就沒用了），好讓gc盡快回收
   // 不要忘了size減一
    elementData[--size ] = null; // Let gc do its work

    return oldValue;
}

/**
 * 根據元素內容刪除，只刪除匹配的第一個
 */
public boolean remove(Object o) {
   // 對要刪除的元素進行null判斷
   // 對數據元素進行遍歷查找，知道找到第一個要刪除的元素，刪除后進行返回，如果要刪除的元素正好是最后一個那就慘了，時間復雜度可達O(n) 。。。
    if (o == null) {
        for (int index = 0; index < size; index++)
          // null值要用==比較
           if (elementData [index] == null) {
              fastRemove(index);
              return true;
          }
   } else {
       for (int index = 0; index < size; index++)
          // 非null當然是用equals比較了
           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++;
   // 原理和之前的add一樣，還是進行數組復制，將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
}

/**
 * 數組越界檢查
 */
private void RangeCheck(int index) {
    if (index >= size )
       throw new IndexOutOfBoundsException(
           "Index: "+index+", Size: " +size);
}</pre> 

 
   
PS：看到了這個方法，便可jdk源碼有些地方寫的也不是那么精巧，比如這里remove時將數組越界檢查封裝成了一個單獨方法，可是往前翻一下add方法中的數組越界就沒有進行封裝，需要檢查的時候都是寫一遍一樣的代碼，why啊。。。

   
增加和刪除方法到這里就解釋完了，代碼是很簡單，主要需要特別關心的就兩個地方：1.數組擴容，2.數組復制，這兩個操作都是極費效率的，最慘的情況下(添加到list第一個位置，刪除list最后一個元素或刪除list第一個索引位置的元素)時間復雜度可達O(n)。

   
還記得上面那個坑嗎（為什么提供一個可以指定容量大小的構造方法 ）？看到這里是不是有點明白了呢，簡單解釋下：如果數組初試容量過小，假設默認的10個大小，而我們使用ArrayList的主要操作時增加元素，不斷的增加，一直增加，不停的增加，會出現上面后果？那就是數組容量不斷的受挑釁，數組需要不斷的進行擴容，擴容的過程就是數組拷貝System.arraycopy的過程，每一次擴容就會開辟一塊新的內存空間和數據的復制移動，這樣勢必對性能造成影響。那么在這種以寫為主（寫會擴容，刪不會縮容）場景下，提前預知性的設置一個大容量，便可減少擴容的次數，提高了性能。

  
 
   
圖1.

   
  

   
圖2.

   
  

   
上面兩張圖分別是數組擴容和數組復制的過程，需要注意的是，數組擴容伴隨著開辟新建的內存空間以創建新數組然后進行數據復制，而數組復制不需要開辟新內存空間，只需將數據進行復制。

   
 上面講增加元素可能會進行擴容，而刪除元素卻不會進行縮容，如果在已刪除為主的場景下使用list，一直不停的刪除而很少進行增加，那么會出現什么情況？再或者數組進行一次大擴容后，我們后續只使用了幾個空間，會出現上面情況？當然是空間浪費啦啦啦，怎么辦呢？        

  
/**


 * 將底層數組的容量調整為當前實際元素的大小，來釋放空間。
 */
public void trimToSize() {
    modCount++;
   // 當前數組的容量
    int oldCapacity = elementData .length;
   // 如果當前實際元素大小 小于 當前數組的容量，則進行縮容
    if (size < oldCapacity) {
        elementData = Arrays.copyOf( elementData, size );
   }</pre> 

 6.更新   
/**


 * 將指定位置的元素更新為新元素
 */
public E set( int index, E element) {
   // 數組越界檢查
   RangeCheck(index);

   // 取出要更新位置的元素，供返回使用
   E oldValue = (E) elementData[index];
   // 將該位置賦值為行的元素
    elementData[index] = element;
   // 返回舊元素
    return oldValue;
}</pre> 

 7.查找 
/**


 * 查找指定位置上的元素
 */
public E get( int index) {
   RangeCheck(index);

    return (E) elementData [index];
}</pre> 

 由于ArrayList使用數組實現，更新和查找直接基于下標操作，變得十分簡單。 
 8.是否包含 
/**


 * 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;
}

/**
 * Returns the index of the last occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the highest 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 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;
}</pre> 

  contains主要是檢查indexOf，也就是元素在list中出現的索引位置也就是數組下標，再看   indexOf和 lastIndexOf代碼是不是很熟悉，沒錯，和  public     boolean  remove(Object o)   的代碼一樣，都是元素null判斷，都是循環比較，不多說了。。。但是要知道，最差的情況（要找的元素是最后一個）也是很慘的。。。  
 9.容量判斷 
/**


 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
    return size ;
}

/**
 * Returns <tt>true</tt> if this list contains no elements.
 *
 * @return <tt> true</tt> if this list contains no elements
 */
public boolean isEmpty() {
    return size == 0;
}</pre> 

 
   
由于使用了size進行計數，發現list大小獲取和判斷真的好容易。。。

   
 好了，至此ArrayList的分析和注釋就基本完成了。什么還差些什么？對， modCount 是干什么的，怎么到處都在操作這個變量，還有遍歷呢，為啥不講？由于iterator遍歷相對比較復雜，而且iterator 是GoF經典  設計模式  比較重要的一個，之后會對iterator單獨分析，這里就不啰嗦了。。。 

   
ArrayList，完！

  
</div>
 </div>
來自： http://www.importnew.com/17440.html