當你停下來休息的時候,不要忘記,別人還在奔跑~
先拋出個問題：大家都知道ArrayList底層是由數(shù)組實現(xiàn)的，java中標準數(shù)組是定長的，在數(shù)組被創(chuàng)建之后奥裸，它們不能被加長或縮短概作。這就意味著在創(chuàng)建數(shù)組時需要知道數(shù)組的所需長度，為什么ArrayList可以動態(tài)擴容艇抠？
1. ArrayList 的構(gòu)造函數(shù)
/**
* 默認初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*默認構(gòu)造函數(shù)幕庐，構(gòu)造一個空數(shù)組(無參數(shù)構(gòu)造)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 帶初始容量參數(shù)的構(gòu)造函數(shù)。（用戶自己指定容量）
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {//初始容量大于0
//創(chuàng)建initialCapacity大小的數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {//初始容量等于0
//創(chuàng)建空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
} else {//初始容量小于0家淤，拋出異常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*構(gòu)造包含指定collection元素的列表异剥，這些元素利用該集合的迭代器按順序返回
*如果指定的集合為null，throws NullPointerException絮重。
*/
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;
}
}
2.ArrayList 擴容機制
List擴容實現(xiàn)步驟届吁，總的來說就是分兩步：
-
擴容
把原來的數(shù)組復制到另一個內(nèi)存空間更大的數(shù)組中 -
添加元素
把新元素添加到擴容以后的數(shù)組中
2.1 假設(shè)使用默認無參構(gòu)造函數(shù)，即初始數(shù)組元素個數(shù)為0（size=0）
/**
*默認構(gòu)造函數(shù)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.2add方法
/**
* 將指定的元素追加到此列表的末尾绿鸣。
*/
public boolean add(E e) {
//添加元素之前疚沐，先調(diào)用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
//這里看到ArrayList添加元素的實質(zhì)就相當于為數(shù)組賦值
elementData[size++] = e;
return true;
}
可以看到以無參數(shù)構(gòu)造方法創(chuàng)建 ArrayList 時，實際上初始化賦值的是一個空數(shù)組潮模。當真正對數(shù)組進行添加元素操作時亮蛔，才真正分配容量。
2.3 可以看到 add 方法 首先調(diào)用了ensureCapacityInternal(size + 1)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//得到最小擴容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 獲取默認的容量和傳入?yún)?shù)的較大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
當 要 add 進第1個元素時擎厢，minCapacity為1究流，在Math.max()方法比較后辣吃，minCapacity 為10。
2.4 ensureExplicitCapacity()方法
// 確保是否需要擴容
private void ensureExplicitCapacity(int minCapacity) {
// 記錄被修改的次數(shù)
modCount++;
// 最小擴容單位長度大于數(shù)組長度芬探，表示需要擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
2.5 grow() 方法 （核心）
/**
* 要分配的最大數(shù)組大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList擴容的核心方法神得。
*/
private void grow(int minCapacity) {
// oldCapacity為舊容量，newCapacity為新容量
int oldCapacity = elementData.length;
//將oldCapacity 右移一位偷仿，其效果相當于oldCapacity /2哩簿，
//結(jié)果就是將新容量更新為舊容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//若新容量還是小于最小需要容量酝静，那么就把最小需要容量（10）當作數(shù)組的新容量节榜，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,進入(執(zhí)行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE，
//如果minCapacity大于最大容量别智，則新容量則為`Integer.MAX_VALUE`宗苍，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`薄榛。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 將原數(shù)組copy到新數(shù)組中
elementData = Arrays.copyOf(elementData, newCapacity);
}
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次擴容之后容量都會變?yōu)樵瓉淼?1.5 倍左右（oldCapacity為偶數(shù)就是1.5倍讳窟，否則是1.5倍左右）！ 奇偶不同敞恋，比如 ：10+10/2 = 15, 33+33/2=49挪钓。如果是奇數(shù)的話會丟掉小數(shù).
">>"（移位運算符）：>>1 右移一位相當于除2，右移n位相當于除以 2 的 n 次方耳舅。這里 oldCapacity 明顯右移了1位所以相當于oldCapacity /2碌上。對于大數(shù)據(jù)的2進制運算,位移運算符比那些普通運算符的運算要快很多,因為程序僅僅移動一下而已,不去計算,這樣提高了效率,節(jié)省了資源
2.6 .hugeCapacity() 方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//對minCapacity和MAX_ARRAY_SIZE進行比較
//若minCapacity大，將Integer.MAX_VALUE作為新數(shù)組的大小
//若MAX_ARRAY_SIZE大浦徊，將MAX_ARRAY_SIZE作為新數(shù)組的大小
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
總結(jié)
- 當我們要 add 進第1個元素到 ArrayList 時馏予，elementData.length 為0 （因為還是一個空的數(shù)組），因為執(zhí)行了 ensureCapacityInternal() 方法 盔性，所以 minCapacity 此時為10霞丧。此時，minCapacity - elementData.length > 0 成立冕香，所以會進入 grow(minCapacity) 方法蛹尝。
- 當add第2個元素時，minCapacity 為2悉尾，此時e lementData.length(容量)在添加第一個元素后擴容成 10 了突那。此時，minCapacity - elementData.length > 0 不成立构眯，所以不會進入 （執(zhí)行）grow(minCapacity) 方法愕难。
- 添加第3、4···到第10個元素時，依然不會執(zhí)行g(shù)row方法猫缭，數(shù)組容量都為10葱弟。
直到添加第11個元素，minCapacity(為11)比elementData.length（為10）要大猜丹。進入grow方法進行擴容芝加。 - 把新元素添加到擴容以后的數(shù)組中。
