public?class?ArrayList?extends?AbstractList????????implements?List,?RandomAccess,?Cloneable,?java.io.Serializable

ArrayList 繼承于AbstractList，實現(xiàn)了List接口，其實AbstractList 已經(jīng)實現(xiàn)過List接口，這里重復實現(xiàn)使得接口功能更加清晰，JDK中很多類都是如此。

其中Cloneable接口是克隆標記接口，Serializable序列化標記接口，需要clone和序列化功能必須實現(xiàn)這兩個接口，而RandomAccess，單純是一個標志接口 ，該接口表示該類支持快速隨機訪問，且在循環(huán)遍歷時for循環(huán)的方式會優(yōu)于用迭代器。

1.成員變量

??//?默認初始容量???private?static?final?int?DEFAULT_CAPACITY?=?10;???//?空數(shù)組實例，初始容量為0或者傳入集合為空集合(不是null)時使用???private?static?final?Object[]?EMPTY_ELEMENTDATA?=?{};??????//?空數(shù)組示例，無參構造時使用???private?static?final?Object[]?DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};??????//?ArrayList內(nèi)部數(shù)據(jù)容器???transient?Object[]?elementData;?//?non-private?to?simplify?nested?class?access??????//?實際元素數(shù)量???private?int?size;

在ArrayList中，主要有五個成員變量。DEFAULT_CAPACITY表示初始容量大小，即在我們初始化ArrayList時不指定容量大小， 默認容量將會是10，Object[] elementData 則是ArrayList內(nèi)部實際存儲對象的容易，也就是我們常說的ArrayList是數(shù)組實現(xiàn)的。

在1.8中，空數(shù)組分為了兩類情況，EMPTY_ELEMENTDATA 與 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在標記空數(shù)組的時候區(qū)分了不同的情況。

2.構造方法

ArrayList有三個構造方法，指定容量的ArrayList(int initialCapacity) ，無參構造ArrayList() 以及傳入集合的ArrayList(Collection extends E> c)。

????public?ArrayList()?{????????this.elementData?=?DEFAULTCAPACITY_EMPTY_ELEMENTDATA;????}

最簡單的莫過于無參構造，直接賦值為空數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA。其實對于常說的默認容量10，是在第一次添加元素調(diào)用add()方法時處理的，并不是構造方法中。

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

對于傳入容量的構造方法，當傳入?yún)?shù) > 0時，直接初始化對應容量的數(shù)組，參數(shù)類型為int，也即ArrayList的最大初始容量不能超過Integer.MAX_VALUE，事實上ArrayList的最大容量也只能是Integer.MAX_VALUE。而初始容量傳入0，會賦值為空數(shù)組EMPTY_ELEMENTDATA。如果 < 0，這個顯然的不允許了，直接IllegalArgumentException

