Java中的ArrayList容量及擴容方式
查看JDK1.8 ArrayList的源代碼
1、默認初始容量為10
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;
2、最大容量為 Integer.MAX_VALUE – 8
/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
原因:之前參考別人的,有待求證:
數組對象有一個額外的元數據,用於表示數組的大小;
數組長度size為int類型,共32位,有一位符號位,所以最大長度為Integer.MAX_VALUE=2^31= 2,147,483,648;
8bytes用來存儲size;
3、擴容方式:
(1)首先傳遞進來一個希望的最小容量minCapacity;
(2)新容量newCapacity = oldCapacity + (oldCapacity >> 1),即新容量等於原容量的1.5倍;
(3)如果minCapacity > newCapacity ,newCapacity = minCapacity ;
(4)如果 newCapacity > 最大容量 MAX_ARRAY_SIZE ,newCapacity = hugeCapacity(minCapacity);
(5)以新容量拷貝原數據
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ 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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
Java ArrayList() 擴容原理
平常都是直接使用 ArrayList(),今天特地看一下 ArrayList() 的擴容原理。
先看下 ArrayList 的屬性以及構造方法,這個比較重要
先看下屬性
// ArrayList 默認容量大小 private static final int DEFAULT_CAPACITY = 10; // 一個共享的空數組, 在空實例時使用 private static final Object[] EMPTY_ELEMENTDATA = {}; // 一個共享的空數組, 在使用默認 size 的空實例時使用 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /* 存儲 ArrayList 元素的數組緩沖區 重點1: ArrayList 的容量是數組緩沖區的長度 重點2: 從這個元素也可以看的出來 ArrayList() 的底層就是一個 Object[] add 第一個元素時, 任何帶有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都將被擴展為 DEFAULT_CAPACITY */ transient Object[] elementData; // ArrayList 的大小, 我們平常使用的 list.size() 底層就是記錄的這個 size private int size; // ArrayList 最大 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
再看構造器,帶參構造器
/* 帶參構造器, 參數為容量大小, 例如: 初始化一個容器為 20 類型為 Integer 的 ArrayList ArrayList<Integer> list = new ArrayList<>(20); */ public ArrayList(int initialCapacity) { /* 初始化容量 > 0, elementData 初始化為初始化容量大小的數組 初始化容量 = 0, elementData = EMPTY_ELEMENTDATA (空數組) 初始化容量 < 0, 直接拋出異常 */ if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
參數為 Collection 的構造器
/* 將一個參數為 Collection 的集合轉換為 ArrayList */ public ArrayList(Collection<? extends E> c) { // Collection 轉換為數組 Object[] 類型 elementData = c.toArray(); // 判斷當前對象大小是否和 Collection 長度相等並且不等於 0, false 的話 elementData 等於空數組瞭 if ((size = elementData.length) != 0) { // c.toArray() 可能不會正確地返回一個 Object[] 數組,所以使用 Arrays.copyOf() if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; } }
不帶參構造器
/* 不帶參構造器就像我們平時使用一樣, 直接 new 一個 ArrayList 不需要傳遞任何參數 構造方法中直接將 elementData 初始化為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA (空數組) */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
看到這裡就發現,帶參的構造器我們可以直接傳遞參數,而默認的構造器怎麼怎麼樣初始化容量大小的呢?
add() 方法可以直接得到答案。
public boolean add(E e) { // 這一行是關鍵, 看下面 ensureCapacityInternal(size + 1); // 將元素追加到集合的末尾 假如當前 size = 10 size++ 追加到第 11 位 elementData[size++] = e; return true; }
ensureCapacityInternal() 方法調用
private void ensureCapacityInternal(int minCapacity) { /* calculateCapacity() 方法, 剛初始化時會返回 10, 其他情況返回當前 size + 1 ensureExplicitCapacity() 方法, 調用擴容 */ ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { /* 使用無參構造器創建創建 ArrayList 的集合, 此時一定是相等的 */ if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { /* 兩數相比返回最大值, 此時 Math.max(10, 1); 默認容量, 由此而來 */ return Math.max(DEFAULT_CAPACITY, minCapacity); } // 不相等的話隻有返回當前的 size + 1 return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { // 增量, 記錄修改/更新次數 modCount++; // 初始化: 10 - 0 > 0 // 其他: size + 1 > 0 if (minCapacity - elementData.length > 0) // 擴容操作 grow(minCapacity); } private void grow(int minCapacity) { // 老的長度, 初始化時為 0, int oldCapacity = elementData.length; // 新的長度此時 0 + (0 >> 1), newCapacity = 0 int newCapacity = oldCapacity + (oldCapacity >> 1); // 初始化場景: 0 - 10 < 0 ? true newCapacity = 10 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 初始化場景: 10 - 2147483639 > 0 返回 false if (newCapacity - MAX_ARRAY_SIZE > 0) // 超大長度才可以執行這個方法, 必須大於 MAX_ARRAY_SIZE 一般不會 newCapacity = hugeCapacity(minCapacity); // 復制原數組中的元素, 並擴容 elementData = Arrays.copyOf(elementData, newCapacity); }
上看說的是初始化場景,下面看一下其他場景,也是相當簡單
private void ensureCapacityInternal(int minCapacity) { /* calculateCapacity() 方法, 正常擴容返回 size + 1, 比如 10 + 1, 因為默認長度為 10 當再次新增數據時就會出發擴容 ensureExplicitCapacity() 方法, 調用擴容 */ ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } /* elementData 不等於空數組 返回當前的 size + 1, 即 10 + 1 返回 11 */ return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { // 增量, 記錄修改/更新次數 modCount++; // 其他: 11 - 10 > 0 true, 觸發擴容, 如果當前下表是 5 的話 5 + 1 =6, 6 < 10 是, 此時不會出發擴容 if (minCapacity - elementData.length > 0) // 擴容操作 grow(minCapacity); } private void grow(int minCapacity) { // 老的長度 10 int oldCapacity = elementData.length; // 新的長度此時 10 + (10 >> 1), newCapacity = 15 int newCapacity = oldCapacity + (oldCapacity >> 1); // 15 - 11 < 0 ? false if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 15 - 2147483639 > 0 返回 false if (newCapacity - MAX_ARRAY_SIZE > 0) // 超大長度才可以執行這個方法, 必須大於 MAX_ARRAY_SIZE 一般不會 newCapacity = hugeCapacity(minCapacity); // 復制原數組中的元素, 並擴容 newCapacity = 15 elementData = Arrays.copyOf(elementData, newCapacity); }
結論
1、 觸發擴容的關鍵是
當前 size + 1 是否大於當前容量,如果大於容量則證明,集合不夠用瞭,需要擴容。如果小與當前容量則證明集合還有容量不需要擴容!
2、 每次擴容的大小是
oldCapacity + (oldCapacity >> 1) 即: 10 + (10 >> 1)
即:當前容量的 1.5 倍!
以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。
推薦閱讀:
- JDK1.8中ArrayList是如何擴容的
- 關於ArrayList的動態擴容機制解讀
- java中List接口與實現類介紹
- java中ArrayList和LinkedList的區別詳解
- Java中Arraylist的最大長度