arraylist能否接收強轉類型_ArrayList 源碼解析

點擊上方"IT牧場"，選擇"設為星標"

技術干貨每日送達！

前言

JDK源碼解析系列文章，都是基于JDK8分析的，雖然JDK14已經出來，但是JDK8我還不會，我…

類圖

實現了RandomAccess接口，可以隨機訪問
實現了Cloneable接口，可以克隆
實現了Serializable接口，可以序列化、反序列化
實現了List接口，是List的實現類之一
實現了Collection接口，是Java Collections Framework成員之一
實現了Iterable接口，可以使用for-each迭代

屬性

//?序列化版本UID
private?static?final?long
????????serialVersionUID?=?8683452581122892189L;

/**
?*?默認的初始容量
?*/
private?static?final?int
????????DEFAULT_CAPACITY?=?10;

/**
?*?用于空實例的共享空數組實例
?*?new?ArrayList(0);
?*/
private?static?final?Object[]
????????EMPTY_ELEMENTDATA?=?{};

/**
?*?用于提供默認大小的實例的共享空數組實例
?*?new?ArrayList();
?*/
private?static?final?Object[]
????????DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};

/**
?*?存儲ArrayList元素的數組緩沖區
?*?ArrayList的容量，是數組的長度
?*?
?*?non-private?to?simplify?nested?class?access
?*/
transient?Object[]?elementData;

/**
?*?ArrayList中元素的數量
?*/
private?int?size;

小朋友，你四否有很多問號？

為什么空實例默認數組有的時候是EMPTY_ELEMENTDATA，而又有的時候是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
為什么elementData要被transient修飾
為什么elementData沒有被private修飾？難道正如注釋所寫的non-private to simplify nested class access

帶著問題，我們繼續往下看。

構造方法

帶初始容量的構造方法

/**
?*?帶一個初始容量參數的構造方法
?*
?*?@param??initialCapacity??初始容量
?*?@throws??如果初始容量非法就拋出
?*??????????IllegalArgumentException
?*/
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);
????}
}

如果initialCapacity ，就創建一個新的長度是initialCapacity的數組
如果initialCapacity == 0，就使用EMPTY_ELEMENTDATA
其他情況，initialCapacity不合法，拋出異常

無參構造方法

