ArrayList源碼分析
ArrayList 底層數據結構
- 是List一個可調整大小的數組
數組結構的優缺點:
- 數組查詢快，根據地址和索引直接獲取元素
- 數組增刪慢，每次都需要創建一個新的數組，且移動元素的位置
ArrayList繼承關係
Serializable 標記性介面
-
類的序列化由實現java.io.Serializable介面的類啟用。不實現此介面的類將不會使任何狀態序列化或反序列化。可序列化的所有子類型都是可序列化的。標記性介面沒有方法或屬性。
序列化：將對象的數據寫入文件
反序列化：將文件中的對象數據讀取出來
Cloneable 標記性介面
-
一個類實現
Cloneable介面來指示Object.clone()方法，該方法對於該類的實例進行屬性的複製是合法的。在不實現Cloneable 介面的實例上調用對象的克隆方法會拋出異常CloneNotSupportedException。 -
clone條件：
- 實現 Cloneable 介面
- 重寫clone 方法
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); // Object.clone() v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }淺克隆：基本數據類型可以完全複製，引用類型不可以，僅僅是拷貝了一份引用
深克隆：修改引用類型數據也不互相影響
RandomAccess 標記性介面
-
表明實現了這個介面的集合是支援快速隨機訪問的。
-
使用
for循環的方式獲取數據的性能優於用iterator迭代器方式開發過程中，先判斷返回的list 是否有實現RandomAccess 介面，(list instanceof RandomAccess)，再決定用那種遍歷方式。
ArrayList源碼分析
構造方法
無參構造
// 第一次調用add(E e)方法時才創建一個容量為10的數組
public ArrayList() {
// 無參構造方法，創建一個初始容量為0的空數組
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
// Object[] elementData
}
帶初始容量的構造
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);
}
}
帶單列集合的構造
public ArrayList(Collection<? extends E> c) {
// 構造方法中的集合轉數組
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// 防止c.toArray() 不返回Object[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 空數組
this.elementData = EMPTY_ELEMENTDATA;
}
}
add源碼分析
list末尾添加一個元素：
public boolean add(E e) {
// 並發修改的次數+1
modCount++;
// size當前元素的個數
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
// 當前元素的個數是否等於原數組的長度
if (s == elementData.length)
// 進入擴容
elementData = grow();
// 擴容後進行元素的賦值
elementData[s] = e;
// 元素個數+1
size = s + 1;
}
private Object[] grow() {
// 元素個數+1作為最小容量
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
// 調用newCapacity算出擴容後的容量，再調用Arrays.copyOf()把原數組的元素複製到擴容後的數組
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {
// 有溢出意識的程式碼
int oldCapacity = elementData.length;
// 擴容為原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) //DEFAULTCAPACITY_EMPTY_ELEMENTDATA空數組
return Math.max(DEFAULT_CAPACITY, minCapacity); //DEFAULT_CAPACITY = 10
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
在list指定位置添加一個元素：
public void add(int index, E element) {
// 判斷下標是否合法
rangeCheckForAdd(index);
// 並發修改次數+1
modCount++;
final int s;
Object[] elementData;
// 判斷是否需要擴容，當元素個數等於數組長度擴容
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// 將要插入的下標後所有的元素向後移動一個位置
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
// 將元素賦值給數組指定位置
elementData[index] = element;
// 元素個數+1
size = s + 1;
}
private void rangeCheckForAdd(int index) {
// 判斷下標是否合法，下標大於元素的個數或下標小於0時不合法拋IndexOutOfBoundsException異常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
添加一個單列集合：
public boolean addAll(Collection<? extends E> c) {
// 將單列集合轉為數組，底層調用Arrays.copyOf()方法
Object[] a = c.toArray();
// 並發修改的次數 +1
modCount++;
// 算出要添加的數組長度
int numNew = a.length;
// =0, 返回false, 表示添加失敗
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// numNew > 0 - 0
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
// 調用System.arraycopy將要添加的單列集合元素添加到新的list
System.arraycopy(a, 0, elementData, s, numNew);
// 修改元素個數
size = s + numNew;
return true;
}
在list指定位置添加一個單列集合：
public boolean addAll(int index, Collection<? extends E> c) {
// 判斷要添加位置的下標是否合法
rangeCheckForAdd(index);
// 將集合轉為Object數組
Object[] a = c.toArray();
// 並發修改次數 +1
modCount++;
// 算出Object數組的長度
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 判斷數組長度是否大於集合中剩餘的元素個數來進行擴容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
// 根據集合中元素的個數-要存的索引位置算出集合中要移動的個數
int numMoved = s - index;
// 如果大於0, 調用System.arraycopy方法進行數組元素的複製，index + numNew算出新下標
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
// 才真正將數據源中的元素添加到集合中
System.arraycopy(a, 0, elementData, index, numNew);
// 重新計算集合元素的個數
size = s + numNew;
return true;
}
set源碼分析
public E set(int index, E element) {
// 判斷index是否合法, 當index下標小於0或大於等於集合中元素的個數時拋異常
Objects.checkIndex(index, size);
// 獲得index下標的舊值
E oldValue = elementData(index);
// 修改下標的值
elementData[index] = element;
// 返回舊值
return oldValue;
}
public static int checkIndex(int index, int length) {
return Preconditions.checkIndex(index, length, null);
}
int checkIndex(int index, int length,
BiFunction<String, List<Integer>, X> oobef) {
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
return index;
}
get源碼解析
public E get(int index) {
// 判斷index是否合法, 當index下標小於0或大於等於集合中元素的個數時拋異常
Objects.checkIndex(index, size);
// 返回index位置的元素
return elementData(index);
}
toString() 源碼解析
public abstract class AbstractCollection<E> implements Collection<E> {
public String toString() {
// 獲取迭代器
Iterator<E> it = iterator();
// 如果迭代器沒有元素，直接返回空
if (! it.hasNext())
return "[]";
// 創建一個StringBuilder對象
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
// 調用迭代器的方法取出元素
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
// 如果沒有元素了, 調用toString()將StringBulilder對象轉成字元串
if (! it.hasNext())
return sb.append(']').toString();
// 如果有元素就調用StringBuilder的append方法追加元素
sb.append(',').append(' ');
}
}
}
迭代器iterator源碼分析
public Iterator<E> iterator() {
return new Itr();
}
// ArrayList的迭代器源碼, 不同集合實現迭代器源碼的方式不同
private class Itr implements Iterator<E> {
int cursor; // 游標, 默認值是0
int lastRet = -1; // 記錄-1
// 將集合的實際修改次數賦值給預期修改次數
int expectedModCount = modCount;
// prevent creating a synthetic constructor
Itr() {}
// 調用hasNext() 判斷集合是否有元素, 比較游標cursor和集合中元素的個數size是否不相等
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
// 檢查集合實際修改次數是否不等於預期修改次數, 不等於則拋出並發修改異常
checkForComodification();
// 將游標賦值給i
int i = cursor;
// 如果i >= 集合中的元素，說明沒有元素了，拋出沒有元素異常
if (i >= size)
throw new NoSuchElementException();
// 把集合存儲數據的數組地址賦值該方法的局部變數
Object[] elementData = ArrayList.this.elementData;
// 如果 i >= 數組長度，拋出並發修改異常
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 游標向下移動
cursor = i + 1;
// 從數組中取出元素並返回
return (E) elementData[lastRet = i];
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int size = ArrayList.this.size;
int i = cursor;
if (i < size) {
final Object[] es = elementData;
if (i >= es.length)
throw new ConcurrentModificationException();
for (; i < size && modCount == expectedModCount; i++)
action.accept(elementAt(es, i));
// update once at end to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
}
final void checkForComodification() {
// 判斷集合實際修改次數是否不等於預期修改次數
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
並發修改異常
/**
測試程式碼=====
**/
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
if (s.equals("3")) {
list.remove("3");
}
}
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
// java的label語法, 通過命名一個語句塊name, 然後調用 break name跳出該語句塊
found: {
// 判斷要刪除的元素是否為null
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
// 調用fastRemove進行刪除
fastRemove(es, i);
return true;
}
private void fastRemove(Object[] es, int i) {
// 集合實際修改次數 +1
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
// （newSize - i） = 計算要被移動的元素個數
System.arraycopy(es, i + 1, es, i, newSize - i);
// 讓刪除的元素置為null, 為了儘快被垃圾回收
es[size = newSize] = null;
}
在調用add()方法時，實際修改次數會+1，而在獲取iterator迭代器時只會執行一次將實際修改次數賦值給預期修改次數，在調用remove(Object o)刪除元素時，實際修改次數也會+1，最終導致在下一次next() 的時候檢查到實際修改次數不等於預期修改次數，從而拋出並發修改異常。
並發修改異常特殊情況
/**
測試程式碼=====
**/
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
if (s.equals("2")) {
list.remove("2");
}
}
當要刪除的元素在集合的倒數第二個位置的時候，不會產生並發修改異常。
原因是 ：因為在調用hasNext方法時，游標cursor的值和元素個數的值size一樣，返回false，不會繼續調用next方法，也就不會去檢查實際修改次數是否不等於預期修改次數。
iterator的默認方法remove
/**
測試程式碼=====
**/
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
if (s.equals("3")) {
iterator.remove();
}
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 調用remove()方法，每次會對預期修改次數重新賦值，不會產生並發修改異常
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
clear源碼分析
public void clear() {
// 並發修改次數 +1
modCount++;
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
// 把數組的每一個位置元素都置為null，讓垃圾回收器儘快回收
es[i] = null;
}
contains源碼分析
public boolean contains(Object o) {
// 調用 indexOf(o)方法，如果返回-1，說明沒有找到，返回false; 如果返回值>=0，說明找到了，返回true
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
// 如果contains的參數是null
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
// 返回數組下標
return i;
}
}
}
return -1;
}
isEmpty源碼分析
public boolean isEmpty() {
// 判斷元素個數是否等於0
return size == 0;
}
