ArrayList分析

2019-11-10 20:52:02

字體：大中小

供稿：網(wǎng)友

ArrayList應(yīng)該是最常用的容器吧，使用非常簡(jiǎn)單，那我就從源碼簡(jiǎn)單分析下。首先看看ArrayList的繼承體系：這里寫(xiě)圖片描述先說(shuō)說(shuō)其對(duì)這些接口的支持吧，

Serializable 一個(gè)標(biāo)記，表明實(shí)現(xiàn)此接口的類具有序列化的能力。Cloneable 一個(gè)標(biāo)記，表明實(shí)現(xiàn)此接口的類能夠調(diào)用 java.lang.Object.clone()方法，不然會(huì)拋出CloneNotSupportedException；對(duì)于Cloneable接口，需要注意一點(diǎn)，屬于淺度復(fù)制，使用時(shí)需要注意，對(duì)于引用類型的字段，只會(huì)復(fù)制引用。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

證明不同引用類型指向同一處內(nèi)存空間。我們來(lái)看下ArrayList對(duì)于clone的支持，先看源碼：

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

使用ArrayList的clone能夠獲得和當(dāng)前引用完全相同的數(shù)據(jù)。這種寫(xiě)法，對(duì)于我們有很重要的借鑒意義，通常實(shí)現(xiàn)Cloneable接口的類，最好的做法就是如同上面的代碼一樣，提供公有的非受檢clone方法。對(duì)于ArrayList本身的這個(gè)方法，估計(jì)會(huì)用的比較少，因?yàn)閷?shí)現(xiàn)與接口分離的思想，大多數(shù)人都會(huì)這么寫(xiě)：

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

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

Random access 這個(gè)估計(jì)一般都會(huì)被忽視，主要作用是表示實(shí)現(xiàn)此接口的類，應(yīng)用隨機(jī)訪問(wèn)比使用迭代器會(huì)有更好的性能。下面段代碼來(lái)自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); } } }

一般情況對(duì)于ArrayList都應(yīng)該使用迭代器進(jìn)行遍歷，不容易出錯(cuò)，尤其應(yīng)該使用foreach語(yǔ)法。在性能和代碼清晰與簡(jiǎn)單上比較，不是特殊情況，都應(yīng)該偏向后者，畢竟簡(jiǎn)單清晰的東西會(huì)很容易理解，就算有問(wèn)題也容易優(yōu)化。寫(xiě)代碼也應(yīng)該是這種思路，清晰簡(jiǎn)單的實(shí)現(xiàn)最佳，如果難以看出代碼的意圖，那么就難以保護(hù)其中的設(shè)計(jì)，更難以維護(hù)。

閑扯到此為止，現(xiàn)在進(jìn)入主題。 ArrayList其實(shí)就是長(zhǎng)度可變的數(shù)組，數(shù)據(jù)長(zhǎng)度不是固定的嗎，如何進(jìn)行擴(kuò)容呢，沒(méi)辦法，只能重新new一個(gè)數(shù)組，然后把現(xiàn)有的東西復(fù)制進(jìn)去。這就是ArrayList實(shí)現(xiàn)的原理。從上面可以看出，性能的優(yōu)化點(diǎn)主要在減少數(shù)據(jù)復(fù)制或者不復(fù)制，怎么辦，初始化合理的數(shù)組長(zhǎng)度，會(huì)有助于性能優(yōu)化。

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

對(duì)于ArrayList討論最多的也就是并發(fā)環(huán)境下的異常：ConcurrentModificationException，那么什么情況下會(huì)拋出呢，看源碼：

@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時(shí)拋出異常，expectedModCount是在內(nèi)部類初始化的時(shí)候賦值外部類的modCount 。當(dāng)兩值不同時(shí)，肯定是有些操作改變了外部類的modCount ，那是哪些方法呢。分析源碼發(fā)現(xiàn)，只要是引起底層數(shù)組長(zhǎng)度變化的方法，都會(huì)改變modCount,都有可能拋出異常，為什么是有可能呢？因?yàn)闆](méi)有正確的同步，其他線程對(duì)modCount值的改變可能對(duì)執(zhí)行遍歷的線程不可見(jiàn)，這也是兼顧性能后做出的最大的努力，快速失?。╢ail-fast）。所以在并發(fā)的環(huán)境有寫(xiě)操作，ArrayList有很大的風(fēng)險(xiǎn)，會(huì)造成遍歷的失敗，對(duì)于并發(fā)使用，JUC中提供了CopyOnWriteArrayList，遍歷開(kāi)始指向原數(shù)組空間，寫(xiě)的時(shí)候復(fù)制原數(shù)組形成新數(shù)組，最后賦值給原數(shù)組引用，由于遍歷器是指向的原數(shù)組地址空間，寫(xiě)操作并不會(huì)對(duì)遍歷產(chǎn)生影響。但是具體如何使用，還得具體問(wèn)題具體分析，只有熟悉了各自的不足，才能正確的規(guī)避。

上一篇：SQLServer2012數(shù)據(jù)庫(kù)降級(jí)方法

下一篇：codeforces#395