ArrayList源碼分析
?
?? ArrayList是以數組為基礎實現的一個動態數組容器,通過以下的代碼分析可知,一方面在ArrayList中添加或者刪除元素(除了在數組容器末尾添加或者刪除元素),是需要移動大量元素的借助System.arraycopy()來實現拷貝移動,另一方面,由于數組實現基礎,可依靠數組下標,可以實現隨機訪問,當然查找具體的元素,還是需要循環去查找的,再者ArrayList不是thread-safe的,在代碼中無論是add,remove,get,都沒有任何同步措施,在多線程環境下需要自己確保thread-safe。由此可知ArrayList適用于在任意位置添加,刪除元素不多,要求隨機訪問的應用場景。
?
? 代碼分析主要羅列:ArrayList構造函數,remove(), add(), get()
?
1.ArrayList構造函數
?
?? private transient E[] elementData;ArrayList使用對象數組元素來作為內部實現的基礎數據結構。
?
- //ArrayList是以數組為基礎實現的,采用的泛型編程,數組元素都是Object類型 ??
- //初始化時主要是構造指定大小的數組,用于存儲對象元素 ??
- public ?ArrayList( int ?initialCapacity){??
- ?????? super ();??
- ?????? if ?(initialCapacity?<? 0 )??
- ?????????? throw ? new ?IllegalArgumentException( "Illegal?Capacity:?" +??
- ?????????????????????????????????????????????initialCapacity);??
- ?????? this .elementData?=?(E[]) new ?Object[initialCapacity];??
- }??
- //ArrayList是以數組為基礎實現的,采用的泛型編程,數組元素都是Object類型 ??
- //初始化時主要是構造指定大小的數組,用于存儲對象元素 ??
- public ?ArrayList( int ?initialCapacity){??
- ?????? super ();??
- ?????? if ?(initialCapacity?<? 0 )??
- ?????????? throw ? new ?IllegalArgumentException( "Illegal?Capacity:?" +??
- ?????????????????????????????????????????????initialCapacity);??
- ?????? this .elementData?=?(E[]) new ?Object[initialCapacity];??
- }??
?
- //默認情況下ArrayList實現依賴的數組長度為10 ??
- ??? public ?ArrayList()?{??
- ???????? this ( 10 );??
- ???}??
- //默認情況下ArrayList實現依賴的數組長度為10 ??
- ??? public ?ArrayList()?{??
- ???????? this ( 10 );??
- ???}??
??
?
?
- //使用另一個集合中的元素來初始化當前的List ??
- ? public ?ArrayList(Collection<?? extends ?E>?c)?{??
- ??????size?=?c.size();??
- ?????? //?Allow?10%?room?for?growth ??
- ??????elementData?=?(E[]) new ?Object[??
- ????????????????????( int )Math.min((size*110L)/ 100 ,Integer.MAX_VALUE)];???
- ??????c.toArray(elementData);??
- ??}??
- //使用另一個集合中的元素來初始化當前的List ??
- ? public ?ArrayList(Collection<?? extends ?E>?c)?{??
- ??????size?=?c.size();??
- ?????? //?Allow?10%?room?for?growth ??
- ??????elementData?=?(E[]) new ?Object[??
- ????????????????????( int )Math.min((size*110L)/ 100 ,Integer.MAX_VALUE)];???
- ??????c.toArray(elementData);??
- ??}??
2.
ensureCapaciyt(int) | add(E) | add(int, E)分析
?
?? ensureCapacity主要用來實現數組的動態擴容,每次擴容為原來大小的1.5倍,在add操作前調用,以確保數組容量夠用。
?
- public ? void ?ensureCapacity( int ?minCapacity)?{??
- ??
- ????modCount++;??
- ???? int ?oldCapacity?=?elementData.length;??
- ??????????
- ???????? //如果當前數組的實際容量(oldCapacity)比當前要求的容量要小(minCapacity) ??
- ???????? //就需要進行擴容,申請新的數組空間,大小為minCapacity,并將原來數組空間中的元素拷貝 ??
- ???????? //到新的數組空間當中。???????? ??
- ???? if ?(minCapacity?>?oldCapacity)?{??
- ????????Object?oldData[]?=?elementData;??
- ????????????
- ???????????? //擴容因子為:1.5倍左右,每次需要擴容時,會將空間擴展為原來的1.5倍大小 ??
- ???????? int ?newCapacity?=?(oldCapacity?*? 3 )/ 2 ?+? 1 ;??
- ??
- ???????????? if ?(newCapacity?<?minCapacity)??
- ????????newCapacity?=?minCapacity;??
- ??
- ????????elementData?=?(E[]) new ?Object[newCapacity];??
- ????????????????
- ???????????? //將數組元素轉移到新申請的數組空間當中 ??
- ????????System.arraycopy(oldData,? 0 ,?elementData,? 0 ,?size);??
- ????}??
- }??
- public ? void ?ensureCapacity( int ?minCapacity)?{??
- ??
- ????modCount++;??
- ???? int ?oldCapacity?=?elementData.length;??
- ??????????
- ???????? //如果當前數組的實際容量(oldCapacity)比當前要求的容量要小(minCapacity) ??
- ???????? //就需要進行擴容,申請新的數組空間,大小為minCapacity,并將原來數組空間中的元素拷貝 ??
- ???????? //到新的數組空間當中。???????? ??
- ???? if ?(minCapacity?>?oldCapacity)?{??
- ????????Object?oldData[]?=?elementData;??
- ????????????
- ???????????? //擴容因子為:1.5倍左右,每次需要擴容時,會將空間擴展為原來的1.5倍大小 ??
- ???????? int ?newCapacity?=?(oldCapacity?*? 3 )/ 2 ?+? 1 ;??
- ??
- ???????????? if ?(newCapacity?<?minCapacity)??
- ????????newCapacity?=?minCapacity;??
- ??
- ????????elementData?=?(E[]) new ?Object[newCapacity];??
- ????????????????
- ???????????? //將數組元素轉移到新申請的數組空間當中 ??
- ????????System.arraycopy(oldData,? 0 ,?elementData,? 0 ,?size);??
- ????}??
- }??
? add(E)操作是向集合ArrayList中存儲元素,在當前數組容器的尾部添加,不需要移動元素,返回true。
?
- public ? boolean ?add(E?o)?{??
- ???????? //調用ensureCapacity確保當前容量不小于(size?+?1),size為容器中當前存儲的實際元素個數. ??
- ????ensureCapacity(size?+? 1 );???
- ???????? //將對象引用o保存到數組容器中,并++size. ??
- ????elementData[size++]?=?o;??
- ???? return ? true ;??
- }??
- public ? boolean ?add(E?o)?{??
- ???????? //調用ensureCapacity確保當前容量不小于(size?+?1),size為容器中當前存儲的實際元素個數. ??
- ????ensureCapacity(size?+? 1 );???
- ???????? //將對象引用o保存到數組容器中,并++size. ??
- ????elementData[size++]?=?o;??
- ???? return ? true ;??
- }??
add(int , E)在ArrayList中的指定位置index,保存對象element.
?
- public ? void ?add( int ?index,?E?element)?{??
- ??
- ???????? //檢測指定位置的合法性 ??
- ???? if ?(index?>?size?||?index?<? 0 )??
- ???????? throw ? new ?IndexOutOfBoundsException(??
- ???????? "Index:?" +index+ ",?Size:?" +size);??
- ??
- ????ensureCapacity(size+ 1 );??
- ??????????
- ???????? //將數組容器elementData中從index位置開始的元素,依次往后移動一個位置 ??
- ???????? //也就是說經過arraycopy()后,index位置被空出來 ??
- ????System.arraycopy(elementData,?index,?elementData,?index?+? 1 ,??
- ?????????????size?-?index);??
- ??
- ???????? //將對象element存儲到數組容器的index位置上 ??
- ????elementData[index]?=?element;??
- ????size++;??
- }??
- public ? void ?add( int ?index,?E?element)?{??
- ??
- ???????? //檢測指定位置的合法性 ??
- ???? if ?(index?>?size?||?index?<? 0 )??
- ???????? throw ? new ?IndexOutOfBoundsException(??
- ???????? "Index:?" +index+ ",?Size:?" +size);??
- ??
- ????ensureCapacity(size+ 1 );??
- ??????????
- ???????? //將數組容器elementData中從index位置開始的元素,依次往后移動一個位置 ??
- ???????? //也就是說經過arraycopy()后,index位置被空出來 ??
- ????System.arraycopy(elementData,?index,?elementData,?index?+? 1 ,??
- ?????????????size?-?index);??
- ??
- ???????? //將對象element存儲到數組容器的index位置上 ??
- ????elementData[index]?=?element;??
- ????size++;??
- }??
3.
remove(int) | remove(Object) | fastRemove(int) | removeRange(int,int)分析
?
? remove(int)用于刪除ArrayList數組容器中指定位置int上的元素,并返回此元素.
?
- public ?E?remove( int ?index)?{??
- ??
- ????RangeCheck(index);??
- ??
- ????modCount++;??
- ??
- ????E?oldValue?=?elementData[index];??
- ???????? //numMoved需要移動的元素個數,也就是index后面的所有的元素個數 ??
- ???? int ?numMoved?=?size?-?index?-? 1 ;??
- ??
- ???????? //將index后面的所有元素全部往前依次移動一個位置 ??
- ???? if ?(numMoved?>? 0 )??
- ????????System.arraycopy(elementData,?index+ 1 ,?elementData,?index,??
- ?????????????????numMoved);??
- ??
- ???????? //經過arraycopy的移位,數組容器的最個位置被騰空, ??
- ???????? //但是仍然持有某個對象的引用,需要把這個多余的引用置為null. ??
- ????????elementData[--size]?=? null ;? //?Let?gc?do?its?work ??
- ??
- ???? return ?oldValue;??
- }??
- public ?E?remove( int ?index)?{??
- ??
- ????RangeCheck(index);??
- ??
- ????modCount++;??
- ??
- ????E?oldValue?=?elementData[index];??
- ???????? //numMoved需要移動的元素個數,也就是index后面的所有的元素個數 ??
- ???? int ?numMoved?=?size?-?index?-? 1 ;??
- ??
- ???????? //將index后面的所有元素全部往前依次移動一個位置 ??
- ???? if ?(numMoved?>? 0 )??
- ????????System.arraycopy(elementData,?index+ 1 ,?elementData,?index,??
- ?????????????????numMoved);??
- ??
- ???????? //經過arraycopy的移位,數組容器的最個位置被騰空, ??
- ???????? //但是仍然持有某個對象的引用,需要把這個多余的引用置為null. ??
- ????????elementData[--size]?=? null ;? //?Let?gc?do?its?work ??
- ??
- ???? return ?oldValue;??
- }??
remove(Object)刪除指定的對象Object,在數組容器中,需要特別處理null對象,過程都是,首先在數組容器中循環查找某個對象,如果查找到則調用fastRemove()進行刪除。
?
- public ? boolean ?remove(Object?o)?{??
- ???? if ?(o?==? null )?{??
- ???????????? for ?( int ?index?=? 0 ;?index?<?size;?index++)??
- ???????? if ?(elementData[index]?==? null )?{??
- ????????????fastRemove(index);??
- ???????????? return ? true ;??
- ????????}??
- ????}? else ?{??
- ???????????? //注意比較兩個對象是否相等調用的是equals(), ??
- ???????????? //如果此類對象沒有重寫equals() ??
- ???????????? //比較的是是否引用同一個對象,如果有重寫,將比較對象內部狀態. ??
- ???????? for ?( int ?index?=? 0 ;?index?<?size;?index++)??
- ???????? if ?(o.equals(elementData[index]))?{??
- ????????????fastRemove(index);??
- ???????????? return ? true ;??
- ????????}??
- ????????}??
- ???? return ? false ;??
- ????}??
- public ? boolean ?remove(Object?o)?{??
- ???? if ?(o?==? null )?{??
- ???????????? for ?( int ?index?=? 0 ;?index?<?size;?index++)??
- ???????? if ?(elementData[index]?==? null )?{??
- ????????????fastRemove(index);??
- ???????????? return ? true ;??
- ????????}??
- ????}? else ?{??
- ???????????? //注意比較兩個對象是否相等調用的是equals(), ??
- ???????????? //如果此類對象沒有重寫equals() ??
- ???????????? //比較的是是否引用同一個對象,如果有重寫,將比較對象內部狀態. ??
- ???????? for ?( int ?index?=? 0 ;?index?<?size;?index++)??
- ???????? if ?(o.equals(elementData[index]))?{??
- ????????????fastRemove(index);??
- ???????????? return ? true ;??
- ????????}??
- ????????}??
- ???? return ? false ;??
- ????}??
fastRemove(int index)是相對于remove(int index)來說的,因為不需要進行index合法性檢查和返回被刪除的元素,所以它可以稱為fast remove.fastRemove是private不能被外界訪問,只是在remove(Object o)中被調用,因為remove(Object o)在調用fastRemove()時候已經確定了此對象的確存在才進行fastRemove(),所以是安全的,不需要檢查。
?
- 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 ;? //?Let?gc?do?its?work ??
- ?}??
- 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 ;? //?Let?gc?do?its?work ??
- ?}??
removeRange(int, int)用于刪除數組容器中指定下標范圍內的元素
?
- ??? protected ? void ?removeRange( int ?fromIndex,? int ?toIndex)?{??
- modCount++;??
- int ?numMoved?=?size?-?toIndex;??
- ??????? //將從toIndex開始的元素依次拷貝到fromIndex位置上。 ??
- ???????System.arraycopy(elementData,?toIndex,?elementData,?fromIndex,??
- ????????????????????????numMoved);??
- ??
- //?Let?gc?do?its?work ??
- ??????? //newSize為刪除指定范圍元素后,容器中所剩下的元素個數。 ??
- int ?newSize?=?size?-?(toIndex-fromIndex);??
- ??????? //將持有多余引用的元素位置(從size-1到newSize?-?1)置為null, ??
- ??????? //讓GC能夠及時回收垃圾對象. ??
- while ?(size?!=?newSize)??
- ????elementData[--size]?=? null ;??
- ???}??
- ??? protected ? void ?removeRange( int ?fromIndex,? int ?toIndex)?{??
- modCount++;??
- int ?numMoved?=?size?-?toIndex;??
- ??????? //將從toIndex開始的元素依次拷貝到fromIndex位置上。 ??
- ???????System.arraycopy(elementData,?toIndex,?elementData,?fromIndex,??
- ????????????????????????numMoved);??
- ??
- //?Let?gc?do?its?work ??
- ??????? //newSize為刪除指定范圍元素后,容器中所剩下的元素個數。 ??
- int ?newSize?=?size?-?(toIndex-fromIndex);??
- ??????? //將持有多余引用的元素位置(從size-1到newSize?-?1)置為null, ??
- ??????? //讓GC能夠及時回收垃圾對象. ??
- while ?(size?!=?newSize)??
- ????elementData[--size]?=? null ;??
- ???}??
4.
get(int)
?
get(int)用于獲取ArrayList指定位置的元素,就是從數組中指定位置上取元素。
?
- public ?E?get( int ?index)?{??
- ??
- ???????? //RangeCheck(index)用于檢查index在數組元素中位置是否合法(必須index?<?size) ??
- ????RangeCheck(index);??
- ??
- ???? return ?elementData[index];??
- }??
- public ?E?get( int ?index)?{??
- ??
- ???????? //RangeCheck(index)用于檢查index在數組元素中位置是否合法(必須index?<?size) ??
- ????RangeCheck(index);??
- ??
- ???? return ?elementData[index];??
- }??
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
