ArrayList源碼解析(一)
- 2019 年 10 月 24 日
- 筆記
歡迎轉載，轉載煩請註明出處，謝謝。
https://www.cnblogs.com/sx-wuyj/p/11177257.html
自己學習ArrayList源碼的一些心得記錄..
1.1 ArrayList的體系
- Iterable : iterable接口裡定義了返回iterator的方法，相當於對iterator的封裝，同時實現了iterable接口的類可以支持for each循環;
- Collction : 集合框架中的根接口,下面有三大子接口.List Set Queue;
- AbstractCollection: 實現了Collection的一些接口,同時也定義了一些抽象方法交給子類實現.
- List : List接口定義了一些公用的接口,比如 toArray() size() add()等接口;
-
AbstractList :AbstractList 是一個抽象類，實現了List接口，是隸屬於Java集合框架中的根接口 Collection 的分支
1.2 ArrayList構造方法.
/** * 有參構造 int類型 集合的大小 */ public ArrayList(int initialCapacity) { //如果參數大於0,緩衝數組的大小就為該參數 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; //如果參數等於0,創建一個空的實例數組 } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { //異常為非法容量 + 參數 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * Constructs an empty list with an initial capacity of ten. * 無參構造 */ public ArrayList() { //緩衝數組為空的默認大小的共享實例 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //有參構造 參數為任意類或者E的子類 //任意類或者E的子類,孫子類等collection都可以構造一個ArrayList出來 public ArrayList(Collection<? extends E> c) { //轉為緩存數組 elementData = c.toArray(); //將數組的長度賦值給size,如果數組長度不等於0 if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) //緩存數組的class不等於object類型數組的class if (elementData.getClass() != Object[].class) //copyOf方法:返回一個數組 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. //替換為一個空的數組 this.elementData = EMPTY_ELEMENTDATA; } }以上就是ArrayList的構造方法,注釋是我自己一行一行寫出來的,可能會有所誤解,歡迎批評指正.
1.3 arrayList常用的方法
- add() : 向集合內部添加元素,這個方法其實是Collection接口中定義的,AbstractCollection抽象類中實現這個方法,ArrayList中重寫了這個方法.如果直接調用AbstractCollection中的add方法,那麼只會拋出一個不支持操作的異常.需要注意一點就是add()一共有兩個,但是其中一個是有boolean的返回值,另一個是void並沒有返回值.
boolean返回值add(),元素添加是為最後一位.
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }首先看一下 ensureCapacityInternal(size + 1)這個方法
private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //max方法為一個三元運算,參數類型為int類型,(a >= b) ? a : b; //size+1 大於等於 初始值 返回初始值10 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } 又調用了ensureExplicitCapacity()方法 private void ensureExplicitCapacity(int minCapacity) { modCount++; //需要的大小大於底層數組的大小 if (minCapacity - elementData.length > 0) grow(minCapacity); } 繼續調用了grow()方法,這個方法很關鍵,先看源碼 private void grow(int minCapacity) { //數組長度賦值給oldCapacity int oldCapacity = elementData.length; //oldCapacity >> 1 相當於 oldCapacity / 2 //newCapacity 為數組長度的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity小於minCapacity if (newCapacity - minCapacity < 0) //minCapacity賦值於newCapacity newCapacity = minCapacity; //newCapacity大於MAX_ARRAY_SIZE if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //通過copyOf方法返回一個數組 elementData = Arrays.copyOf(elementData, newCapacity); }整體來說 如果size+1小於10,那麼minCapacity就是10,10就是默認大小.如果大於10,那麼minCapacity則為size+1.
minCapacity-lementData.length 如果size+1比底層數組小,那麼可以繼續向默認數組中添加元素.如果size+1大於底層數組,就調用grow()進行擴容.
grow()這個方法就是arrayList自動擴容的方法.newCapacity為數組的1.5倍,先判斷newCapacity是否小於
minCapacity,也就是size+1
如果小於那麼將minCapacity賦值於newCapacity.
再判斷newCapacity是否大於MAX_ARRAY_SIZE,關於MAX_ARRAY_SIZE下面有代碼.
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;
如果大於就調用hugeCapacity()方法
private static int hugeCapacity(int minCapacity) { //minCapacity 小於 0 報錯 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //minCapacity大於MAX_ARRAY_SIZE嗎? //大於返回Integer.MAX_VALUE //小於返回MAX_ARRAY_SIZE return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }最後將elementData,也就是底層數組.lenth變為newCapacity.
總結起來說,arrayList的擴容機制其實就修改底層數組的大小.
繼續回頭add()方法往下看:
elementData[size++] = e;
這個其實很好理解了,e就是你要添加的那個新的元素,size++就是新元素在底層數組中的位置.
return true;
最後返回一個 true 添加成功
void add(),
public void add(int index, E element) { //校驗index rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } rangeCheckForAdd(index);
private void rangeCheckForAdd(int index) { //如果index大於size或者index小於0 就拋出異常 if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }ensureCapacityInternal(size + 1);
這個在前面有說過,就不在細說,可以去看一下前面add()帶返回值的那個解析.
System.arraycopy(elementData, index, elementData, index + 1,size – index);
調用System提供的arraycopy(),這是一個靜態native方法,native這裡不進行說明,可以百度進行查看.這個方法就是現數組之間的複製。
elementData:底層數組. index:數組要複製的起始位置. elementData:複製後的數組. index + 1:數組放置的起始位置. size - index:複製的長度elementData[index] = element;
將要添加的元素放入指定的位置.
size++
將集合的長度+1.