/**
?*?無參構造方法?將elementData?賦值為
?*???DEFAULTCAPACITY_EMPTY_ELEMENTDATA
?*/
public?ArrayList()?{
????this.elementData?=
????????????DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

帶一個集合參數的構造方法

/**
?*?帶一個集合參數的構造方法
?*
?*?@param?c?集合，代表集合中的元素會被放到list中
?*?@throws?如果集合為空，拋出NullPointerException
?*/
public?ArrayList(Collection?extends?E>?c)?{
????elementData?=?c.toArray();
????//?如果?size?!=?0
????if?((size?=?elementData.length)?!=?0)?{
????????//?c.toArray?可能不正確的，不返回?Object[]
????????//?https://bugs.openjdk.java.net/browse/JDK-6260652
????????if?(elementData.getClass()?!=?Object[].class)
????????????elementData?=?Arrays.copyOf(
????????????????????elementData,?size,?Object[].class);
????}?else?{
????????//?size?==?0
????????//?將EMPTY_ELEMENTDATA?賦值給?elementData
????????this.elementData?=?EMPTY_ELEMENTDATA;
????}
}

使用將集合轉換為數組的方法
為了防止c.toArray()方法不正確的執行，導致沒有返回Object[]，特殊做了處理
如果數組大小等于0，則使用 EMPTY_ELEMENTDATA

那么問題來了，什么情況下c.toArray()會不返回Object[]呢？

public?static?void?main(String[]?args)?{
????List?list?=?new?ArrayList<>(Arrays.asList("list"));//?class?java.util.ArrayList
????System.out.println(list.getClass());
????Object[]?listArray?=?list.toArray();//?class?[Ljava.lang.Object;
????System.out.println(listArray.getClass());
????listArray[0]?=?new?Object();
????System.out.println();
????List?asList?=?Arrays.asList("asList");//?class?java.util.Arrays$ArrayList
????System.out.println(asList.getClass());
????Object[]?asListArray?=?asList.toArray();//?class?[Ljava.lang.String;
????System.out.println(asListArray.getClass());//?java.lang.ArrayStoreException
????asListArray[0]?=?new?Object();
}

我們通過這個例子可以看出來，java.util.ArrayList.toArray()方法會返回Object[]沒有問題。而java.util.Arrays的私有內部類ArrayList的toArray()方法可能不返回Object[]。

為什么會這樣？

我們看ArrayList的toArray()方法源碼：

public?Object[]?toArray()?{
????//?ArrayLisy中?elementData是這樣定義的
????//?transient?Object[]?elementData;
????return?Arrays.copyOf(elementData,?size);
}

使用了Arrays.copyOf()方法：

public?static??T[]?copyOf(T[]?original,?int?newLength)?{//?original.getClass()?是?class?[Ljava.lang.Objectreturn?(T[])?copyOf(original,?newLength,?original.getClass());
}

copyOf()的具體實現：

public?static??T[]?copyOf(U[]?original,?int?newLength,?Class?extends?T[]>?newType)?{@SuppressWarnings("unchecked")/**
?????*?如果newType是Object[]?copy?數組?類型就是?Object?
?????*?否則就是?newType?類型
?????*/
????T[]?copy?=?((Object)newType?==?(Object)Object[].class)
??????????(T[])?new?Object[newLength]
????????:?(T[])?Array.newInstance(newType.getComponentType(),?newLength);
????System.arraycopy(original,?0,?copy,?0,
?????????????????????Math.min(original.length,?newLength));return?copy;
}

我們知道ArrayList中elementData就是Object[]類型，所以ArrayList的toArray()方法必然會返回Object[]。

我們再看一下java.util.Arrays的內部ArrayList源碼(截取的部分源碼)：

private?static?class?ArrayList<E>?extends?AbstractList<E>implements?RandomAccess,?java.io.Serializable?{

????//?存儲元素的數組
????private?final?E[]?a;

????ArrayList(E[]?array)?{
????????//?直接把接收的數組?賦值?給?a
????????a?=?Objects.requireNonNull(array);
????}

????/**
?????*?obj?為空拋出異常
?????*?不為空?返回?obj
?????*/
????public?static??T?requireNonNull(T?obj)?{if?(obj?==?null)throw?new?NullPointerException();return?obj;
????}@Overridepublic?Object[]?toArray()?{//?返回?a?的克隆對象return?a.clone();
????}
}

這是Arrays.asList()方法源碼

public?static??List?asList(T...?a)?{return?new?ArrayList<>(a);
}

不難看出來java.util.Arrays的內部ArrayList的toArray()方法，是構造方法接收什么類型的數組，就返回什么類型的數組。

所以，在我們上面的例子中，實際上返回的是String類型的數組，再將其中的元素賦值成Object類型的，自然報錯。

我們還是繼續看ArrayList吧…

插入方法

在列表最后添加指定元素

/**
?*?在列表最后添加指定元素
?*
?*?@param?e?要添加的指定元素
?*?@return?true
?*/
public?boolean?add(E?e)?{
????//?增加?modCount?！！
????ensureCapacityInternal(size?+?1);?
????elementData[size++]?=?e;
????return?true;
}

在父類AbstractList上，定義了modCount 屬性，用于記錄數組修改的次數。

在指定位置添加指定元素

/**
?*?在指定位置添加指定元素
?*?如果指定位置已經有元素，就將該元素和隨后的元素移動到右面一位
?*
?*?@param?index?待插入元素的下標
?*?@param?element?待插入的元素
?*?@throws?可能拋出?IndexOutOfBoundsException
?*/
public?void?add(int?index,?E?element)?{
????rangeCheckForAdd(index);


????//?增加?modCount?！！
????ensureCapacityInternal(size?+?1);
????System.arraycopy(elementData,?index,?elementData,?index?+?1,
?????????????????????size?-?index);
????elementData[index]?=?element;
????size++;
}

插入方法調用的其他私有方法

/**
?*?計算容量
?*/
private?static?int?calculateCapacity(
????????Object[]?elementData,?int?minCapacity)?{

????if?(elementData?==
????????????DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{
????????return?Math.max(DEFAULT_CAPACITY,?minCapacity);
????}
????return?minCapacity;
}

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

private?void?ensureExplicitCapacity(int?minCapacity)?{
????modCount++;

????//?overflow-conscious?code
????if?(minCapacity?-?elementData.length?>?0)
????????grow(minCapacity);
}

擴容方法

/**
?*?數組可以分配的最大size
?*?一些虛擬機在數組中預留一些header?words
?*?如果嘗試分配更大的size，可能導致OutOfMemoryError
?*/
private?static?final?int?MAX_ARRAY_SIZE?=?Integer.MAX_VALUE?-?8;

/**
?*?增加容量，至少保證比minCapacity大
?*?@param?minCapacity?期望的最小容量
?*/
private?void?grow(int?minCapacity)?{
????//?有可能溢出的代碼
????int?oldCapacity?=?elementData.length;
????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);
????if?(newCapacity?-?minCapacity?0)
????????newCapacity?=?minCapacity;
????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);
}

