ArrayList分析

2019-11-10 20:52:02

字體：大中小

來源：轉載

供稿：網友

ArrayList應該是最常用的容器吧，使用非常簡單，那我就從源碼簡單分析下。首先看看ArrayList的繼承體系：這里寫圖片描述先說說其對這些接口的支持吧，

Serializable 一個標記，表明實現此接口的類具有序列化的能力。Cloneable 一個標記，表明實現此接口的類能夠調用 java.lang.Object.clone()方法，不然會拋出CloneNotSupportedException；對于Cloneable接口，需要注意一點，屬于淺度復制，使用時需要注意，對于引用類型的字段，只會復制引用。public class T01 implements Cloneable{ int i = 3; Object o = 3; public static void main(String[] args) throws CloneNotSupportedException { T01 t = new T01(); T01 t1 = (T01)t.clone(); System.out.PRintln(t1.i == t.i); System.out.println(t1.o == t.o); }}

打?。?/p>truetrue

證明不同引用類型指向同一處內存空間。我們來看下ArrayList對于clone的支持，先看源碼：

public Object clone() { try { @SuppressWarnings("unchecked") ArrayList<E> v = (ArrayList<E>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); //集合的內容進行了深度拷貝 v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(); } }

使用ArrayList的clone能夠獲得和當前引用完全相同的數據。這種寫法，對于我們有很重要的借鑒意義，通常實現Cloneable接口的類，最好的做法就是如同上面的代碼一樣，提供公有的非受檢clone方法。對于ArrayList本身的這個方法，估計會用的比較少，因為實現與接口分離的思想，大多數人都會這么寫：

List<Integer> list = new ArrayList<Integer>()

而List接口是不提供克隆方法的。

Random access 這個估計一般都會被忽視，主要作用是表示實現此接口的類，應用隨機訪問比使用迭代器會有更好的性能。下面段代碼來自Collections public static <T> void fill(List<? super T> list, T obj) { int size = list.size(); if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i<size; i++) list.set(i, obj); } else { ListIterator<? super T> itr = list.listIterator(); for (int i=0; i<size; i++) { itr.next(); itr.set(obj); } } }

一般情況對于ArrayList都應該使用迭代器進行遍歷，不容易出錯，尤其應該使用foreach語法。在性能和代碼清晰與簡單上比較，不是特殊情況，都應該偏向后者，畢竟簡單清晰的東西會很容易理解，就算有問題也容易優化。寫代碼也應該是這種思路，清晰簡單的實現最佳，如果難以看出代碼的意圖，那么就難以保護其中的設計，更難以維護。

閑扯到此為止，現在進入主題。 ArrayList其實就是長度可變的數組，數據長度不是固定的嗎，如何進行擴容呢，沒辦法，只能重新new一個數組，然后把現有的東西復制進去。這就是ArrayList實現的原理。從上面可以看出，性能的優化點主要在減少數據復制或者不復制，怎么辦，初始化合理的數組長度，會有助于性能優化。

public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; }

對于ArrayList討論最多的也就是并發環境下的異常：ConcurrentModificationException，那么什么情況下會拋出呢，看源碼：

@SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new **ConcurrentModificationException**(); cursor = i + 1; return (E) elementData[lastRet = i]; }final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

這是遍歷器的部分源碼，大致可以看出modCount != expectedModCount時拋出異常，expectedModCount是在內部類初始化的時候賦值外部類的modCount 。當兩值不同時，肯定是有些操作改變了外部類的modCount ，那是哪些方法呢。分析源碼發現，只要是引起底層數組長度變化的方法，都會改變modCount,都有可能拋出異常，為什么是有可能呢？因為沒有正確的同步，其他線程對modCount值的改變可能對執行遍歷的線程不可見，這也是兼顧性能后做出的最大的努力，快速失敗（fail-fast）。所以在并發的環境有寫操作，ArrayList有很大的風險，會造成遍歷的失敗，對于并發使用，JUC中提供了CopyOnWriteArrayList，遍歷開始指向原數組空間，寫的時候復制原數組形成新數組，最后賦值給原數組引用，由于遍歷器是指向的原數組地址空間，寫操作并不會對遍歷產生影響。但是具體如何使用，還得具體問題具體分析，只有熟悉了各自的不足，才能正確的規避。

上一篇：SQLServer2012數據庫降級方法

下一篇：codeforces#395