摘要:表明該類具有序列化功能。關鍵屬性默認初始容量大小指定該容量為時,返回該空數組。構造一個包含指定的元素的列表,這些元素是按照該的迭代器返回它們的順序排列的。對擴容后的容量進行判斷,如果大于允許的最大容量,則將容量再次調整為。
總覽
底層:ArrayList底層是一個數組,可以擴容,正因為它擴容,所以它能夠實現“動態”增長
允許null元素
時間復雜度:size、isEmpty、get、set、iterator和listIterator方法都以固定時間運行,時間復雜度為O(1)。add和remove方法需要O(n)時間。與用于LinkedList實現的常數因子相比,此實現的常數因子較低。
容量:ArrayList的容量可以自動增長。
是否同步:ArrayList不同步的。
迭代器:ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的。
定義public class ArrayListextends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
ArrayList
extends AbstractList
implements
List
RandomAccess:RandomAccess 是一個標志接口,表明實現這個這個接口的 List 集合是支持快速隨機訪問的。在 ArrayList 中,我們即可以通過元素的序號快速獲取元素對象,這就是快速隨機訪問。
Cloneable:表明其可以調用clone()方法來返回實例的field-for-field拷貝。
java.io.Serializable:表明該類具有序列化功能。
關鍵屬性/** * 默認初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 指定該ArrayList容量為0時,返回該空數組。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 當調用無參構造方法,返回的是該數組。剛創建一個ArrayList 時,其內數據量為0。 * 它與EMPTY_ELEMENTDATA的區別就是:該數組是默認返回的,而后者是在用戶指定容量為0時返回。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 保存ArrayList數據的數組 * 該值為DEFAULTCAPACITY_EMPTY_ELEMENTDATA 時,當第一次添加元素進入ArrayList中時,數組將擴容值DEFAULT_CAPACITY。 */ transient Object[] elementData; /** * ArrayList 所包含的元素個數 */ private int size;
問:elementData被標記為transient,那么它的序列化和反序列化是如何實現的呢?
答:ArrayList自定義了它的序列化和反序列化方式。詳情請查看writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。
ArrayList提供了三種構造方法。
ArrayList(int initialCapacity):構造一個指定容量為capacity的空ArrayList。
ArrayList():構造一個初始容量為 10 的空列表。
ArrayList(Collection extends E> c):構造一個包含指定 collection 的元素的列表,這些元素是按照該 collection 的迭代器返回它們的順序排列的。
/** * 帶初始容量參數的構造函數。(用戶自己指定容量) */ public ArrayList(int initialCapacity) { //初始容量大于0 if (initialCapacity > 0) { //創建initialCapacity大小的數組 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //創建空數組 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 默認構造函數,DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為0.初始化為10, * 也就是說初始其實是空數組 當添加第一個元素的時候數組容量才變成10 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 構造一個包含指定集合的元素的列表,按照它們由集合的迭代器返回的順序。 * 如果指定的集合為null,throws NullPointerException。 */ public ArrayList(Collection extends E> c) { elementData = c.toArray(); //如果指定集合元素個數不為0 if ((size = elementData.length) != 0) { // c.toArray 可能返回的不是Object類型的數組所以加上下面的語句用于判斷, if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); //【2】Arrays包含用來操作數組(比如排序和搜索)的各種方法。 //copyOf(U[] original, int newLength, Class extends T[]> newType) // 復制指定的數組,截取或用 null 填充(如有必要),以使副本具有指定的長度。 } else { this.elementData = EMPTY_ELEMENTDATA; } }核心方法 get(int index)
步驟:
檢查角標
返回元素
/** * 返回此列表中指定位置的元素。 * * @param index 需要返回的元素的索引 * @return list中索引為index的元素 * @throws IndexOutOfBoundsException 如果索引超出size */ public E get(int index) { //越界檢查 rangeCheck(index); return elementData(index); } /** * 檢查給定的索引是否在范圍內。 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 返回IndexOutOfBoundsException細節信息 */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } /** * 返回索引為index的元素 */ @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }add(E e)
步驟:
檢查是否需要擴容
插入元素
整個擴容過程:
首先去檢查一下數組的容量是否足夠
足夠:直接添加
不足夠:擴容
擴容到原來的1.5倍
第一次擴容后,如果容量還是小于minCapacity,就將容量擴充為minCapacity。
/** * 將指定的元素追加到此列表的末尾。 */ public boolean add(E e) { //確認list容量,如果不夠,容量加1。注意:只加1,保證資源不被浪費 ensureCapacityInternal(size + 1); //這里看到ArrayList添加元素的實質就相當于為數組賦值 elementData[size++] = e; return true; }
擴容
/** * ArrayList的擴容機制 * ArrayList的擴容機制提高了性能,如果每次只擴充一個, * 那么頻繁的插入會導致頻繁的拷貝,降低性能,而ArrayList的擴容機制避免了這種情況。 * 如有必要,增加此ArrayList實例的容量,以確保它至少能容納元素的數量 * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { // 如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA,最小擴容量為DEFAULT_CAPACITY,否則為0 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } /** * 數組容量檢查,不夠時則進行擴容。 * * @param minCapacity 想要的最小容量 */ private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA, // 則取minCapacity為DEFAULT_CAPACITY和參數minCapacity之間的最大值 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } //得到最小擴容量 private void ensureCapacityInternal(int minCapacity) { // 獲取默認的容量和傳入參數的較大值 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //判斷是否需要擴容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 確保指定的最小容量 > 數組緩沖區當前的長度 if (minCapacity - elementData.length > 0) //擴容 grow(minCapacity); } /** * 要分配的最大數組大小 * 為什么要減去8呢? * 因為某些VM會在數組中保留一些頭字,嘗試分配這個最大存儲容量,可能會導致array容量大于VM的limit,最終導致OutOfMemoryError。 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList擴容的核心方法 * * 第一次擴容,邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎上增加一半。 * 第一次擴容后,如果容量還是小于minCapacity,就將容量擴充為minCapacity。 */ private void grow(int minCapacity) { // oldCapacity為舊容量,newCapacity為新容量 int oldCapacity = elementData.length; //將oldCapacity 右移一位,其效果相當于oldCapacity /2, //我們知道位運算的速度遠遠快于整除運算,整句運算式的結果就是將新容量更新為舊容量的1.5倍, int newCapacity = oldCapacity + (oldCapacity >> 1); //然后檢查新容量是否大于最小需要容量,若還是小于最小需要容量,那么就把最小需要容量當作數組的新容量, if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //再檢查新容量是否超出了ArrayList所定義的最大容量, //若超出了,則調用hugeCapacity()來比較minCapacity和 MAX_ARRAY_SIZE, //如果minCapacity大于MAX_ARRAY_SIZE,則新容量則為Interger.MAX_VALUE,否則,新容量大小則為 MAX_ARRAY_SIZE。 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //比較minCapacity和 MAX_ARRAY_SIZE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
看完了代碼,可以對擴容方法總結如下:
進行空間檢查,決定是否進行擴容,以及確定最少需要的容量
如果確定擴容,就執行grow(int minCapacity),minCapacity為最少需要的容量
第一次擴容,邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎上增加一半。
第一次擴容后,如果容量還是小于minCapacity,就將容量擴充為minCapacity。
對擴容后的容量進行判斷,如果大于允許的最大容量MAX_ARRAY_SIZE,則將容量再次調整為MAX_ARRAY_SIZE。至此擴容操作結束。
add(int index, E element)步驟:
越界檢查
空間檢查,如果有需要進行擴容
插入元素
/** * 在此列表中的指定位置插入指定的元素。 * 先調用 rangeCheckForAdd 對index進行界限檢查;然后調用 ensureCapacityInternal 方法保證capacity足夠大; * 再將從index開始之后的所有成員后移一個位置;將element插入index位置;最后size加1。 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); //arraycopy()這個實現數組之間復制的方法一定要看一下,下面就用到了arraycopy()方法實現數組自己復制自己 //實現讓index開始之后的所有元素后移一個位置: //elementData:源數組;index:源數組中的起始位置;elementData:目標數組;index + 1:目標數組中的起始位置; size - index:要復制的數組元素的數量; System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
add(int index, E e)需要先對元素進行移動,然后完成插入操作,也就意味著該方法有著線性的時間復雜度,即O(n)
remove(int index)步驟:
檢查角標
刪除元素
計算出需要移動的個數,將索引大于index的元素左移一位(左移后,該刪除的元素就被覆蓋了,相當于被刪除了)
設置為null(size-1處),讓Gc回收
/** * 刪除該列表中指定位置的元素。 將任何后續元素移動到左側(從其索引中減去一個元素)。 */ public E remove(int index) { //檢查索引是否越界 rangeCheck(index); //結構性修改次數+1【1】 modCount++; E oldValue = elementData(index); // 刪除指定元素后,需要左移的元素個數 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // size減一,然后將索引為size-1處的元素置為null。為了讓GC起作用,必須顯式的為最后一個位置賦null值 elementData[--size] = null; //從列表中刪除的元素 return oldValue; }
注意:為了讓GC起作用,必須顯式的為最后一個位置賦null值。上面代碼中如果不手動賦null值,除非對應的位置被其他元素覆蓋,否則原來的對象就一直不會被回收。
set( int index, E element)步驟:
檢查角標
替代元素
返回舊值
/** * 用指定的元素替換此列表中指定索引的元素。 */ public E set(int index, E element) { //對index進行界限檢查 rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; //返回原來在這個位置的元素 return oldValue; }
細節:
ArrayList是基于動態數組實現的,在增刪時候,需要數組的拷貝復制。
ArrayList的默認初始化容量是10,每次擴容時候增加原先容量的一半,也就是變為原來的1.5倍
刪除元素時不會減少容量,若希望減少容量則調用trimToSize()
它能存放null值。
和 Vector 不同,ArrayList 中的操作不是線程安全的!所以,建議在單線程中才使用 ArrayList,而在多線程中可以選擇 Vector 或者 CopyOnWriteArrayList。
移位運算符
簡介:移位運算符就是在二進制的基礎上對數字進行平移。按照平移的方向和填充數字的規則分為三種:<<(左移)、>>(帶符號右移)和>>>(無符號右移)。
作用:對于大數據的2進制運算,位移運算符比那些普通運算符的運算要快很多,因為程序僅僅移動一下而已,不去計算,這樣提高了效率,節省了資源
比如這里:int newCapacity = oldCapacity + (oldCapacity >> 1); 右移一位相當于除2,右移n位相當于除以 2 的 n 次方。這里 oldCapacity 明顯右移了1位所以相當于oldCapacity /2。
另外需要注意的是:
java 中的length 屬性是針對數組說的,比如說你聲明了一個數組,想知道這個數組的長度則用到了 length 這個屬性.
java 中的length()方法是針對字符串String說的,如果想看這個字符串的長度則用到 length()這個方法.
java 中的size()方法是針對泛型集合說的,如果想看這個泛型有多少個元素,就調用此方法來查看!
內部類:
(1)private class Itr implements Iterator(2)private class ListItr extends Itr implements ListIterator (3)private class SubList extends AbstractList implements RandomAccess (4)static final class ArrayListSpliterator implements Spliterator
Itr是實現了Iterator接口,同時重寫了里面的hasNext(),next(),remove()等方法;
ListItr繼承Itr,實現了ListIterator接口,同時重寫了hasPrevious(),nextIndex(),previousIndex(),previous(),set(E e),add(E e)等方法,
所以這也可以看出了 Iterator和ListIterator的區別:ListIterator在Iterator的基礎上增加了添加對象,修改對象,逆向遍歷等方法,這些是Iterator不能實現的。
參考資料:
https://blog.csdn.net/panweiw...
https://segmentfault.com/a/11...
https://github.com/Snailclimb...
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74475.html
摘要:需要注意的是,通過構造函數定義初始量是動態數組的實際大小。帶容量的構造函數新建一個容量為的數組默認構造函數,默認為空構造一個包含指定元素的第一個構造方法使用提供的來初始化數組的大小。 前言 今天介紹經常使用的一個Java集合類——ArrayList(基于JDK1.8.0_121)。ArrayList在工作和日常面試中經常被使用或者提到。總的來說,工作中使用ArrayList主要是因為動...
摘要:源碼和多線程安全問題分析在分析線程安全問題之前,我們線對此類的源碼進行分析,找出可能出現線程安全問題的地方,然后代碼進行驗證和分析。即當多線程調用方法的時候會出現元素覆蓋的問題。 1.ArrayList源碼和多線程安全問題分析 在分析ArrayList線程安全問題之前,我們線對此類的源碼進行分析,找出可能出現線程安全問題的地方,然后代碼進行驗證和分析。 1.1 數據結構 ArrayLi...
摘要:部分源碼分析小記底層數據結構底層的數據結構就是數組,數組元素類型為類型,即可以存放所有類型數據。初始容量大于初始化元素數組新建一個數組初始容量為為空對象數組初始容量小于,拋出異常無參構造函數。 JDK1.8 ArrayList部分源碼分析小記 底層數據結構 底層的數據結構就是數組,數組元素類型為Object類型,即可以存放所有類型數據。我們對ArrayList類的實例的所有的操作底層都...
摘要:源碼分析類的實現接口及繼承父類和和都實現了接口。這個接口的作用是實現它能夠支持快速隨機訪問。在取出值的時候利用范型轉為聲明的類型。如果等于則初始化為空如果小于則拋出異常。并且設置為傳入的大小。常用方法解析的元素數方法很簡單直接返回值的大小。 ArrayList源碼分析 類的實現接口及繼承父類 public class ArrayList extends AbstractList. i...
摘要:同步眾所周知,是同步的而不是,在一些必要的方法上都加了關鍵字,但是這也會加大系統開銷。中有一個方法用來返回一個,以匿名內部類的方式實現的接口和類似,都用作于對集合進行迭代,不過沒有刪除功能,已經被取代。還有是的,但不是,這一點很重要。 在上篇文章ArrayList源碼淺析中分析了一下 ArrayList的源碼和一些重要方法,現在對比 ArrayList,總結一下 Vector和 Arr...
閱讀 2538·2023-04-26 00:57
閱讀 911·2021-11-25 09:43
閱讀 2221·2021-11-11 16:55
閱讀 2207·2019-08-30 15:53
閱讀 3592·2019-08-30 15:52
閱讀 1459·2019-08-30 14:10
閱讀 3379·2019-08-30 13:22
閱讀 1209·2019-08-29 11:18