/**
?*?最大容量返回?Integer.MAX_VALUE
?*/
private?static?int?hugeCapacity(int?minCapacity)?{
????if?(minCapacity?0)?//?overflow
????????throw?new?OutOfMemoryError();
????return?(minCapacity?>?MAX_ARRAY_SIZE)??
????????Integer.MAX_VALUE?:
????????MAX_ARRAY_SIZE;
}

通常情況新容量是原來容量的1.5倍
如果原容量的1.5倍比minCapacity小，那么就擴容到minCapacity
特殊情況擴容到Integer.MAX_VALUE

看完構造方法、添加方法、擴容方法之后，上文第1個問題終于有了答案。原來，new ArrayList()會將elementData 賦值為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，new ArrayList(0)會將elementData 賦值為 EMPTY_ELEMENTDATA，EMPTY_ELEMENTDATA添加元素會擴容到容量為1，而DEFAULTCAPACITY_EMPTY_ELEMENTDATA擴容之后容量為10。

通過反射我們可以驗證這一想法。如下：

public?static?void?main(String[]?args)?{
????printDefaultCapacityList();
????printEmptyCapacityList();
}

public?static?void?printDefaultCapacityList()?{
????ArrayList?defaultCapacity?=?new?ArrayList();
????System.out.println(
????????????"default?初始化長度："?+?getCapacity(defaultCapacity));

????defaultCapacity.add(1);
????System.out.println(
????????????"default?add?之后?長度："?+?getCapacity(defaultCapacity));
}

public?static?void?printEmptyCapacityList()?{
????ArrayList?emptyCapacity?=?new?ArrayList(0);
????System.out.println(
????????????"empty?初始化長度："?+?getCapacity(emptyCapacity));

????emptyCapacity.add(1);
????System.out.println(
????????????"empty?add?之后?長度："?+?getCapacity(emptyCapacity));
}

public?static?int?getCapacity(ArrayList>?arrayList)?{
????Class?arrayListClass?=?ArrayList.class;try?{//?獲取?elementData?字段
????????Field?field?=?arrayListClass.getDeclaredField("elementData");//?開啟訪問權限
????????field.setAccessible(true);//?把示例傳入get，獲取實例字段elementData的值
????????Object[]?objects?=?(Object[])?field.get(arrayList);//返回當前ArrayList實例的容量值return?objects.length;
????}?catch?(Exception?e)?{
????????e.printStackTrace();return?-1;
????}
}

移除方法

移除指定下標元素方法

/**
?*?移除列表中指定下標位置的元素
?*?將所有的后續元素，向左移動
?*
?*?@param?要移除的指定下標
?*?@return?返回被移除的元素
?*?@throws?下標越界會拋出IndexOutOfBoundsException
?*/
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);
????//?將引用置空，讓GC回收
????elementData[--size]?=?null;

????return?oldValue;
}

移除指定元素方法

