今天有事嗎？可以抽半個小時時間從原始碼去學習ArrayList，從而徹底掌握它，
簡介
ArrayList是一個陣列集合，了解它的特性我們從原始碼看它繼承以及實作的介面就可以，
首先它繼承 AbstractList類，實作了List，RandomAccess、Cloneable、java.io.Serializable介面，
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- List：提供List基本方法，同時讓ArrayList有集合的方法以及行為屬性，
- RandomAccess：該實作類支持隨機訪問，也就是下標訪問 get（index），
- Cloneable：該類是克隆的介面，不僅僅實作了淺拷貝，也可以重寫該類去實作深拷貝，
淺拷貝：
基本資料型別的變數拷貝之后是獨立的，不會隨著源變數變動而變
String型別拷貝之后也是獨立的
參考型別拷貝的是參考地址，拷貝前后的變數參考同一個堆中的物件，
深拷貝：
變數的所有參考型別變數（除了String）都需要實作Cloneable（陣列可以直接呼叫clone方法），clone方法中，參考型別需要各
- java.io.Serializable：該類是序列化介面，
結合上面介面分析，所以ArrayList 是支持快速訪問、復制、序列化的，
ArrayList類
基本屬性
//序列化版本號：類內容的改變會影響版本號變化，導致反序列化失敗（自動生成或自己定義）
private static final long serialVersionUID = 8683452581122892189L;
//如果實體化時未指定容量，則在初次添加元素時會進行擴容使用此容量作為陣列長度
private static final int DEFAULT_CAPACITY = 10;
//一個空由于某些操作導致資料變成空的陣列
private static final Object[] EMPTY_ELEMENTDATA = {};
//利用無參構造器，無論創建多少個默認的ArrayList，只要不添加元素都會指向這個空陣列節省空間
//它和上面就是該陣列再次添加元素會自動擴容10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList存盤資料的地方 transient 是禁止序列化
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList中的元素個數
private int size;
ArrayList arr = new ArrayList();
arr.add(1);
size大小是10，而elementData大小是默認初始化大小10
構造方法
/*
把DEFAULTCAPACITY_EMPTY_ELEMENTDATA賦值給elementData
第一次添加元素時容量擴大至 10 的，
*/
ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/*
當 initialCapacity 為零時則是把 EMPTY_ELEMENTDATA 賦值給 elementData，
當 initialCapacity 大于零時初始化一個大小為 initialCapacity
的 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);
}
}
/*
將collection轉換成陣列，存盤在elementData
if c.toArray成object[]失敗用Arrays.copyOf將elementData存盤資料
轉換成object[]物件拷貝到elementData中
*/
//ArrayList（Collection<? extends E> c）
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;
}
}
基本操作
這部分的方法我就不介紹了，大家看看就行，ArrayList的很簡單基礎的操作，
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
修剪大小
//就是把ArrayList陣列中的空位置給減掉了
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
添加元素–默認尾部添加
//在末尾添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//如果elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA（創建的新陣列）
//按照取出來的最大值也就是10進行擴容elementData.
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//運算元++，運算元用來多執行緒中一個執行緒正在操作ArrayList，而另一個也進行操作完成
//導致該執行緒運算元變化從而引起報錯，
//if所需要的最小空間沒有elementData陣列長度大，就需要擴容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//ArrayList的elementData陣列長度的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//擴容操作 容量擴大原來容量的1.5倍，如果擴大1.5倍的陣列長度還小于minCapacity
//陣列長度擴容到minCapacity，將新陣列拷貝到elementData
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);
}
想要提升ArrayList的大批量插入速度，我們可以減少擴容操作，給一個大的初始值進行創建ArrayList，這樣做能夠使得ArrayList的大批量插入元素速度變得非常快，
指定下標添加元素
public void add(int index, E element) {
//檢查下標是否越界，越界報錯
rangeCheckForAdd(index);
//判斷是否需要擴容,記錄運算元
ensureCapacityInternal(size + 1);
//講index位置之后的元素向后移動1個位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在index位置添加元素
elementData[index] = element;
size++;
}
洗掉元素
//洗掉指定下標的元素
public E remove(int index) {
//檢查是否越界
rangeCheck(index);
//運算元++
modCount++;
//把下標是index的元素取出來
E oldValue = elementData(index);
//需要移動的長度，如果==0就不必拷貝移動了，ps：size = 1而index為0，那么洗掉一個元
//素之后為空，就不必arraycopy
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;
}
//洗掉指定元素
public boolean remove(Object o) {
//如果元素為null直接快速洗掉
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;
}
//指定下標快速洗掉，和第一個洗掉一樣，只不過不需要回傳洗掉元素的值
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
}
迭代器 iterator
private class Itr implements Iterator<E> {
//游標記錄下一個元素的位置
int cursor;
//上一個操作的元素位置，若為-1就是沒有上一個操作的歷史元素
//個人理解就是回傳上一步，如果-1就是無法回傳上一步
int lastRet = -1;
//期望運算元 快速失敗判斷條件，modCount是否發生變化，
int expectedModCount = modCount;
//快速失敗：modCound是一個全域變數，如果當用戶A正在遍歷arr，而這時候
//B對arr進行add或者remove操作，導致modCount++，從而和expectedModCount不相同
//直接進行報錯，不然容易出現迭代器的越界，游標錯位，遍歷不全等各種問題，
Itr() {}
//是否還有下一個元素
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
//后移
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;
//把當前元素遍歷出來，上一個操作元素位置lastRet可以賦值該位置
return (E) elementData[lastRet = i];
}
//洗掉當前元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
//快速失敗，檢查modCount是否變化
checkForComodification();
try {
//移除當前元素
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//快速失敗：判斷modCount是否改變
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
iterator弊端：
1、只能進行remove操作，add、clear 等 Itr 中沒有，
2、呼叫 remove 之前必須先呼叫 next，因為 remove 開始就對 lastRet 做了校驗，而 lastRet 初始化時為 -1，
3、next 之后只可以呼叫一次 remove，因為 remove 會將 lastRet 重新初始化為 -1
總結
ArrayList是非常常用的一種資料結構，這里也只是對ArrayLitt類中常用的方法進行總結，另外大家從上面原始碼也可以看出
1.Arraylist并非執行緒安全的，
2.大批量元素創建并插入ArryList中，初始化它的容量進行創建，比默認容量為10創建之后擴容插入的速度提高非常大，
好了，這次分享就到這里了，希望我的博客對大家在學習java方面有些許幫助·······
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/46644.html
標籤：AI
上一篇：搶紅包演算法（公平版和手速版）
下一篇：Java三種方法實作佇列