ArrayList的類定義

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable{

實(shí)現(xiàn) List 接口，繼承了 AbstractList 抽象類，這個是很好理解的，ArrayList作為List集合類家族的一部分，可以更好的將公用方法抽象給上層

實(shí)現(xiàn)Cloneable和Serializable接口?，可以進(jìn)行克隆和序列化操作

實(shí)現(xiàn)RandomAccess接口，這個接口會相對陌生點(diǎn)，點(diǎn)進(jìn)去官方給的解釋是，RandomAccess是一個標(biāo)記接口，是一個空接口，僅起到標(biāo)記的作用(類似Serializable接口)

public interface RandomAccess {}

List實(shí)現(xiàn)這個接口表明這個類能實(shí)現(xiàn)?快速隨機(jī)訪問。該接口的主要目的是允許通用算法更改其行為，以便在應(yīng)用于隨機(jī)訪問或順序訪問列表時提供良好的性能

而后文檔里給了說明，如果實(shí)現(xiàn)了RandomAccess接口，對List做查詢操作時使用for循環(huán)的方式，否則使用迭代器的方式。這樣做的原因做了RandomAccess接口標(biāo)記的LIst實(shí)現(xiàn)類底層數(shù)據(jù)結(jié)構(gòu)使用for循環(huán)效率更高(比如ArrayList)，沒有RandomAccess接口標(biāo)記的使用迭代器效率更高(比如LinkedList，下文可以看到LinkedList沒有實(shí)現(xiàn)RandomAccess接口)

舉個簡單的小例子，比如Collections類里的二分查找方法，就是用是否標(biāo)記了RandomAccess接口來區(qū)分用哪種方法實(shí)現(xiàn)的：

public static int binarySearch(List extends Comparable super T>> list, T key) { if (list instanceof RandomAccess || list.size() return Collections.indexedBinarySearch(list, key); // for循環(huán)方法 else return Collections.iteratorBinarySearch(list, key); // Iterator循環(huán)方法}

ArrayList構(gòu)造函數(shù)

public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList實(shí)現(xiàn)了三種構(gòu)造函數(shù)用于不同情形下的對象創(chuàng)建

a. 無參構(gòu)造了一個空數(shù)組，在首次添加元素的時候才給數(shù)據(jù)設(shè)置大小的構(gòu)造函數(shù)

b.?給定初始容量的構(gòu)造函數(shù),通過參數(shù) initialCapacity 可設(shè)置List數(shù)組的初始大小，這樣做的好處是當(dāng) ArrayList 新增元素時，如果所存儲的元素已經(jīng)超過其已有大小，它會計(jì)算元素大小后再進(jìn)行動態(tài)擴(kuò)容，數(shù)組的擴(kuò)容會導(dǎo)致整個數(shù)組進(jìn)行一次內(nèi)存復(fù)制。因此，我們在初始化 ArrayList 時，可以通過第一個構(gòu)造函數(shù)合理指定數(shù)組初始大小，這樣有助于減少數(shù)組的擴(kuò)容次數(shù)，從而提高系統(tǒng)性能

public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // initialCapacity大于0，數(shù)組的大小為initialCapacity值 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // initialCapacity等于0，生成默認(rèn)空數(shù)組EMPTY_ELEMENTDATA this.elementData = EMPTY_ELEMENTDATA; } else { // 其他情況，報非法參數(shù)異常-》數(shù)組的大小必須大于等于0 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}

c.傳入Collection對象轉(zhuǎn)化成ArrayList,將 Collection 轉(zhuǎn)化為數(shù)組并賦值給 elementData，把 elementData 中元素的個數(shù)賦值給 size。如果 size 不為零，則判斷 elementData 的 class 類型是否為 Object[]，不是的話則做一次轉(zhuǎn)換。如果 size 為零，則把 EMPTY_ELEMENTDATA 賦值給 elementData，相當(dāng)于new ArrayList(0)

public ArrayList(Collection extends E> c) { Object[] a = c.toArray(); if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. elementData = EMPTY_ELEMENTDATA; }}

ArrayList屬性

transient Object[] elementData; // non-private to simplify nested class accessprivate static final int DEFAULT_CAPACITY = 10;private int size;

elementData?：底層數(shù)組，用來存儲數(shù)據(jù)

DEFAULT_CAPACITY?：數(shù)組的默認(rèn)初始化容量 10

size?：當(dāng)前的數(shù)組大小，用來表示當(dāng)前數(shù)組包含了多少個元素

ArrayList新增元素

/** * 直接將元素添加到數(shù)組尾部 */public boolean add(E e) { // 1.判斷當(dāng)前數(shù)組容量是否夠用，不夠的話進(jìn)行數(shù)組擴(kuò)容操作 ensureCapacityInternal(size + 1); // Increments modCount!! // 2.將元素添加到數(shù)組尾部，size加1 elementData[size++] = e; return true;}/** * 將元素添加到指定位置 */public void add(int index, E element) { // 1.判斷指定位置是否在數(shù)組包含范圍內(nèi) rangeCheckForAdd(index); // 2.判斷當(dāng)前數(shù)組容量是否夠用，不夠的話進(jìn)行數(shù)組擴(kuò)容操作 ensureCapacityInternal(size + 1); // Increments modCount!! // 3.將指定位置開始的元素向后挪動一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 4.將元素添加到指定位置上 elementData[index] = element; size++;}

ArrayList提供了兩種添加元素的方法，第一種：直接將元素添加到數(shù)組尾部；第二種：將元素添加到指定位置

從代碼里可以看出，兩種添加方式都執(zhí)行了 ensureCapacityInternal 方法，判斷數(shù)組的容量情況，具體看下這個方法是如何實(shí)現(xiàn)的呢：

判斷當(dāng)前數(shù)組是否是空數(shù)組EMPTY_ELEMENTDATA，如果是的話，判斷默認(rèn)值(10)和傳入的容量(size+1)誰大，就返回哪個，如果不是空數(shù)組的話，直接返回(size+1)，這一步是對初始化為空數(shù)組的情況進(jìn)行特殊處理

判斷傳入容量(size+1)是否大于當(dāng)前的數(shù)組大小，如果是的話進(jìn)行擴(kuò)容操作(grow)

擴(kuò)容操作是將容量擴(kuò)充到原始容量的1.5倍大小，如果還是不夠，就將容量給定為當(dāng)前傳入的容量(size+1)

這里需要判斷下是否有內(nèi)存溢出的問題，當(dāng)容量達(dá)到允許的最大值(MAX_ARRAY_SIZE)的時候，將數(shù)組容量給定為int最大值

擴(kuò)容后需要將原數(shù)組重新分配到新的內(nèi)存地址中

/** * 計(jì)算數(shù)組容量，從傳入的容量和默認(rèn)容量(10)里面去較大的 */private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;}/** * 計(jì)算數(shù)組容量，從傳入的容量和默認(rèn)容量(10)里面去較大的 */private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}/** * 計(jì)算數(shù)組容量，如果傳入容量比當(dāng)前數(shù)組已有元素?cái)?shù)量小，需要進(jìn)行擴(kuò)容操作 */private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);}/** * 數(shù)組擴(kuò)容 */private void grow(int minCapacity) { // 計(jì)算擴(kuò)容后的數(shù)組容量 // overflow-conscious code int oldCapacity = elementData.length; // 擴(kuò)容后新的容量是原容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 將原數(shù)組的元素復(fù)制到新數(shù)組上 // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);}/** * 數(shù)據(jù)容量大小邊界處理 */private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}/** * 數(shù)據(jù)允許的最大容量 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

從代碼里可以看到，添加元素到任意位置，會導(dǎo)致在該位置后的所有元素都需要重新排列，而將元素添加到數(shù)組的末尾，在沒有發(fā)生擴(kuò)容的前提下，是不會有元素復(fù)制排序過程的。所以直接將元素添加的數(shù)組的末尾效率會更高

ArrayList查找元素

public E get(int index) { // 檢查index是否越界， rangeCheck(index); // 返回?cái)?shù)組對應(yīng)下標(biāo)元素值 return elementData(index);}private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}@SuppressWarnings("unchecked")E elementData(int index) { return (E) elementData[index];}

ArrayList在數(shù)據(jù)查找上的效率很高，只需要O(1)的時間復(fù)雜度就能獲取數(shù)據(jù)，傳入需要元素的下標(biāo)index，返回?cái)?shù)據(jù)中的對應(yīng)元素即可

ArrayList刪除元素

public E remove(int 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;}

ArrayList刪除元素的代碼邏輯和添加元素到任意位置的方法類似，在每一次有效的刪除元素操作之后，都要進(jìn)行數(shù)組的重組，并且刪除的元素位置越靠前，數(shù)組重組的開銷就越大

判斷index是否合法(有沒有下標(biāo)越界)

獲取要刪除的元素

將要刪除數(shù)據(jù)下標(biāo)往后的元素向前移動一位

將最后一位置零

返回被刪除的元素

今天的分享就到這里，一起學(xué)技術(shù)，一起在生活中探險～歡迎關(guān)注【小肖愛吃肉】

總結(jié)

以上是生活随笔為你收集整理的arraylist是如何扩容的?_ArrayList的源码分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。