/**
?*?移除第一個在列表中出現的指定元素
?*?如果存在，移除返回true
?*?否則，返回false
?*
?*?@param?o?指定元素
?*/
public?boolean?remove(Object?o)?{
????if?(o?==?null)?{
????????for?(int?index?=?0;?index?????????????if?(elementData[index]?==?null)?{
????????????????fastRemove(index);
????????????????return?true;
????????????}
????}?else?{
????????for?(int?index?=?0;?index?????????????if?(o.equals(elementData[index]))?{
????????????????fastRemove(index);
????????????????return?true;
????????????}
????}
????return?false;
}

移除方法名字、參數的個數都一樣，使用的時候要注意。

私有移除方法

/*
?*?私有的?移除?方法?跳過邊界檢查且不返回移除的元素
?*/
private?void?fastRemove(int?index)?{
????modCount++;
????int?numMoved?=?size?-?index?-?1;
????if?(numMoved?>?0)
????????System.arraycopy(elementData,?index+1,?elementData,?index,
?????????????????????????numMoved);
????//?將引用置空，讓GC回收
????elementData[--size]?=?null;
}

查找方法

查找指定元素的所在位置

/**
?*?返回指定元素第一次出現的下標
?*?如果不存在該元素，返回?-1
?*?如果?o?==null?會特殊處理
?*/
public?int?indexOf(Object?o)?{
????if?(o?==?null)?{
????????for?(int?i?=?0;?i?????????????if?(elementData[i]==null)
????????????????return?i;
????}?else?{
????????for?(int?i?=?0;?i?????????????if?(o.equals(elementData[i]))
????????????????return?i;
????}
????return?-1;
}

查找指定位置的元素

/**
?*?返回指定位置的元素
?*
?*?@param??index?指定元素的位置?
?*?@throws?index越界會拋出IndexOutOfBoundsException
?*/
public?E?get(int?index)?{
????rangeCheck(index);

????return?elementData(index);
}

該方法直接返回elementData數組指定下標的元素，效率還是很高的。所以ArrayList，for循環遍歷效率也是很高的。

序列化方法

/**
?*?將ArrayLisy實例的狀態保存到一個流里面
?*/
private?void?writeObject(java.io.ObjectOutputStream?s)throws?java.io.IOException{
????//?Write?out?element?count,?and?any?hidden?stuff
????int?expectedModCount?=?modCount;
????s.defaultWriteObject();

????//?Write?out?size?as?capacity?for?behavioural?compatibility?with?clone()
????s.writeInt(size);

????//?按照順序寫入所有的元素
????for?(int?i=0;?i????????s.writeObject(elementData[i]);
????}

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

反序列化方法

/**
?*?根據一個流(參數)重新生成一個ArrayList
?*/
private?void?readObject(java.io.ObjectInputStream?s)throws?java.io.IOException,?ClassNotFoundException?{
????elementData?=?EMPTY_ELEMENTDATA;

????//?Read?in?size,?and?any?hidden?stuff
????s.defaultReadObject();

????//?Read?in?capacity
????s.readInt();

????if?(size?>?0)?{
????????//?be?like?clone(),?allocate?array?based?upon?size?not?capacity
????????ensureCapacityInternal(size);

????????Object[]?a?=?elementData;
????????//?Read?in?all?elements?in?the?proper?order.
????????for?(int?i=0;?i????????????a[i]?=?s.readObject();
????????}
????}
}

看完序列化，反序列化方法，我們終于又能回答開篇的第二個問題了。elementData之所以用transient修飾，是因為JDK不想將整個elementData都序列化或者反序列化，而只是將size和實際存儲的元素序列化或反序列化，從而節省空間和時間。

創建子數組

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

我們看一下簡短版的SubList：

private?class?SubList?extends?AbstractList<E>?implements?RandomAccess?{
????private?final?AbstractList?parent;private?final?int?parentOffset;private?final?int?offset;int?size;
????SubList(AbstractList?parent,int?offset,?int?fromIndex,?int?toIndex)?{this.parent?=?parent;this.parentOffset?=?fromIndex;this.offset?=?offset?+?fromIndex;this.size?=?toIndex?-?fromIndex;this.modCount?=?ArrayList.this.modCount;
????}public?E?set(int?index,?E?e)?{
????????rangeCheck(index);
????????checkForComodification();
????????E?oldValue?=?ArrayList.this.elementData(offset?+?index);
????????ArrayList.this.elementData[offset?+?index]?=?e;return?oldValue;
????}//?省略代碼...
}

SubList的set()方法，是直接修改ArrayList中elementData數組的，使用中應該注意
SubList是沒有實現Serializable接口的，是不能序列化的

迭代器

創建迭代器方法

public?Iterator?iterator()?{
????return?new?Itr();
}

Itr屬性

//?下一個要返回的元素的下標
int?cursor;
//?最后一個要返回元素的下標?沒有元素返回?-1
int?lastRet?=?-1;
//?期望的?modCount
int?expectedModCount?=?modCount;

Itr的hasNext() 方法

public?boolean?hasNext()?{
????return?cursor?!=?size;
}

Itr的next()方法

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，不等于就會拋出著名的ConcurrentModificationException異常。什么時候會拋出ConcurrentModificationException？

public?static?void?main(String[]?args)?{
????ArrayList?arrayList?=?new?ArrayList();
????for?(int?i?=?0;?i?10;?i++)?{
????????arrayList.add(i);
????}
????remove(arrayList);
????System.out.println(arrayList);
}

public?static?void?remove(ArrayList?list)?{
????Iterator?iterator?=?list.iterator();while?(iterator.hasNext())?{
????????Integer?number?=?iterator.next();if?(number?%?2?==?0)?{//?拋出ConcurrentModificationException異常
????????????list.remove(number);
????????}
????}
}

那怎么寫才能不拋出ConcurrentModificationException？很簡單，將list.remove(number);換成iterator.remove();即可。why？請看Itr的remove()源碼…

Itr的remove()方法

public?void?remove()?{
????if?(lastRet?0)
????????throw?new?IllegalStateException();
????checkForComodification();

????try?{
????????ArrayList.this.remove(lastRet);
????????cursor?=?lastRet;
????????lastRet?=?-1;
????????//?移除之后將modCount?重新賦值給?expectedModCount
????????expectedModCount?=?modCount;
????}?catch?(IndexOutOfBoundsException?ex)?{
????????throw?new?ConcurrentModificationException();
????}
}

原因就是因為Itr的remove()方法，移除之后將modCount重新賦值給 expectedModCount。這就是源碼，不管單線程還是多線程，只要違反了規則，就會拋異常。

源碼看的差不多了，開篇的問題卻還剩一個！到底為什么elementData沒有用private修飾呢？

我們知道的，private修飾的變量，內部類也是可以訪問到的。難道注釋中non-private to simplify nested class access的這句話有毛病？

當我們看表面看不到什么東西的時候，不妨看一下底層。

測試類代碼：

一頓javac、javap之后(使用JDK8)：

再一頓javac、javap之后(使用JDK11)：

雖然字節碼指令我還看不太懂，但是我能品出來，注釋是沒毛病的，private修飾的確會影響內部類的訪問。

ArrayList類注釋翻譯

類注釋還是要看的，能給我們一個整體的了解這個類。我將ArrayList的類注釋大概翻譯整理了一下：

ArrayList是實現List接口的可自動擴容的數組。實現了所有的List操作，允許所有的元素，包括null值。
ArrayList大致和Vector相同，除了ArrayList是非同步的。
size isEmpty get set iterator 和 listIterator 方法時間復雜度是O(1)，常量時間。其他方法是O(n)，線性時間。
每一個ArrayList實例都有一個capacity(容量)。capacity是用于存儲列表中元素的數組的大小。capacity至少和列表的大小一樣大。
如果多個線程同時訪問ArrayList的實例，并且至少一個線程會修改，必須在外部保證ArrayList的同步。修改包括添加刪除擴容等操作，僅僅設置值不包括。這種場景可以用其他的一些封裝好的同步的list。如果不存在這樣的Object，ArrayList應該用Collections.synchronizedList包裝起來最好在創建的時候就包裝起來，來保證同步訪問。
iterator()和listIterator(int)方法是fail-fast的，如果在迭代器創建之后，列表進行結構化修改，迭代器會拋出ConcurrentModificationException。
面對并發修改，迭代器快速失敗、清理，而不是在未知的時間不確定的情況下冒險。請注意，快速失敗行為不能被保證。通常來講，不能同步進行的并發修改幾乎不可能做任何保證。因此，寫依賴這個異常的程序的代碼是錯誤的，快速失敗行為應該僅僅用于防止bug。

總結

ArrayList底層的數據結構是數組
ArrayList可以自動擴容，不傳初始容量或者初始容量是0，都會初始化一個空數組，但是如果添加元素，會自動進行擴容，所以，創建ArrayList的時候，給初始容量是必要的
Arrays.asList()方法返回的是的Arrays內部的ArrayList，用的時候需要注意
subList()返回內部類，不能序列化，和ArrayList共用同一個數組
迭代刪除要用，迭代器的remove方法，或者可以用倒序的for循環
ArrayList重寫了序列化、反序列化方法，避免序列化、反序列化全部數組，浪費時間和空間
elementData不使用private修飾，可以簡化內部類的訪問

源碼系列第一篇，一不小心就寫的有點長。但是懵懂到深刻的過程還是挺耐人尋味的。文章中沒有展開的點，或者你有什么其他好奇的地方，歡迎留言討論。我們下篇文章再見…

干貨分享

最近將個人學習筆記整理成冊，使用PDF分享。關注我，回復如下代碼，即可獲得百度盤地址，無套路領取！
?001：《Java并發與高并發解決方案》學習筆記；?002：《深入JVM內核——原理、診斷與優化》學習筆記；?003：《Java面試寶典》?004：《Docker開源書》?005：《Kubernetes開源書》?006：《DDD速成(領域驅動設計速成)》?007：全部?008：加技術討論群

近期熱文

?徹底解決 GitHub 拉取代碼網速慢的問題?基于 SpringBoot2 和 Netty 實現一個簡易的RPC通信框架?一本徹底搞懂MySQL索引優化EXPLAIN百科全書?盤點 10 個代碼重構的小技巧?性能測試如何定位瓶頸？偶發超時？看高手如何快速排查問題?震精！Spring Boot內存泄露，排查竟這么難！

想知道更多？長按/掃碼關注我吧↓↓↓>>>技術討論群<<<喜歡就點個"在看"唄^_^