初始化
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient 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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
初始化目的是為了初始化底層的elementData材义，但是無參構(gòu)造會將elementData初始化為一個空數(shù)組蠕蚜，當插入梢灭，擴容會按默認值重新初始化數(shù)組，有參數(shù)構(gòu)造幕侠，則會根據(jù)次參數(shù)來構(gòu)造數(shù)組帝美，這樣的做法顯然是為了按需分配避免浪費
插入
/** 在元素序列尾部插入 */
public boolean add(E e) {
// 1. 檢測是否需要擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 將新元素插入序列尾部
elementData[size++] = e;
return true;
}
/** 在元素序列 index 位置處插入 */
public void add(int index, E element) {
rangeCheckForAdd(index);
// 1. 檢測是否需要擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 將 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 將新元素插入至 index 處
elementData[index] = element;
size++;
}
- 直接插入（默認插入到尾部）
- 檢查數(shù)組是否有足夠的空間
-
將新元素插入至尾部
image
- 指定位置插入
- 檢測是不是有足夠的空間
- 將index及其后面的所有元素退因為
- 將新元素插入
image
注意 可以看到這個操作時間復(fù)雜度為O（N），平凡的一定元素坑定為導(dǎo)致效率的問題晤硕，所以日常開發(fā)中最好別用特別是元素較多的時候
擴容
接下來就講講擴容吧
擴容的入口：
ensureCapacityInternal 就是擴容的入口悼潭，在插入前我們得檢查是否需要擴容從而得到了他庇忌。
/** 擴容的入口方法 */
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/** 計算最小容量 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/** 擴容的核心方法 */
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果最小容量超過 MAX_ARRAY_SIZE，則將數(shù)組容量擴容至 Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
em....比較簡單就不講了女责，最關(guān)鍵查看到put時會查看這個時候其表elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA如果是漆枚，才開始初始化數(shù)組。
刪除
因為刪除沒有無參的方法抵知，所以難以避免的就是造成了元素的移動墙基。
/** 刪除指定位置的元素 */
public E remove(int index) {
rangeCheck(index);
modCount++;
// 返回被刪除的元素值
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 將 index + 1 及之后的元素向前移動一位，覆蓋被刪除值
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 將最后一個元素置空刷喜，并將 size 值減1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
/** 刪除指定元素残制，若元素重復(fù)，則只刪除下標最小的元素 */
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍歷數(shù)組掖疮，查找要刪除元素的位置
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
}
先來看根據(jù)index判斷是不是要進行刪除浊闪。
- 獲取索引位置的元素值
- 將index+1之后的的元素向前移動一位
- 最后將最后一個元素置空恼布，size也減去一個1
- 然后 返回被刪除的值。
如果是對象
- 判斷是不是傳入對象是不是為空搁宾，如果是就調(diào)用fastRemove刪除value為空的
-
如果不是就刪除折汞，就遍歷找到最小的所以同樣調(diào)用fastRemove進行刪除。
image
縮容
因為Arraylist的變化超大盖腿，擴容后刪除會產(chǎn)生大量空閑空間爽待，這個時候就需要鎖絨了
/** 將數(shù)組容量縮小至元素數(shù)量 */
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
image
遍歷
快速失敗機制
當遇到并發(fā)修改的時候，的迭代器會快速失敗翩腐，拋出異常ConcurrentModificationException鸟款。
關(guān)于遍歷時刪除
這個得注意，阿里巴巴 Java 開發(fā)手冊里也有所提及茂卦。這里引用一下：
【強制】不要在 foreach 循環(huán)里進行元素的 remove/add 操作何什。remove 元素請使用 Iterator 方式，如果并發(fā)操作等龙，需要對 Iterator 對象加鎖处渣。
List<String> a = new ArrayList<String>();
a.add("1");
a.add("2");
for (String temp : a) {
System.out.println(temp);
if("1".equals(temp)){
a.remove(temp);
}
}
}
eg代碼：執(zhí)行的邏輯看不出來問題，因為問題“隱藏”得比較深而咆，我們把次打印到控制臺發(fā)下只有1沒有2霍比，為啥捏
先來看看轉(zhuǎn)換的另外一個代碼吧：
List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){
a.remove(temp);
}
}
這個時候幕袱，我們再去分析一下 ArrayList 的迭代器源碼就能找出原因暴备。
