深入學習集合之ArrayList實作原理

1. ArrayList概述：

   ArrayList是List接口的可變數組的實作。實作了所有可選清單操作，并允許包括 null 在内的所有元素。除了實作 List 接口外，此類還提供一些方法來操作内部用來存儲清單的數組的大小。

   每個ArrayList執行個體都有一個容量，該容量是指用來存儲清單元素的數組的大小。它總是至少等于清單的大小。随着向ArrayList中不斷添加元素，其容量也自動增長。自動增長會帶來資料向新數組的重新拷貝，是以，如果可預知資料量的多少，可在構造ArrayList時指定其容量。在添加大量元素前，應用程式也可以使用ensureCapacity操作來增加ArrayList執行個體的容量，這可以減少遞增式再配置設定的數量。 

   注意，此實作不是同步的。如果多個線程同時通路一個ArrayList執行個體，而其中至少一個線程從結構上修改了清單，那麼它必須保持外部同步。

2. ArrayList的實作：

   對于ArrayList而言，它實作List接口、底層使用數組儲存所有元素。其操作基本上是對數組的操作。下面我們來分析ArrayList的源代碼：

1) 底層使用數組實作：

private transient Object[] elementData;       

1. private transient

2) 構造方法： 

   ArrayList提供了三種方式的構造器，可以構造一個預設初始容量為10的空清單、構造一個指定初始容量的空清單以及構造一個包含指定collection的元素的清單，這些元素按照該collection的疊代器傳回它們的順序排列的。

1. public
2. this(10);  
3. }  
4.   
5. public ArrayList(int
6. super();  
7. if (initialCapacity < 0)  
8. throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);  
9. this.elementData = new
10. }  
11.   
12. public ArrayList(Collection<? extends
13.     elementData = c.toArray();  
14.     size = elementData.length;  
15. // c.toArray might (incorrectly) not return Object[] (see 6260652)
16. if (elementData.getClass() != Object[].class)  
17. class);  
18. }      

 3) 存儲： 

   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)這些添加元素的方法。下面我們一一講解：

// 用指定的元素替代此清單中指定位置上的元素，并傳回以前位于該位置上的元素。  
public E set(int index, E element) {  
    RangeCheck(index);  
  
    E oldValue = (E) elementData[index];  
    elementData[index] = element;  
    return oldValue;  
}        

1. // 将指定的元素添加到此清單的尾部。
2. public boolean
3. 1);   
4.     elementData[size++] = e;  
5. return true;  
6. }      

1. // 将指定的元素插入此清單中的指定位置。
2. // 如果目前位置有元素，則向右移動目前位于該位置的元素以及所有後續元素（将其索引加1）。
3. public void add(int
4. if (index > size || index < 0)  
5. throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
6. // 如果數組長度不足，将進行擴容。
7. 1);  // Increments modCount!!
8. // 将 elementData中從Index位置開始、長度為size-index的元素，
9. // 拷貝到從下标為index+1位置開始的新的elementData數組中。
10. // 即将目前位于該位置的元素以及所有後續元素右移一個位置。
11. 1, size - index);  
12.     elementData[index] = element;  
13.     size++;  
14. }      

1. // 按照指定collection的疊代器所傳回的元素順序，将該collection中的所有元素添加到此清單的尾部。
2. public boolean addAll(Collection<? extends
3.     Object[] a = c.toArray();  
4. int
5. // Increments modCount
6. 0, elementData, size, numNew);  
7.     size += numNew;  
8. return numNew != 0;  
9. }      

1. // 從指定的位置開始，将指定collection中的所有元素插入到此清單中。
2. public boolean addAll(int index, Collection<? extends
3. if (index > size || index < 0)  
4. throw new
5. "Index: " + index + ", Size: "
6.   
7.     Object[] a = c.toArray();  
8. int
9. // Increments modCount
10.   
11. int
12. if (numMoved > 0)  
13.         System.arraycopy(elementData, index, elementData, index + numNew, numMoved);  
14.   
15. 0, elementData, index, numNew);  
16.     size += numNew;  
17. return numNew != 0;  
18. }      

 4) 讀取：

1. // 傳回此清單中指定位置上的元素。
2. public E get(int
3.     RangeCheck(index);  
4.   
5. return
6. }      

  5) 删除： 

   ArrayList提供了根據下标或者指定對象兩種方式的删除功能。如下：

1. // 移除此清單中指定位置上的元素。
2. public E remove(int
3.     RangeCheck(index);  
4.   
5.     modCount++;  
6.     E oldValue = (E) elementData[index];  
7.   
8. int numMoved = size - index - 1;  
9. if (numMoved > 0)  
10. 1, elementData, index, numMoved);  
11. null; // Let gc do its work
12.   
13. return
14. }      

1. // 移除此清單中首次出現的指定元素（如果存在）。這是應為ArrayList中允許存放重複的元素。
2. public boolean
3. // 由于ArrayList中允許存放null，是以下面通過兩種情況來分别處理。
4. if (o == null) {  
5. for (int index = 0; index < size; index++)  
6. if (elementData[index] == null) {  
7. // 類似remove(int index)，移除清單中指定位置上的元素。
8.                 fastRemove(index);  
9. return true;  
10.             }  
11. } else
12. for (int index = 0; index < size; index++)  
13. if
14.             fastRemove(index);  
15. return true;  
16.         }  
17.     }  
18. return false;  
19. }      

    注意：從數組中移除元素的操作，也會導緻被移除的元素以後的所有元素的向左移動一個位置。

   6) 調整數組容量： 

   從上面介紹的向ArrayList中存儲元素的代碼中，我們看到，每當向數組中添加元素時，都要去檢查添加後元素的個數是否會超出目前數組的長度，如果超出，數組将會進行擴容，以滿足添加資料的需求。數組擴容通過一個公開的方法ensureCapacity(int minCapacity)來實作。在實際添加大量元素前，我也可以使用ensureCapacity來手動增加ArrayList執行個體的容量，以減少遞增式再配置設定的數量。

1. public void ensureCapacity(int
2.     modCount++;  
3. int
4. if
5.         Object oldData[] = elementData;  
6. int newCapacity = (oldCapacity * 3)/2 + 1;  
7. if
8.                 newCapacity = minCapacity;  
9. // minCapacity is usually close to size, so this is a win:
10.       elementData = Arrays.copyOf(elementData, newCapacity);  
11.     }  
12. }      

   從上述代碼中可以看出，數組進行擴容時，會将老數組中的元素重新拷貝一份到新的數組中，每次數組容量的增長大約是其原容量的1.5倍。這種操作的代價是很高的，是以在實際使用時，我們應該盡量避免數組容量的擴張。當我們可預知要儲存的元素的多少時，要在構造ArrayList執行個體時，就指定其容量，以避免數組擴容的發生。或者根據實際需求，通過調用ensureCapacity方法來手動增加ArrayList執行個體的容量。

   ArrayList還給我們提供了将底層數組的容量調整為目前清單儲存的實際元素的大小的功能。它可以通過trimToSize方法來實作。代碼如下：

1. public void
2.     modCount++;  
3. int
4. if
5.         elementData = Arrays.copyOf(elementData, size);  
6.     }  
7. }