ArrayList源碼分析
前言
在之前的文章中我們提到過ArrayList,ArrayList可以說是每一個學java的人使用最多最熟練的集合了,但是知其然不知其是以然。關于ArrayList的具體實作,一些基本的都也知道,譬如數組實作,線程不安全等等,但是更加具體的就很少去了解了,例如:初始化的長度,擴容等。
本篇主要通過一些對源碼的分析,講解幾個ArrayList常見的方法,以及和Vector的差別。
ArrayList
定義
1 public class ArrayList<E> extends AbstractList<E>
2 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList實際上是一個動态數組,容量可以動态的增長,其繼承了AbstractList,實作了List, RandomAccess, Cloneable, java.io.Serializable這些接口。
RandomAccess接口,被List實作之後,為List提供了随機通路功能,也就是通過下标擷取元素對象的功能。
實作了Cloneable, java.io.Serializable意味着可以被克隆和序列化。
初始化
在使用中我們經常需要new出來各種泛型的ArrayList,那麼在初始化過程是怎樣的呢?
如下一行代碼,建立一個ArrayList對象
List<Person> list = new ArrayList<>();
我們來看源碼,是如何初始化的,找到構造方法
//無參構造方法
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
看到這些代碼的時候,我也是不解的,elementData和EMPTY_ELEMENTDATA是什麼啊?但是很明顯EMPTY_ELEMENTDATA是一個常量,追本溯源我們去看一下成員屬性。
//如果是無參構造方法建立對象的話,ArrayList的初始化長度為10,這是一個靜态常量
private static final int DEFAULT_CAPACITY = 10;
//在這裡可以看到我們不解的EMPTY_ELEMENTDATA實際上是一個空的對象數組
private static final Object[] EMPTY_ELEMENTDATA = {};
//儲存ArrayList資料的對象數組緩沖區 空的ArrayList的elementData = EMPTY_ELEMENTDATA 這就是為什麼說ArrayList底層是數組實作的了。elementData的初始容量為10,大小會根據ArrayList容量的增長而動态的增長。
private transient Object[] elementData;
//集合的長度
private int size;
執行完構造方法,如下圖
可以說ArrayList的作者真的是很貼心,連緩存都處理好了,多次new出來的新對象,都指向同一個引用。
添加方法add
add(E e)
/**
* Appends the specified element to the end of this list.
*/
//增加元素到集合的最後
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//因為++運算符的特點 先使用後運算 這裡實際上是
//elementData[size] = e
//size+1
elementData[size++] = e;
return true;
}
先不管ensureCapacityInternal的話,這個方法就是将一個元素增加到數組的size++位置上。
再說回ensureCapacityInternal,它是用來擴容的,準确說是用來進行擴容檢查的。下面我們來看一下整個擴容的過程
//初始長度是10,size預設值0,假定添加的是第一個元素,那麼minCapacity=1 這是最小容量 如果小于這個容量就會報錯
//如果底層數組就是預設數組,那麼選一個大的值,就是10
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//調用另一個方法ensureExplicitCapacity
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//記錄修改的次數
modCount++;
// overflow-conscious code
//如果傳過來的值大于初始長度 執行grow方法(參數為傳過來的值)擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//真正的擴容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新的容量是在原有的容量基礎上+50% 右移一位就是二分之一
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:
//這裡是重點 調用工具類Arrays的copyOf擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
//Arrays
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> 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;
}
add(int index, E element)
添加到指定的位置
public void add(int index, E element) {
//判斷索引是否越界,如果越界就會抛出下标越界異常
rangeCheckForAdd(index);
//擴容檢查
ensureCapacityInternal(size + 1); // Increments modCount!!
//将指定下标空出 具體作法就是index及其後的所有元素後移一位
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//将要添加元素指派到空出來的指定下标處
elementData[index] = element;
//長度加1
size++;
}
//判斷是否出現下标是否越界
private void rangeCheckForAdd(int index) {
//如果下标超過了集合的尺寸 或者 小于0就是越界
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
remove(int index)
ArrayList支援兩種删除元素的方式
- remove(int index) 按照下标删除 常用
- remove(Object o) 按照元素删除 會删除和參數比對的第一個元素
下面我們看一下ArrayList的實作
/**
移除list中指定位置的元素
* Removes the element at the specified position in this list.
所有後續元素左移 下标減1
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*參數是要移除元素的下标
* @param index the index of the element to be removed
傳回值是被移除的元素
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//下标越界檢查
rangeCheck(index);
//修改次數統計
modCount++;
//擷取這個下标上的值
E oldValue = elementData(index);
//計算出需要移動的元素個數 (因為需要将後續元素左移一位 此處計算出來的是後續元素的位數)
int numMoved = size - index - 1;
//如果這個值大于0 說明後續有元素需要左移 是0說明被移除的對象就是最後一位元素
if (numMoved > 0)
//索引index隻有的所有元素左移一位 覆寫掉index位置上的元素
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 将最後一個元素指派為null 這樣就可以被gc回收了
elementData[--size] = null; // clear to let GC do its work
//傳回index位置上的元素
return oldValue;
}
//移除特定元素
public boolean remove(Object o) {
//如果元素是null 周遊數組移除第一個null
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//周遊找到第一個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
}
ArrayList總結
- 底層數組實作,使用預設構造方法初始化出來的容量是10
- 擴容的長度是在原長度基礎上加二分之一
- 實作了RandomAccess接口,底層又是數組,get讀取元素性能很好
- 線程不安全,所有的方法均不是同步方法也沒有加鎖,是以多線程下慎用
- 順序添加很友善
- 删除和插入需要複制數組 性能很差(可以使用LinkindList)
為什麼ArrayList的elementData是用transient修飾的?
transient修飾的屬性意味着不會被序列化,也就是說在序列化ArrayList的時候,不序列化elementData。
為什麼要這麼做呢?
- elementData不總是滿的,每次都序列化,會浪費時間和空間
- 重寫了writeObject 保證序列化的時候雖然不序列化全部 但是有的元素都序列化
是以說不是不序列化 而是不全部序列化。
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 array length
s.writeInt(elementData.length);
// Write out all elements in the proper order.
for (int i=0; i<size; i++)
s.writeObject(elementData[i]);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
ArrayList和Vector的差別
标準答案
- ArrayList是線程不安全的,Vector是線程安全的
- 擴容時候ArrayList擴0.5倍,Vector擴1倍
那麼問題來了
ArrayList有沒有辦法線程安全?
Collections工具類有一個synchronizedList方法
可以把list變為線程安全的集合,但是意義不大,因為可以使用Vector
Vector為什麼是線程安全的?
老實講,抛開多線程 它倆差別沒多大,但是多線程下就不一樣了,那麼Vector是如何實作線程安全的,我們來看幾個關鍵方法
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
就代碼實作上來說,和ArrayList并沒有很多邏輯上的差別,但是在Vector的關鍵方法都使用了synchronized修飾。
我不能保證每一個地方都是對的,但是可以保證每一句話,每一行代碼都是經過推敲和斟酌的。希望每一篇文章背後都是自己追求純粹技術人生的态度。
永遠相信美好的事情即将發生。