當前位置:編程學習大全網 - 源碼下載 - ArrayList詳解,自動擴容原理

ArrayList詳解,自動擴容原理

ArrayList<E>:說明ArrayList支持泛型。

extends AbstractList<E> :繼承了AbstractList。AbstractList提供List接口的骨幹實現,以最大限度地減少“隨機訪問”數據存儲(如ArrayList)實現Llist所需的工作。

implements List<E>:實現了List。實現了所有可選列表操作。

implements RandomAccess:表明ArrayList支持快速(通常是固定時間)隨機訪問。此接口的主要目的是允許壹般的算法更改其行為,從而在將其應用到隨機或連續訪問列表時能提供良好的性能。

implements Cloneable:表明其可以調用clone()方法來返回實例的field-for-field拷貝。

implements java.io.Serializable:表明該類具有序列化功能。有序列化功能

下面來看壹些比較重要的參數:

ArrayList的實際大小(數組包含真正的元素個數)

執行完構造方法時還是壹個空數組,等到add方法執行的時候則會初始化容量為10;

自己穿入想要的容量參數,對容量進行判斷如果容量小於零,則會拋出異常,否則會創建壹個容量為initialCapacity的空ArrayList

構造壹個包含指定 collection 的元素的列表,這些元素是按照該 collection 的叠代器返回它們的順序排列的。

先來看其中的add()方法:

add方法首先會調用ensureCapacityInternal(size+1)方法,

ensureCapacityInternal(size+1)方法是用來進行容量檢查,決定擴容的想要的最小容量,舉個例子,第壹次擴容的時候,size默認為0則minCapacity(即想要的最小容量)為1,執行完Math.max語句minCapacity就變為10,這個時候也就是進行空構造第壹次add的情況,當ensureCapacityInternal(size+1)傳入的參數小於默認參數的時候,就把默認參數當做想要的最小容量,如果大於默認參數就把妳想要的參數當做想要的最小容量

這個方法是用來判斷是否擴容,如果妳想要的最小容量大於數組長度則會調用grow方法進行擴容

通過grow方法可以看到新容量為當前數組容量的1.5倍,然後進行判斷,如果理論擴容後新的容量小於小於妳想要的最小容量(但我覺得這種情況不太可能會出現,因為為了節省空間,假如當前容量為10,只會傳入11來和擴容後的進行比較因此我自己認為不會出現if為真的情況)真正的實現擴容其實是Arrays.copy方法,就是復制數組實現擴容,

但是如果出現了if為真的情況,從這個方法中可以看到數組的理論最大值為Integer的最大值減去8,但是如果妳想要的最小容量已經大於數組的理論最大值,則會進行大容量分配為Integer的最大值至此擴容結束,

下面粗略的談壹下快速失敗機制(因為對線程還沒有壹個好的認識)

fail-fast是怎麽產生的。步驟如下:

新建了壹個ArrayList,名稱為arrayList。

向arrayList中添加內容

新建壹個“線程a”,並在“線程a”中通過Iterator反復的讀取arrayList的值。

新建壹個“線程b”,在“線程b”中刪除arrayList中的壹個“節點A”。

這時,就會產生有趣的事件了。

在某壹時刻,“線程a”創建了arrayList的Iterator。此時“節點A”仍然存在於arrayList中,創建arrayList時,expectedModCount = modCount(假設它們此時的值為N)。

在“線程a”在遍歷arrayList過程中的某壹時刻,“線程b”執行了,並且“線程b”刪除了arrayList中的“節點A”。“線程b”執行remove()進行刪除操作時,在remove()中執行了“modCount++”,此時modCount變成了N+1!

“線程a”接著遍歷,當它執行到next()函數時,調用checkForComodification()比較“expectedModCount”和“modCount”的大小;而“expectedModCount=N”,“modCount=N+1”,這樣,便拋出ConcurrentModificationException異常,產生fail-fast事件。

至此,我們就完全了解了fail-fast是如何產生的!

即,當多個線程對同壹個集合進行操作的時候,某線程訪問集合的過程中,該集合的內容被其他線程所改變(即其它線程通過add、remove、clear等方法,改變了modCount的值);這時,就會拋出ConcurrentModificationException異常,產生fail-fast事件。

方法1

在單線程的遍歷過程中,如果要進行remove操作,可以調用叠代器的remove方法而不是集合類的remove方法。看看ArrayList中叠代器的remove方法的源碼:

可以看到,該remove方法並不會修改modCount的值,並且不會對後面的遍歷造成影響,因為該方法remove不能指定元素,只能remove當前遍歷過的那個元素,所以調用該方法並不會發生fail-fast現象。該方法有局限性。

例子:

方法2

使用java並發包(java.util.concurrent)中的類來代替ArrayList 和hashMap。

比如使用 CopyOnWriterArrayList代替ArrayList,CopyOnWriterArrayList在是使用上跟ArrayList幾乎壹樣,CopyOnWriter是寫時復制的容器(COW),在讀寫時是線程安全的。該容器在對add和remove等操作時,並不是在原數組上進行修改,而是將原數組拷貝壹份,在新數組上進行修改,待完成後,才將指向舊數組的引用指向新數組,所以對於CopyOnWriterArrayList在叠代過程並不會發生fail-fast現象。但 CopyOnWrite容器只能保證數據的最終壹致性,不能保證數據的實時壹致性。

對於HashMap,可以使用ConcurrentHashMap,ConcurrentHashMap采用了鎖機制,是線程安全的。在叠代方面,ConcurrentHashMap使用了壹種不同的叠代方式。在這種叠代方式中,當iterator被創建後集合再發生改變就不再是拋出ConcurrentModificationException,取而代之的是在改變時new新的數據從而不影響原有的數據 ,iterator完成後再將頭指針替換為新的數據 ,這樣iterator線程可以使用原來老的數據,而寫線程也可以並發的完成改變。即叠代不會發生fail-fast,但不保證獲取的是最新的數據。

  • 上一篇:ibox首個3d藏品
  • 下一篇:大智慧增益源代碼
  • copyright 2024編程學習大全網