????public?ArrayList(Collection?extends?E>?c)?{????????elementData?=?c.toArray();????????if?((size?=?elementData.length)?!=?0)?{????????????//?c.toArray?might?(incorrectly)?not?return?Object[]?(see?6260652)????????????if?(elementData.getClass()?!=?Object[].class)????????????????elementData?=?Arrays.copyOf(elementData,?size,?Object[].class);????????}?else?{????????????//?replace?with?empty?array.????????????this.elementData?=?EMPTY_ELEMENTDATA;????????}????}

集合構造時，沒有進行null校驗，也就是說如果傳入null，直接就會NPE異常。集合構造的邏輯也很簡單，當傳入集合不為空時，調(diào)用Arrays.copyOf進行復制，并且容量 size為傳入大小，而傳入集合為空，則賦值為空數(shù)組EMPTY_ELEMENTDATA。

3.添加元素

ArrayList在添加元素時，都會進行容量確認，可能會涉及到擴容，數(shù)組復制，所以效率相對較低。同時在添加元素時，ArrayList并未對元素本身進行校驗，所以是允許集合中存在null的情況。

3.1.尾部添加元素

????public?boolean?add(E?e)?{????????//?確定容量????????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!????????//?設值????????elementData[size++]?=?e;????????return?true;????}

在add()方法中，最主要的是確定容量ensureCapacityInternal(int minCapacity)方法。

????private?void?ensureCapacityInternal(int?minCapacity)?{????????ensureExplicitCapacity(calculateCapacity(elementData,?minCapacity));????}

首先會調(diào)用calculateCapacity(Object[] elementData, int minCapacity) 計算容量然后再ensureExplicitCapacity(int minCapacity)

????private?static?int?calculateCapacity(Object[]?elementData,?int?minCapacity)?{????????if?(elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{????????????return?Math.max(DEFAULT_CAPACITY,?minCapacity);????????}????????return?minCapacity;????}

這里僅僅判斷了是否是空數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA(== 地址比較)，如果前面還有印象的話，這個只會在無參構造時，才會初始化為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，這時候會取DEFAULT_CAPACITY(10)與傳入minCapacity的較大值，常說的默認容量大小10也就是在這里誕生的。

而其他的情況，都直接但會minCapacity，也即 size + 1，如果首次添加，那就是1。

????private?void?ensureExplicitCapacity(int?minCapacity)?{????????modCount++;????????//?overflow-conscious?code????????if?(minCapacity?-?elementData.length?>?0)????????????grow(minCapacity);????}

modCount是一個操作計數(shù)器，add與remove都會 + 1。當我們需要在循環(huán)中刪除ArrayList元素時，需要使用迭代器Iterator的remove()方法，此時直接使用List的刪除有針對modCount的校驗，會拋出 ConcurrentModificationException異常。

如果minCapacity大于數(shù)組容量，則調(diào)用grow(int minCapacity)進行擴容。

????private?void?grow(int?minCapacity)?{????????//?overflow-conscious?code????????int?oldCapacity?=?elementData.length;????????//?新容量增長?0.5倍????????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);????????if?(newCapacity?-?minCapacity??0)?//?MAX_ARRAY_SIZE?=?Integer.MAX_VALUE?-?8????????????newCapacity?=?hugeCapacity(minCapacity);????????//?minCapacity?is?usually?close?to?size,?so?this?is?a?win:????????elementData?=?Arrays.copyOf(elementData,?newCapacity);????}

擴容時，新的容量為原容量 + 原容量的一半，也就是0.5倍增長。如果增長后的新容量比計算出來的容量minCapacity小，則賦值為minCapacity，如果大于MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)，則進入hugeCapacity(int minCapacity)方法。

????private?static?int?hugeCapacity(int?minCapacity)?{????????if?(minCapacity??MAX_ARRAY_SIZE)??????????????Integer.MAX_VALUE?:????????????MAX_ARRAY_SIZE;????}

這里可以看到，當minCapacity < 0 時，會產(chǎn)生OutOfMemoryError，這是一個Error子類，這是需要避免的。什么時候minCapacity會小于0呢，當ArrayList大小為Integer.MAX_VALUE后，還需要擴容，則會發(fā)生錯誤。

這個方法，我們可以看出，當ArrayList需要的容量首次大于MAX_ARRAY_SIZE時，會設置為MAX_ARRAY_SIZE，然后再次擴容時會變成Integer.MAX_VALUE，如果還不夠，那就會發(fā)生錯誤。

擴容的最后一步是調(diào)用Arrays.copyOf進行元素的復制，這個最終也是調(diào)用System.arraycopy進行操作的。同時size++，實際元素的數(shù)量也增加 1。

3.2.中間添加元素

????public?void?add(int?index,?E?element)?{????????rangeCheckForAdd(index);??//?確認容量大小????????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!????????System.arraycopy(elementData,?index,?elementData,?index?+?1,?size?-?index);????????elementData[index]?=?element;????????size++;????}

在中間添加元素的邏輯和尾部添加元素基本一樣。

????private?void?rangeCheckForAdd(int?index)?{????????if?(index?>?size?||?index?

添加元素前，首先要進行范圍檢查，添加的范圍只能在[0，size]之間，index == size時，其實就是尾部插入。然后確認容量新的容量，這個方法尾部添加時已經(jīng)講過，接著數(shù)組復制，這步復制會跳過index位置的處理，最后再對index位置賦值，即完成了index位置的添加。

可以看到最后調(diào)用了size++，add(int index, E element)方法總是會添加元素，即使該index位置存在數(shù)據(jù)，只是會將原來的index位置數(shù)據(jù)往后擠動一位，并不會進行覆蓋。

img

3.3.批量添加

ArrayList除了add()與add(int index, E element)，還有兩個批量添加的方法。

????public?boolean?addAll(Collection?extends?E>?c)?{????????Object[]?a?=?c.toArray();????????int?numNew?=?a.length;????????//?確認容量????????ensureCapacityInternal(size?+?numNew);??//?Increments?modCount????????System.arraycopy(a,?0,?elementData,?size,?numNew);????????size?+=?numNew;????????return?numNew?!=?0;????}????public?boolean?addAll(int?index,?Collection?extends?E>?c)?{????????//?范圍檢查????????rangeCheckForAdd(index);????????Object[]?a?=?c.toArray();????????int?numNew?=?a.length;????????//?確認容量????????ensureCapacityInternal(size?+?numNew);??//?Increments?modCount????????int?numMoved?=?size?-?index;????????if?(numMoved?>?0)????????????System.arraycopy(elementData,?index,?elementData,?index?+?numNew,?numMoved);????????System.arraycopy(a,?0,?elementData,?index,?numNew);????????size?+=?numNew;????????return?numNew?!=?0;????}

有了前面單個元素的添加基礎，批量添加就很好懂了，唯一的區(qū)別就是在數(shù)組復制時，是復制整個待添加的集合。對于index位置的批量添加，中間插入的話(numMoved > 0)，第一次復制會騰出中間要添加集合長度的位置，第二次將添加的集合復制到index位置。

4.修改元素

對于ArrayList中元素的修改，如果是對象屬性的修改，可以直接修改引用對象，但對于基本類型包裝類或者String呢，并沒有辦法通過引用修改，亦或者我們要更換對象引用，這時候就需要調(diào)用set(int index, E element)。

????public?E?set(int?index,?E?element)?{????????//?范圍檢查????????rangeCheck(index);????????E?oldValue?=?elementData(index);????????elementData[index]?=?element;????????return?oldValue;????}

這個方法實現(xiàn)很容易，ArrayList的修改本質(zhì)就是對數(shù)組的值進行更改。首先進行范圍檢查，防止數(shù)組越界，這個很好理解，ArrayList內(nèi)部就是數(shù)組，然后對index位置的值進行替換即可。

????private?void?rangeCheck(int?index)?{????????if?(index?>=?size)????????????throw?new?IndexOutOfBoundsException(outOfBoundsMsg(index));????}

elementData(int index)獲取了原來的值，用于set返回值，elementData實現(xiàn)更加簡單，就是數(shù)組取值。

5.移除元素

ArrayList中移除元素的方法有三個，按索引刪除remove(int index)、按元素刪除remove(Object o)以及批量刪除removeAll(Collection> c)等。

5.1.索引刪除

????public?E?remove(int?index)?{????????//?范圍檢查????????rangeCheck(index);????????modCount++;????????E?oldValue?=?elementData(index);????????int?numMoved?=?size?-?index?-?1;????????//?是否刪除的最尾部????????if?(numMoved?>?0)????????????System.arraycopy(elementData,?index+1,?elementData,?index,?numMoved);????????elementData[--size]?=?null;?//?clear?to?let?GC?do?its?work????????return?oldValue;????}

由于移除元素，并不涉及內(nèi)部數(shù)組大小變化，所以實現(xiàn)相對較簡單。必須要的范圍檢查，這個已經(jīng)絲毫不陌生了，然后判斷是否是尾部刪除，如果不是尾部刪除，則進行System.arraycopy復制，復制的目的是將index后的元素向前挪動 1 位元素以覆蓋要刪除的index位置，然后size減 1。

在移除方法中，可以看到modCount進行增加。同時對移除后尾部的元素賦值為null了，讓GC生效。

img

5.2.按元素刪除

public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }

按元素刪除的時候，首先判斷了元素是否為null，因為ArrayList中是可以添加null的，這里不同分支的邏輯是一樣的，都是遍歷集合比較是否和傳入元素相同，只是比較一個是 == null 一個是 equals。如果相同則刪除，然后return了，所以remove(Object o)方法只會刪除集合第一個與傳入對象相同的元素。

重點就是這個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;?//?clear?to?let?GC?do?its?work????}

看到這個方法第一感覺是什么？是不是似曾相識，沒錯，fastRemove和按指針刪除基本上市一樣的，只是少了范圍校驗和獲取刪除前的元素這兩步。

5.3.批量刪除

????public?boolean?removeAll(Collection>?c)?{????????Objects.requireNonNull(c);????????return?batchRemove(c,?false);????}

對于removeAll(Collection< ? > c)，校驗非空后調(diào)用了batchRemove(Collection< ? > c, boolean complement)。

????private?boolean?batchRemove(Collection>?c,?boolean?complement)?{????????final?Object[]?elementData?=?this.elementData;????????int?r?=?0,?w?=?0;????????boolean?modified?=?false;????????try?{????????????for?(;?r?

這個方法看著可能有一點點繞，但明白其原理后就很清晰了，首先遍歷數(shù)組，找出在要移除數(shù)組中不包含的元素，從原數(shù)組頭部開始放，這樣的數(shù)有w個，即最終數(shù)組前w個元素都是在集合c中包含的，而剩下的位置的元素則不關心，最后就是講w到size的元素賦值為null，以便GC工作。

6.循環(huán)刪除

前面也提到了，ArrayList在循環(huán)刪除時會報錯，這個究竟是怎么回事呢？

如果我們想刪除一個集合中全部的某一個元素，例如下面集合ss中的a元素。

????????List?ss?=?new?ArrayList<>();????????ss.add("a");????????ss.add("b");????????ss.add("a");????????ss.add("b");????????ss.add("c");

當我們需要刪除一個時，我們可以調(diào)用remove方法刪除，根據(jù)索引或者根據(jù)元素都用，但是多個時，我們不知道每一個元素的索引，而根據(jù)值也不知道有多少個a存在，所以我們需要遍歷集合。

這時候就可能存在問題了。

????????for?(String?s?:?ss)?{????????????if("a".equals(s)){????????????????ss.remove(s);????????????}????????}

無論是fori的還是foreach的刪除，都會拋出java.util.ConcurrentModificationException，這是因為Arraylist循環(huán)時每一次取值都會調(diào)用其內(nèi)部類Itr.next()方法。

????????public?E?next()?{????????????//?校驗modCount????????????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];????????}

在該方法最開始的地方，有校驗modCount的checkForComodification()方法，這個方法中比較了modCount和expectedModCount，不相等就會拋出ConcurrentModificationException異常。

????????final?void?checkForComodification()?{????????????if?(modCount?!=?expectedModCount)????????????????throw?new?ConcurrentModificationException();????????}

那expectedModCount到底是什么，為什么和modCount不相等呢。

????private?class?Itr?implements?Iterator?{????????int?cursor;???????//?index?of?next?element?to?return????????int?lastRet?=?-1;?//?index?of?last?element?returned;?-1?if?no?such????????int?expectedModCount?=?modCount;

expectedModCount是Itr的成員變量，這個在進行循環(huán)時會初始化賦值為modCount，最開始的時候他們是相等的，經(jīng)過前面的探究，我們已經(jīng)知道在remove調(diào)用時modCount會自增，所以checkForComodification就會拋出異常。

而我們常使用的這個做法就是使用 Itr 的remove。

????????Iterator?it?=?ss.iterator();????????while?(it.hasNext()){????????????if("a".equals(it.next())){????????????????it.remove();????????????}????????}

這樣刪除時就沒有任何問題了，這是因為 Itr 的remove中，對expectedModCount進行了重新賦值，使得每一次調(diào)用后值都相等。

????????public?void?remove()?{????????????if?(lastRet?

7.其他方法

ArrayList中主要的就是構造方法、add和remove了，這幾個方法看懂后，其他方法實現(xiàn)就比較清晰了。

比如get方法，其實就是根據(jù)索引獲取了數(shù)組的元素。

????public?E?get(int?index)?{????????//?范圍檢查????????rangeCheck(index);????????//?從數(shù)組獲取值，即?elementData[index]????????return?elementData(index);????}

例如size方法， 就是返回了size屬性的值。

????public?int?size()?{????????return?size;????}

而isEmpty方法，就是判斷size是否為0.

????public?boolean?isEmpty()?{????????return?size?==?0;????}

在ArrayList中，有一個獲取子集合的subList方法，這個方法返回的是一個內(nèi)部類SubList，該類并沒重新創(chuàng)建新的數(shù)組，依舊持有了ArrayList數(shù)組的元素的引用，所以當修改ArrayList元素的時候，SubList的元素也會跟著修改，這個在實際開發(fā)中一定要注意。

????public?List?subList(int?fromIndex,?int?toIndex)?{????????subListRangeCheck(fromIndex,?toIndex,?size);????????return?new?SubList(this,?0,?fromIndex,?toIndex);????}

作者：楊小格子

https://www.cnblogs.com/imyanger/p/11963624.html

總結

以上是生活随笔為你收集整理的arraylist 初始化_ArrayList实现原理（JDK1.8）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。