面試必會之ArrayList原始碼分析以及手寫ArrayList
簡介
ArrayList是我們開發中非常常用的資料儲存容器之一,其底層是陣列實現的,我們可以在集合中儲存任意型別的資料,ArrayList是執行緒不安全的,非常適合用於對元素進行查詢,效率非常高。
執行緒安全性
對ArrayList的操作一般分為兩個步驟,改變位置(size)和操作元素(e)。所以這個過程在多執行緒的環境下是不能保證具有原子性的,因此ArrayList在多執行緒的環境下是執行緒不安全的。
原始碼分析
1. 屬性分析
/** * 預設初始化容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 如果自定義容量為0,則會預設用它來初始化ArrayList。或者用於空陣列替換。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 如果沒有自定義容量,則會使用它來初始化ArrayList。或者用於空陣列比對。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 這就是ArrayList底層用到的陣列 * 非私有,以簡化巢狀類訪問 * transient 在已經實現序列化的類中,不允許某變數序列化 */ transient Object[] elementData; /** * 實際ArrayList集合大小 */ private int size; /** * 可分配的最大容量 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 複製程式碼
擴充套件:什麼是序列化
序列化是指:將物件轉換成以位元組序列的形式來表示,以便用於持久化和傳輸。
實現方法:實現Serializable介面。
然後用的時候拿出來進行反序列化即可又變成Java物件。
transient關鍵字解析
Java中transient關鍵字的作用,簡單地說,就是讓某些被修飾的成員屬性變數不被序列化。
有了 transient
關鍵字宣告,則這個變數不會參與序列化操作,即使所在類實現了Serializable介面,反序列化後該變數為空值。
那麼問題來了:ArrayList中陣列宣告: transient Object[] elementData;
,事實上我們使用ArrayList在網路傳輸用的很正常,並沒有出現空值。
原來: ArrayList
在序列化的時候會呼叫 writeObject()
方法,將 size
和 element
寫入 ObjectOutputStream
;反序列化時呼叫 readObject()
,從 ObjectInputStream
獲取 size
和 element
,再恢復到 elementData
。
那為什麼不直接用elementData來序列化,而採用上訴的方式來實現序列化呢?
原因在於 elementData
是一個快取陣列,它通常會預留一些容量,等容量不足時再擴充容量,那麼有些空間可能就沒有實際儲存元素,採用上訴的方式來實現序列化時,就可以保證只序列化實際儲存的那些元素,而不是整個陣列,從而 節省空間和時間 。
2. 構造方法分析
根據initialCapacity 初始化一個空陣列,如果值為0,則初始化一個空陣列:
/** * 根據initialCapacity 初始化一個空陣列 */ 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); } } 複製程式碼
不帶引數初始化,預設容量為10:
/** * 不帶引數初始化,預設容量為10 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } 複製程式碼
通過集合做引數的形式初始化:如果集合為空,則初始化為空陣列:
/** * 通過集合做引數的形式初始化 */ 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; } } 複製程式碼
3. 主幹方法
trimToSize()方法:
用來最小化例項儲存,將容器大小調整為當前元素所佔用的容量大小。
/** * 這個方法用來最小化例項儲存。 */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }複製程式碼
clone()方法
用來克隆出一個新陣列。
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.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); } } 複製程式碼
通過呼叫 Object
的 clone()
方法來得到一個新的 ArrayList
物件,然後將 elementData
複製給該物件並返回。
add(E e)方法
在陣列末尾新增元素
/** * 在陣列末尾新增元素 */ public boolean add(E e) { ensureCapacityInternal(size + 1);// Increments modCount!! elementData[size++] = e; return true; } 複製程式碼
看到它首先呼叫了 ensureCapacityInternal()
方法.注意引數是size+1,這是個面試考點。
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } 複製程式碼
這個方法裡又巢狀呼叫了兩個方法:計算容量+確保容量
計算容量:如果elementData是空,則返回預設容量10和size+1的最大值,否則返回size+1
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } 複製程式碼
計算完容量後,進行確保容量可用:(modCount不用理它,它用來計算修改次數)
如果 size+1 > elementData.length
證明陣列已經放滿,則增加容量,呼叫 grow()
。
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } 複製程式碼
增加容量:預設1.5倍擴容。
- 獲取當前陣列長度=>oldCapacity
- oldCapacity>>1 表示將oldCapacity右移一位(位運算),相當於除2。再加上1,相當於新容量擴容1.5倍。
- 如果
newCapacity<minCapacity
,則newCapacity = minCapacity
。看例子更明白一點:假設size為1,則minCapacity=size+1=2
,而elementData.length=1
,newCapacity=1+1>>1=1
,1<2
所以如果不處理該情況,擴容將不能正確完成。 - 如果新容量比最大值還要大,則將新容量賦值為VM要求最大值。
- 將elementData拷貝到一個新的容量中。
private void grow(int minCapacity) { // overflow-conscious code 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); }複製程式碼
size+1的問題
好了,那到這裡可以說一下為什麼要size+1。
size+1代表的含義是:
- 如果集合新增元素成功後,集合中的實際元素個數。
- 為了確保擴容不會出現錯誤。
假如不加一處理,如果預設size是0,則0+0>>1還是0。
如果size是1,則1+1>>1還是1。有人問:不是預設容量大小是10嗎?事實上,jdk1.8版本以後,ArrayList的擴容放在add()方法中。之前放在構造方法中。我用的是1.8版本,所以預設 ArrayList arrayList = new ArrayList();
後,size應該是0.所以,size+1對擴容來講很必要.
public static void main(String[] args) { ArrayList arrayList = new ArrayList(); System.out.println(arrayList.size()); } 輸出:0 複製程式碼
事實上上面的程式碼是證明不了容量大小的,因為size只會在呼叫 add()
方法時才會自增。有辦法的小夥伴可以在評論區大顯神通。
add(int index, E element)方法
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1);// Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } 複製程式碼
rangeCheckForAdd()是越界異常檢測方法。 ensureCapacityInternal()
之前有講,著重說一下 System.arrayCopy
方法:
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 程式碼解釋: Object src : 原陣列 int srcPos : 從元資料的起始位置開始 Object dest : 目標陣列 int destPos : 目標陣列的開始起始位置 int length: 要copy的陣列的長度 複製程式碼
示例:size為6,我們呼叫 add(2,element)
方法,則會從index= 2+1=3
的位置開始,將陣列元素替換為從index起始位置為 index=2
,長度為 6-2=4
的資料。
異常處理:
private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }複製程式碼
set(int index,E element)方法
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } E elementData(int index) { return (E) elementData[index]; } 複製程式碼
邏輯很簡單,覆蓋舊值並返回。
indexOf(Object o)方法
根據Object物件獲取陣列中的索引值。
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; } 複製程式碼
如果o為空,則返回陣列中第一個為空的索引;不為空也類似。
注意:通過原始碼可以看到,該方法是允許傳空值進來的。
get(int index)方法
返回指定下標處的元素的值。
public E get(int index) { rangeCheck(index); return elementData(index); } 複製程式碼
rangeCheck(index)
會檢測index值是否合法,如果合法則返回索引對應的值。
remove(int index)方法
刪除指定下標的元素。
public E remove(int index) { // 檢測index是否合法 rangeCheck(index); // 資料結構修改次數 modCount++; E oldValue = elementData(index); // 記住這個演算法 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; } 複製程式碼
這裡又碰到了 System.arraycopy()
方法,詳情請查閱上文。
大概思路:將該元素後面的元素前移,最後一個元素置空。
ArrayList優缺點
優點:
- 因為其底層是陣列,所以修改和查詢效率高。
- 可自動擴容(1.5倍)。
缺點:
- 插入和刪除效率不高。
- 執行緒不安全。
手寫ArrayList
那面試手寫ArrayList應該就不是問題了。
下面貼出我手寫的一個簡單閹割版的ArrayList:
public class MyArrayList { // 非私有,以簡化巢狀類訪問 // transient 在已經實現序列化的類中,不允許某變數序列化 transient Object[] elementData; //預設容量 private static final int DEFAULT_CAPACITY = 10; // 用於空例項的 空陣列例項 private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 實際ArrayList集合大小 private int size; /** * 構造方法 */ public MyArrayList(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 MyArrayList(){ this(DEFAULT_CAPACITY); } public void add(Object o){ //1. 判斷資料容量是否大於 elementData ensureExplicitCapacity(size+1); //2. 使用下標進行賦值 elementData[size++] = o; } private void ensureExplicitCapacity(int minCapacity){ if (size == elementData.length){ // 需要擴容,擴容1.5倍(ArrayList預設擴容1.5倍) // 注意:如果oldCapacity值為1 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新容量 < 最小容量, 則將最小容量賦值給新容量 // 如果 oldCapacity=1, 則 minCapacity=1+1=2newCapacity=1+(1>>1)=1 if (newCapacity - minCapacity < 0){ newCapacity = minCapacity; } // 建立新陣列 Object[] objects = new Object[newCapacity]; // 將資料複製給新陣列 System.arraycopy(elementData, 0, objects, 0, elementData.length); // 修改引用 elementData = objects; } } public Object get(int index) { rangeCheck(index); return elementData[index]; } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException("下標越界"); } /** * 通過下標刪除 * @param index * @return */ public Object remove(int index) { rangeCheck(index); //modCount++; // 先查出元素 Object oldValue = elementData[index]; // 找出置換結束位置 int numMoved = size - index - 1; if (numMoved > 0) // 從 index+1 開始 將值覆蓋為 index-numMoved 的值 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) { for (int index = 0; index < size; index++){ if (o.equals(elementData[index])) { remove(index); return true; } } return false; } }複製程式碼
最後
大家覺得不錯可以 點個贊在關注下,以後還會分享更多文章!