ArrayList是開發中非常常用的資料儲存容器之一，其底層是
陣列
實現的，我們可以在集合中儲存任意型別的資料，
ArrayList是執行緒不安全的，擅長隨機訪問元素，插入和刪除較慢
。
1、ArrayList的資料結構
ArrayList的底層資料結構就是一個
陣列
，陣列元素的型別為Object型別，對ArrayList的所有操作底層都是基於陣列的。
2、ArrayList是執行緒不安全的
對ArrayList進行新增元素的操作的時候是分兩個步驟進行的：
先在
object［size］
的位置上存放需要新增的元素；
將
size
的值增加1。
由於這個過程在多執行緒的環境下是不能保證具有原子性 的，因此ArrayList在多執行緒的環境下是執行緒不安全的。
在單執行緒情況下，如果Size = 0，新增一個元素後，此元素在位置 0，而且Size=1；而如果是在多執行緒情況下，比如有兩個執行緒，執行緒 A 先將元素存放在位置0。但是此時 CPU 排程執行緒A暫停，執行緒 B 得到執行的機會。執行緒B也向此ArrayList 新增元素，因為此時 Size 仍然等於 0。
（
注意
：我們假設的是新增一個元素是要兩個步驟哦，而執行緒A僅僅完成了步驟1），所以執行緒B也將 元素存放在位置0。然後執行緒A和執行緒B都繼續執行，都增 加 Size 的值。 那好，現在我們來看看ArrayList 的情況，元素實際上只有一個，存放在位置 0，而Size卻等於 2。這就是“執行緒不安全”了。
如果非要在多執行緒的環境下使用ArrayList，就需要保證它的執行緒安全性，通常有兩種解決辦法：
使用synchronized關鍵字；
可以用Collections類中的靜態方法synchronizedList（），對ArrayList進行呼叫即可。
3、ArrayList的實現
對於ArrayList而言，它實現List介面、底層使用陣列儲存所有元素。其操作基本上是對陣列的操作。下面我們來分析ArrayList的原始碼：
1） 私有屬性：
ArrayList定義只定義類兩個私有屬性：
/** *ArrayList 的元素儲存在其中的陣列緩衝區。 *ArrayList 的容量就是這個陣列緩衝區的長度。新增第一個元素時，任何帶有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都將擴充套件為 DEFAULT_CAPACITY（10）。 */ transient Object［］ elementData； // ArrayList 的大小 private int size；
Java的serialization提供了一種持久化物件例項的機制。當持久化物件時，可能有一個特殊的物件資料成員，我們不想用serialization機制來儲存它。為了在一個特定物件的一個域上關閉serialization，可以在這個域前加上關鍵字transient。
有點抽象，看個例子應該能明白：
public class UserInfo implements Serializable { private static final long serialVersionUID = 996890129747019948L； private String name； private transient String psw； public UserInfo（String name， String psw） { this。name = name； this。psw = psw； } public String toString（） { return “name=” + name + “， psw=” + psw； } } public class TestTransient { public static void main（String［］ args） { UserInfo userInfo = new UserInfo（“張三”， “123456”）； System。out。println（userInfo）； try { // 序列化，被設定為transient的屬性沒有被序列化 ObjectOutputStream o = new ObjectOutputStream（new FileOutputStream（“UserInfo。out”））； o。writeObject（userInfo）； o。close（）； } catch （Exception e） { e。printStackTrace（）； } try { // 重新讀取內容 ObjectInputStream in = new ObjectInputStream（new FileInputStream（“UserInfo。out”））； UserInfo readUserInfo = （UserInfo） in。readObject（）； // 讀取後psw的內容為null System。out。println（readUserInfo。toString（））； } catch （Exception e） { e。printStackTrace（）； } } }
被標記為transient的屬性在物件被序列化的時候不會被儲存。回到ArrayList的分析中
2） 構造方法：
ArrayList提供了三種方式的構造器，可以構造一個預設初始容量為10的空列表、構造一個指定初始容量的空列表以及構造一個包含指定collection的元素的列表，這些元素按照該collection的迭代器返回它們的順序排列的。
/** * 構造一個具有指定初始容量的空列表。 */ 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）； } } /** * 構造一個預設初始容量為10的空列表 */ public ArrayList（） { this。elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA； } /** * 構造一個包含指定集合元素的列表，按照集合的迭代器返回的順序。 */ public ArrayList（Collection<？ extends E> c） { Object［］ a = c。toArray（）； if （（size = a。length） ！= 0） { if （c。getClass（） == ArrayList。class） { elementData = a； } else { elementData = Arrays。copyOf（a， size， Object［］。class）； } } else { // 替換為空陣列。 elementData = EMPTY_ELEMENTDATA； } }
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； } // 將指定的元素新增到此列表的尾部。 public boolean add（E e） { // 增加modCount ensureCapacity（size + 1）； elementData［size++］ = e； return true； } // 將指定的元素插入此列表中的指定位置。 // 如果當前位置有元素，則向右移動位於該位置的元素及所有後續元素（其索引加1）。 public void add（int index， E element） { // if （index > size || index < 0） // throw new IndexOutOfBoundsException（“Index： ” + index + “， Size： ” + size）； rangeCheckForAdd（index）； // 如果陣列長度不足，將進行擴容。 ensureCapacity（size + 1）； // 增加modCount // 將 elementData中從Index位置開始、長度為size-index的元素， // 複製到從下標為index+1位置開始的新的elementData陣列中。 // 即將當前位於該位置的元素以及所有後續元素右移一個位置。 System。arraycopy（elementData， index， elementData， index + 1， size - index）； elementData［index］ = element； size++； } // 按照指定collection的迭代器所返回的元素順序，將該collection中的所有元素新增到此列表的尾部。 public boolean addAll（Collection<？ extends E> c） { Object［］ a = c。toArray（）； int numNew = a。length； ensureCapacity（size + numNew）； // Increments modCount System。arraycopy（a， 0， elementData， size， numNew）； size += numNew； return numNew ！= 0； } // 從指定的位置開始，將指定collection中的所有元素插入到此列表中。 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）； // 增加modCount int 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； }
ArrayList是基於陣列實現的，屬性中也看到了陣列，具體是怎麼實現的呢？比如就這個新增元素的方法，如果陣列大，則在將某個位置的值設定為指定元素即可，如果陣列容量不夠了呢？
看到add（E e）中先呼叫了ensureCapacity（size+1）方法，之後將元素的索引賦給elementData［size］， 而後size自增。例如初次新增時，size為0，add將elementData［0］賦值為e，然後size設定為1（類似執行以下兩條語句elementData［0］=e；size=1）。將元素的索引賦給elementData［size］不是會出現陣列越界的情況嗎？這裡關鍵就在ensureCapacity（size+1）中了。
4） 元素讀取：
// 返回此列表中指定位置的元素。 public E get（int index） { rangeCheck（index）； return elementData（index）； }
5） 元素刪除：
ArrayList提供了根據下標或者指定物件兩種方式的刪除功能。如下：
// 刪除此列表中指定位置的元素。將任何後續元素向左移動（從它們的索引中減去一個）。 public E remove（int index） { rangeCheck（index）； modCount++； E oldValue = elementData（index）； 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 return oldValue； }
首先是檢查範圍，修改modCount，保留將要被移除的元素，將移除位置之後的元素向前挪動一個位置，將list末尾元素置空（null），返回被移除的元素。
// 從此列表中刪除第一次出現的指定元素（如果存在）。如果列表不包含該元素，則保持不變。 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； } // 私有刪除方法，跳過邊界檢查並且不返回刪除的值。 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； }
首先透過程式碼可以看到，當移除成功後返回true，否則返回 false。remove（Object o）中透過遍歷 element 尋找是否存在傳入物件，一旦找到就呼叫 fastRemove 移除物件。為什麼找到了元素就知道了index，不透過remove（index） 來移除元素呢？因為 fastRemove 跳過了判斷邊界的處理，找到元素就相當於確定了 index 不會超過邊界，而且 fastRemove 並不返回被移除的元素。
// 從此列表中刪除索引介於兩者之間的所有元素 protected void removeRange（int fromIndex， int toIndex） { modCount++； int numMoved = size - toIndex； System。arraycopy（elementData， toIndex， elementData， fromIndex， numMoved）； int newSize = size - （toIndex-fromIndex）； for （int i = newSize； i < size； i++） { elementData［i］ = null； } size = newSize； }
執行過程是將 elementData 從 toIndex 位置開始的元素向前移動到 fromIndex，然後將 toIndex 位置之後的元素全部置空順便修改size。
這個方法是protected，及受保護的方法，為什麼這個方法被定義為protected呢？ 先看下面這個例子
ArrayList
結果是不是像呼叫了 removeRange（int fromIndex，int toIndex）！
6） 調整陣列容量ensureCapacity：
從上面介紹的向ArrayList中儲存元素的程式碼中，我們看到，每當向陣列中新增元素時，都要去檢查新增後元素的個數是否會超出當前陣列的長度，如果超出，陣列將會進行擴容，以滿足新增資料的需求。 陣列擴容透過一個公開的方法
ensureCapacity（int minCapacity）
來實現。在實際新增大量元素前，我也可以使用ensureCapacity來手動增加ArrayList例項的容量，以減少遞增式再分配的數量。
public void ensureCapacity（int minCapacity） { modCount++； int oldCapacity = elementData。length； if （minCapacity > oldCapacity） { Object oldData［］ = elementData； int newCapacity = （oldCapacity * 3） / 2 + 1； // 增加50%+1 if （newCapacity < minCapacity） newCapacity = minCapacity； // 通常接近 size elementData = Arrays。copyOf（elementData， newCapacity）； } }
從上述程式碼中可以看出，陣列進行擴容時，會將老陣列中的元素重新複製一份到新的陣列中，每次陣列 容量的增長大約是其原容量的1。5倍。這種操作的代價是很高的，因此在實際使用時，我們應該儘量避 免陣列容量的擴張。當我們可預知要儲存的元素的多少時，要在構造ArrayList例項時，就指定其容量， 以避免陣列擴容的發生。或者根據實際需求，透過呼叫ensureCapacity方法來手動增加ArrayList例項的容量。
// 為什麼要用到oldData［］ Object oldData［］ = elementData；
乍一看來後面並沒有用到關於oldData， 這句話顯得多此一舉！但是這是一個牽涉到記憶體管理的類， 所以要 瞭解內部的問題 。 而且為什麼這一句還在if的內部，這跟
elementData = Arrays。copyOf（elementData， newCapacity）；
這句是有關係的，下面這句Arrays。copyOf的實現時新建立了newCapacity大小的記憶體，然後把老的elementData放入。好像也沒有用到oldData，有什麼問題 呢。問題就在於舊的記憶體的引用是elementData， elementData指向了新的記憶體塊，如果有一個區域性變數oldData變數引用舊的記憶體塊的話，在copy的過程中就會比較安全，因為這樣證明這塊老的記憶體依 然有引用，分配記憶體的時候就不會被侵佔掉，然後copy完成後這個區域性變數的生命期也過去了，然後釋放才是安全的。不然在copy的的時候萬一新的記憶體或其他執行緒的分配記憶體侵佔了這塊老的記憶體，而 copy 還沒有結束，這將是個嚴重的事情。
ArrayList還給我們提供了將底層陣列的容量調整為當前列表儲存的實際元素的大小的功能。它可以透過trimToSize方法來實現。程式碼如下：
// 將此ArrayList例項的容量修剪為列表的當前大小。可以使用此操作來最小化ArrayList例項的儲存空間。 public void trimToSize（） { modCount++； if （size < elementData。length） { elementData = （size == 0） ？ EMPTY_ELEMENTDATA ： Arrays。copyOf（elementData， size）； } }
由於elementData的長度會被拓展，size標記的是其中包含的元素的個數。所以會出現size很小但elementData。length很大的情況，將出現空間的浪費。trimToSize將返回一個新的陣列給elementData，元素內容保持不變，length和size相同，節省空間。
7） 轉為靜態陣列toArray
4、注意ArrayList的兩個轉化為靜態陣列的toArray方法。
第一個，呼叫Arrays。copyOf將返回一個數組，陣列內容是size個elementData的元素，即複製
elementData從0至size-1位置的元素到新陣列並返回。
// 返回一個數組，該陣列以適當的順序包含此列表中的所有元素。 public Object［］ toArray（） { return Arrays。copyOf（elementData， size）； }
第二個，如果傳入陣列的長度小於size，返回一個新的陣列，大小為size，型別與傳入陣列相同。所傳入陣列長度與size相等，則將elementData複製到傳入陣列中並返回傳入的陣列。若傳入陣列長度大於size，除了複製elementData外，還將把返回陣列的第size個元素置為空。
/* 以適當的順序返回一個包含此列表中所有元素的陣列； 返回陣列的執行時型別是指定陣列的型別。 如果列表適合指定的陣列，則在其中返回。 否則將使用指定陣列的執行時型別和此列表的大小分配一個新陣列。*/ public
Fail-Fast機制：
ArrayList也採用了快速失敗的機制，透過記錄modCount引數來實現。在面對併發的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發生任意不確定行為的風險
4、總結
關於ArrayList的原始碼，給出幾點比較重要的總結：
1、注意其三個不同的構造方法。無參構造方法構造的ArrayList的容量預設為10，帶有Collection引數的構造方法，將Collection轉化為陣列賦給ArrayList的實現陣列elementData。
2、注意擴充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個，也可能是一組） 時，都要呼叫該方法來確保足夠的容量。當容量不足以容納當前的元素個數時，就設定新的容量為舊的 容量的1。5倍加1，如果設定後的新容量還不夠，則直接新容量設定為傳入的引數（也就是所需的容量），而後用Arrays。copyof（）方法將元素複製到新的陣列。從中可以看出，當容量不夠時，每次增加元素，都要將原來的元素複製到一個新的陣列中，非常之耗時，也因此建議在事先 能確定元素數量的情況下，才使用ArrayList，否則建議使用LinkedList。
3、ArrayList的實現中大量地呼叫了
Arrays。copyOf（）
和
System。arrayCopy（）
方法。我們有必要對這兩個方法的實現做下深入的瞭解。先看Arrays。copyof（）方法，它有很多個過載的方法，但實現思路都是一樣的，看看泛型版本的原始碼：
// 複製指定的陣列，用空值截斷或填充（如有必要），使副本具有指定的長度。對於在原始陣列和副本中都有效的所有索引，這兩個陣列將包含相同的值。對於副本中有效但不是原始索引的任何索引，副本將包含null。// 當且僅當指定的長度大於原始陣列的長度時，此類索引才會存在。// 生成的陣列與原始陣列的類完全相同。 public static
很明顯呼叫了另一個copyOf方法，該方法有三個引數，最後一個引數指明要轉換的資料的型別，其原始碼 如下：
// newType類public static
這裡可以很明顯地看出，該方法實際上是在其內部又建立了一個長度為newlength的陣列，呼叫System。arrayCopy（）方法，將原來陣列中的元素複製到了新的陣列中。下面來看System。arrayCopy（）方法。該方法被標記了native，呼叫了系統的C/C++程式碼，在JDK中是看不到的，但在openJDK中可以看到其原始碼。該函式實際上最終呼叫了C語言的memmove（）函式，因此它可以保證同一個陣列內元素的正確複製和移動，比一般的複製方法的實現效率要高很多，很適合用來批次處理陣列。Java強烈推薦在複製大量陣列元素時用該方法，以取得更高的效率。
4、ArrayList基於陣列實現，可以透過下標索引直接查詢到指定位置的元素，因此查詢效率高，但每次插入或刪除元素，就要大量地移動元素，插入刪除元素的效率低。
5、在查詢給定元素索引值等的方法中，原始碼都將該元素的值分為null和不為null兩種情況處理， ArrayList中允許元素為null。
