ArrayList 簡(jiǎn)介
ArrayList 的底層是數(shù)組隊(duì)列，相當(dāng)于動(dòng)態(tài)數(shù)組。與 Java 中的數(shù)組相比，它的容量能動(dòng)態(tài)增長(zhǎng)。在添加大量元素前，應(yīng)用程序可以使用ensureCapacity操作來(lái)增加 ArrayList 實(shí)例的容量。這可以減少遞增式再分配的數(shù)量。
ArrayList繼承于 AbstractList，實(shí)現(xiàn)了 List, RandomAccess, Cloneable, java.io.Serializable 這些接口。
image-20201015193404305
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
-
RandomAccess是一個(gè)標(biāo)志接口(空接口)，表明實(shí)現(xiàn)這個(gè)這個(gè)接口的 List 集合是支持快速隨機(jī)訪(fǎng)問(wèn)的。在ArrayList中，我們即可以通過(guò)元素的序號(hào)快速獲取元素對(duì)象，這就是快速隨機(jī)訪(fǎng)問(wèn)。(原因是：底層是使用Object[]數(shù)組存儲(chǔ)數(shù)據(jù)的) -
ArrayList實(shí)現(xiàn)了Cloneable接口 ，即覆蓋了函數(shù)clone()，能被克隆。 -
ArrayList實(shí)現(xiàn)了java.io.Serializable接口，這意味著ArrayList支持序列化，能通過(guò)序列化去傳輸。
ArrayList 核心源碼解讀
<mark>JDK1.8版本</mark>
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默認(rèn)初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空數(shù)組（用于空實(shí)例）。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默認(rèn)大小空實(shí)例的共享空數(shù)組實(shí)例。
//我們把它從EMPTY_ELEMENTDATA數(shù)組中區(qū)分出來(lái)，以知道在添加第一個(gè)元素時(shí)容量需要增加多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList數(shù)據(jù)的數(shù)組
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList 所包含的元素個(gè)數(shù)
*/
private int size;
/**
* 帶初始容量參數(shù)的構(gòu)造函數(shù)（用戶(hù)可以在創(chuàng)建ArrayList對(duì)象時(shí)自己指定集合的初始大?。? */
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果傳入的參數(shù)大于0，創(chuàng)建initialCapacity大小的數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果傳入的參數(shù)等于0，創(chuàng)建空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
} else {
//其他情況，拋出異常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*默認(rèn)無(wú)參構(gòu)造函數(shù)
*DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為0.初始化為10，也就是說(shuō)初始其實(shí)是空數(shù)組 當(dāng)添加第一個(gè)元素的時(shí)候數(shù)組容量才變成10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 構(gòu)造一個(gè)包含指定集合的元素的列表，按照它們由集合的迭代器返回的順序。
*/
public ArrayList(Collection<? extends E> c) {
//將指定集合轉(zhuǎn)換為數(shù)組
elementData = c.toArray();
//如果elementData數(shù)組的長(zhǎng)度不為0
if ((size = elementData.length) != 0) {
// 如果elementData不是Object類(lèi)型數(shù)據(jù)（c.toArray可能返回的不是Object類(lèi)型的數(shù)組所以加上下面的語(yǔ)句用于判斷）
if (elementData.getClass() != Object[].class)
//將原來(lái)不是Object類(lèi)型的elementData數(shù)組的內(nèi)容，賦值給新的Object類(lèi)型的elementData數(shù)組
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 其他情況，用空數(shù)組代替
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* 修改這個(gè)ArrayList實(shí)例的容量是列表的當(dāng)前大小。 應(yīng)用程序可以使用此操作來(lái)最小化ArrayList實(shí)例的存儲(chǔ)。
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//下面是ArrayList的擴(kuò)容機(jī)制
//ArrayList的擴(kuò)容機(jī)制提高了性能，如果每次只擴(kuò)充一個(gè)，
//那么頻繁的插入會(huì)導(dǎo)致頻繁的拷貝，降低性能，而ArrayList的擴(kuò)容機(jī)制避免了這種情況。
/**
* 如有必要，增加此ArrayList實(shí)例的容量，以確保它至少能容納元素的數(shù)量
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
//如果是true，minExpand的值為0，如果是false,minExpand的值為10
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
//如果最小容量大于已有的最大容量
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//得到最小擴(kuò)容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 獲取“默認(rèn)的容量”和“傳入?yún)?shù)”兩者之間的最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//判斷是否需要擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//調(diào)用grow方法進(jìn)行擴(kuò)容，調(diào)用此方法代表已經(jīng)開(kāi)始擴(kuò)容了
grow(minCapacity);
}
/**
* 要分配的最大數(shù)組大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList擴(kuò)容的核心方法。
*/
private void grow(int minCapacity) {
// oldCapacity為舊容量，newCapacity為新容量
int oldCapacity = elementData.length;
//將oldCapacity 右移一位，其效果相當(dāng)于oldCapacity /2，
//我們知道位運(yùn)算的速度遠(yuǎn)遠(yuǎn)快于整除運(yùn)算，整句運(yùn)算式的結(jié)果就是將新容量更新為舊容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那么就把最小需要容量當(dāng)作數(shù)組的新容量，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//再檢查新容量是否超出了ArrayList所定義的最大容量，
//若超出了，則調(diào)用hugeCapacity()來(lái)比較minCapacity和 MAX_ARRAY_SIZE，
//如果minCapacity大于MAX_ARRAY_SIZE，則新容量則為Interger.MAX_VALUE，否則，新容量大小則為 MAX_ARRAY_SIZE。
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);
}
//比較minCapacity和 MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
*返回此列表中的元素?cái)?shù)。
*/
public int size() {
return size;
}
/**
* 如果此列表不包含元素，則返回 true 。
*/
public boolean isEmpty() {
//注意=和==的區(qū)別
return size == 0;
}
/**
* 如果此列表包含指定的元素，則返回true 。
*/
public boolean contains(Object o) {
//indexOf()方法：返回此列表中指定元素的首次出現(xiàn)的索引，如果此列表不包含此元素，則為-1
return indexOf(o) >= 0;
}
/**
*返回此列表中指定元素的首次出現(xiàn)的索引，如果此列表不包含此元素，則為-1
*/
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++)
//equals()方法比較
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 返回此列表中指定元素的最后一次出現(xiàn)的索引，如果此列表不包含元素，則返回-1。.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 返回此ArrayList實(shí)例的淺拷貝。 （元素本身不被復(fù)制。）
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
//Arrays.copyOf功能是實(shí)現(xiàn)數(shù)組的復(fù)制，返回復(fù)制后的數(shù)組。參數(shù)是被復(fù)制的數(shù)組和復(fù)制的長(zhǎng)度
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// 這不應(yīng)該發(fā)生，因?yàn)槲覀兪强梢钥寺〉? throw new InternalError(e);
}
}
/**
*以正確的順序（從第一個(gè)到最后一個(gè)元素）返回一個(gè)包含此列表中所有元素的數(shù)組。
*返回的數(shù)組將是“安全的”，因?yàn)樵摿斜聿槐Ａ魧?duì)它的引用。 （換句話(huà)說(shuō)，這個(gè)方法必須分配一個(gè)新的數(shù)組）。
*因此，調(diào)用者可以自由地修改返回的數(shù)組。 此方法充當(dāng)基于陣列和基于集合的API之間的橋梁。
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 以正確的順序返回一個(gè)包含此列表中所有元素的數(shù)組（從第一個(gè)到最后一個(gè)元素）;
*返回的數(shù)組的運(yùn)行時(shí)類(lèi)型是指定數(shù)組的運(yùn)行時(shí)類(lèi)型。 如果列表適合指定的數(shù)組，則返回其中。
*否則，將為指定數(shù)組的運(yùn)行時(shí)類(lèi)型和此列表的大小分配一個(gè)新數(shù)組。
*如果列表適用于指定的數(shù)組，其余空間（即數(shù)組的列表數(shù)量多于此元素），則緊跟在集合結(jié)束后的數(shù)組中的元素設(shè)置為null 。
*（這僅在調(diào)用者知道列表不包含任何空元素的情況下才能確定列表的長(zhǎng)度。）
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 新建一個(gè)運(yùn)行時(shí)類(lèi)型的數(shù)組，但是ArrayList數(shù)組的內(nèi)容
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//調(diào)用System提供的arraycopy()方法實(shí)現(xiàn)數(shù)組之間的復(fù)制
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* 返回此列表中指定位置的元素。
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* 用指定的元素替換此列表中指定位置的元素。
*/
public E set(int index, E element) {
//對(duì)index進(jìn)行界限檢查
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
//返回原來(lái)在這個(gè)位置的元素
return oldValue;
}
/**
* 將指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//這里看到ArrayList添加元素的實(shí)質(zhì)就相當(dāng)于為數(shù)組賦值
elementData[size++] = e;
return true;
}
/**
* 在此列表中的指定位置插入指定的元素。
*先調(diào)用 rangeCheckForAdd 對(duì)index進(jìn)行界限檢查；然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大；
*再將從index開(kāi)始之后的所有成員后移一個(gè)位置；將element插入index位置；最后size加1。
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy()這個(gè)實(shí)現(xiàn)數(shù)組之間復(fù)制的方法一定要看一下，下面就用到了arraycopy()方法實(shí)現(xiàn)數(shù)組自己復(fù)制自己
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 刪除該列表中指定位置的元素。 將任何后續(xù)元素移動(dòng)到左側(cè)（從其索引中減去一個(gè)元素）。
*/
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;
}
/**
* 從列表中刪除指定元素的第一個(gè)出現(xiàn)（如果存在）。 如果列表不包含該元素，則它不會(huì)更改。
*返回true，如果此列表包含指定的元素
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == 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 remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
/**
* 從列表中刪除所有元素。
*/
public void clear() {
modCount++;
// 把數(shù)組中所有的元素的值設(shè)為null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 按指定集合的Iterator返回的順序?qū)⒅付现械乃性刈芳拥酱肆斜淼哪┪病? */
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 將指定集合中的所有元素插入到此列表中，從指定的位置開(kāi)始。
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* 從此列表中刪除所有索引為fromIndex （含）和toIndex之間的元素。
*將任何后續(xù)元素移動(dòng)到左側(cè)（減少其索引）。
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* 檢查給定的索引是否在范圍內(nèi)。
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* add和addAll使用的rangeCheck的一個(gè)版本
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 返回IndexOutOfBoundsException細(xì)節(jié)信息
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 從此列表中刪除指定集合中包含的所有元素。
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
//如果此列表被修改則返回true
return batchRemove(c, false);
}
/**
* 僅保留此列表中包含在指定集合中的元素。
*換句話(huà)說(shuō)，從此列表中刪除其中不包含在指定集合中的所有元素。
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* 從列表中的指定位置開(kāi)始，返回列表中的元素（按正確順序）的列表迭代器。
*指定的索引表示初始調(diào)用將返回的第一個(gè)元素為next 。 初始調(diào)用previous將返回指定索引減1的元素。
*返回的列表迭代器是fail-fast 。
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
*返回列表中的列表迭代器（按適當(dāng)?shù)捻樞颍? *返回的列表迭代器是fail-fast 。
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
*以正確的順序返回該列表中的元素的迭代器。
*返回的迭代器是fail-fast 。
*/
public Iterator<E> iterator() {
return new Itr();
}
ArrayList 擴(kuò)容機(jī)制分析
構(gòu)造函數(shù)
ArrayList 有三種方式來(lái)初始化，構(gòu)造方法源碼如下：
/**
* 默認(rèn)初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*默認(rèn)構(gòu)造函數(shù)，使用初始容量10構(gòu)造一個(gè)空列表(無(wú)參數(shù)構(gòu)造)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 帶初始容量參數(shù)的構(gòu)造函數(shù)。（用戶(hù)自己指定容量）
*/
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;
}
}
image-20201015194503905
//默認(rèn)初始容量大小
private static final int DEFAULT_CAPACITY = 10;
//空數(shù)組（用于空實(shí)例）。
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默認(rèn)大小空實(shí)例的共享空數(shù)組實(shí)例。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//保存ArrayList數(shù)據(jù)的數(shù)組
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList 所包含的元素個(gè)數(shù)
private int size;
//默認(rèn)構(gòu)造函數(shù)，使用初始容量10構(gòu)造一個(gè)空列表(無(wú)參數(shù)構(gòu)造)
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
<mark>以無(wú)參數(shù)構(gòu)造方法創(chuàng)建 ArrayList 時(shí)，實(shí)際上初始化賦值的是一個(gè)空數(shù)組。</mark>
image-20201015200357062
那么什么時(shí)候才真正分配容量呢？？答案是添加第一個(gè)元素時(shí)
add()
image-20201015200522618
/**
* 將指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {
//添加元素之前，先調(diào)用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
//這里看到ArrayList添加元素的實(shí)質(zhì)就相當(dāng)于為數(shù)組賦值
elementData[size++] = e;
return true;
}
add()將制定的元素追加到末尾， 我們可以看到該方法中首先是調(diào)用了ensureCapacityInternal(size + 1); size+1 =0+1=1。
ensureCapacityInternal()
<mark>該方法得到的是得到最小擴(kuò)容量minCapacity</mark>
image-20201015201301480
//得到的是得到最小擴(kuò)容量minCapacity
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
該方法中調(diào)用的是ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
calculateCapacity()
我們首先來(lái)看calculateCapacity這個(gè)方法，<mark>計(jì)算容量</mark>
image-20201015201917190
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA使用默認(rèn)構(gòu)造器時(shí)已經(jīng)賦值this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;所以符合條件為true。
return Math.max(DEFAULT_CAPACITY, minCapacity); 比較兩值取最大值。DEFAULT_CAPACITY 值為10，minCapacity為傳過(guò)來(lái)的值，第一次為size+1=0+1=1。所以最大值為10。返回10。
ensureExplicitCapacity()
此時(shí)我們?cè)贂?huì)到add方法中查看這個(gè)被調(diào)用的ensureExplicitCapacity方法，該方法是<mark>判斷是否需要擴(kuò)容</mark>
image-20201015202441971
//判斷是否需要擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//調(diào)用grow方法進(jìn)行擴(kuò)容，調(diào)用此方法代表已經(jīng)開(kāi)始擴(kuò)容了
grow(minCapacity);
}
第一次添加元素時(shí)，我們經(jīng)過(guò)重重判斷已經(jīng)得到了minCapacity=10,此時(shí)判斷minCapacity - elementData.length > 0此時(shí)到數(shù)據(jù)長(zhǎng)度還是為0，所以10-0=10>0，符合條件調(diào)用grow()方法。
- 當(dāng)我們要 add 進(jìn)第 1 個(gè)元素到 ArrayList 時(shí)，elementData.length 為 0 （因?yàn)檫€是一個(gè)空的 list），因?yàn)閳?zhí)行了
ensureCapacityInternal()方法 ，所以 minCapacity 此時(shí)為 10。此時(shí)，minCapacity - elementData.length > 0成立，所以會(huì)進(jìn)入grow(minCapacity)方法。 - 當(dāng) add 第 2 個(gè)元素時(shí)，minCapacity 為 2，此時(shí) e lementData.length(容量)在添加第一個(gè)元素后擴(kuò)容成 10 了。此時(shí)，
minCapacity - elementData.length > 0不成立，所以不會(huì)進(jìn)入 （執(zhí)行）grow(minCapacity)方法。 - 添加第 3、4···到第 10 個(gè)元素時(shí)，依然不會(huì)執(zhí)行 grow 方法，數(shù)組容量都為 10。
直到添加第 11 個(gè)元素，minCapacity(為 11)比 elementData.length（為 10）要大。進(jìn)入 grow 方法進(jìn)行擴(kuò)容。
<mark>當(dāng)我們添加第1個(gè)元素，和第11個(gè)元素時(shí)是符合擴(kuò)容條件的。</mark>
grow()
<mark>要分配的最大數(shù)組大小</mark>
image-20201015203613540
添加第1個(gè)元素時(shí):
int oldCapacity = elementData.length;oldCapacity=0;-
int newCapacity = oldCapacity + (oldCapacity >> 1);newCapacity = 0 + 0/2 = 0;<mark>newCapacity這個(gè)代表了新的數(shù)組的大小，>>1 右移一位相當(dāng)于除 2，加上原數(shù)組大小的一半，也就是擴(kuò)容1.5</mark>oldCapacity 為偶數(shù)就是 1.5 倍，否則是 1.5 倍左右）！ 奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇數(shù)的話(huà)會(huì)丟掉小數(shù).
第一個(gè)if條件
newCapacity - minCapacity < 0此時(shí)是滿(mǎn)足的0-10=-10<0,所以newCapacity = minCapacity;此時(shí)newCapacity為10第二個(gè)if條件
newCapacity - MAX_ARRAY_SIZE > 0由上面定義的代碼可以的得到private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;這個(gè)數(shù)是21億，比他小。不符合。elementData = Arrays.copyOf(elementData, newCapacity);通過(guò)Arrays.copy將原本的數(shù)組復(fù)制并且長(zhǎng)度變成了newCapacity也就是10。此時(shí)我們的ArrayList也就終于有了容量。默認(rèn)為10
此時(shí)終于可以回到add方法了執(zhí)行后面的代碼elementData[size++] = e;此時(shí)elemetnData的長(zhǎng)度已經(jīng)為10了，size為0，在elementData[0]添加元素，size+1=1。返回true。
image-20201015205752417
當(dāng)添加第11個(gè)元素時(shí)：
-
int oldCapacity = elementData.length;為10 -
int newCapacity = oldCapacity + (oldCapacity >> 1);10+10/2 = 15 - 全都不符
elementData = Arrays.copyOf(elementData, newCapacity);復(fù)制原數(shù)組擴(kuò)容為15。
/**
* 要分配的最大數(shù)組大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList擴(kuò)容的核心方法。
*/
private void grow(int minCapacity) {
// oldCapacity為舊容量，newCapacity為新容量
int oldCapacity = elementData.length;
//將oldCapacity 右移一位，其效果相當(dāng)于oldCapacity /2，
//我們知道位運(yùn)算的速度遠(yuǎn)遠(yuǎn)快于整除運(yùn)算，整句運(yùn)算式的結(jié)果就是將新容量更新為舊容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那么就把最小需要容量當(dāng)作數(shù)組的新容量，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) `hugeCapacity()` 方法來(lái)比較 minCapacity 和 MAX_ARRAY_SIZE，
//如果minCapacity大于最大容量，則新容量則為`Integer.MAX_VALUE`，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`。
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);
}
hugeCapacity()
從上面 grow() 方法源碼我們知道： 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) hugeCapacity() 方法來(lái)比較 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，則新容量則為Integer.MAX_VALUE，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 Integer.MAX_VALUE - 8。
image-20201015211304744
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//對(duì)minCapacity和MAX_ARRAY_SIZE進(jìn)行比較
//若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;
}
System.arraycopy() 和 Arrays.copyOf()
閱讀源碼的話(huà)，我們就會(huì)發(fā)現(xiàn) ArrayList 中大量調(diào)用了這兩個(gè)方法。比如：我們上面講的擴(kuò)容操作以及add(int index, E element)、toArray() 等方法中都用到了該方法！
image-20201015211653292
image-20201015211502747
看兩者源代碼可以發(fā)現(xiàn) copyOf()內(nèi)部實(shí)際調(diào)用了 System.arraycopy() 方法
arraycopy() 需要目標(biāo)數(shù)組，將原數(shù)組拷貝到你自己定義的數(shù)組里或者原數(shù)組，而且可以選擇拷貝的起點(diǎn)和長(zhǎng)度以及放入新數(shù)組中的位置 copyOf() 是系統(tǒng)自動(dòng)在內(nèi)部新建一個(gè)數(shù)組，并返回該數(shù)組。
總結(jié)
當(dāng)我們使用默認(rèn)的構(gòu)造器是實(shí)例化ArrayList時(shí)，數(shù)組大小經(jīng)過(guò)種種判斷擴(kuò)容為10。
使用默認(rèn)構(gòu)造器實(shí)例化的ArrayList，在第一次添加元素和第11次添加元素時(shí)才會(huì)觸發(fā)擴(kuò)容。也就是第一次時(shí)，和超過(guò)數(shù)組容量時(shí)添加才觸發(fā)擴(kuò)容。
而初始化指定實(shí)例化創(chuàng)建的ArrayList只有超過(guò)數(shù)組容量時(shí)添加才觸發(fā)擴(kuò)容。擴(kuò)容為1.5倍左右（分奇偶數(shù)）
ensureCapacity方法
ArrayList 源碼中有一個(gè) ensureCapacity 方法不知道大家注意到?jīng)]有，這個(gè)方法 ArrayList 內(nèi)部沒(méi)有被調(diào)用過(guò)，所以很顯然是提供給用戶(hù)調(diào)用的，那么這個(gè)方法有什么作用呢？
/**
如有必要，增加此 ArrayList 實(shí)例的容量，以確保它至少可以容納由minimum capacity參數(shù)指定的元素?cái)?shù)。
*
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
最好在 add 大量元素之前用 ensureCapacity 方法，以減少增量重新分配的次數(shù)
我們通過(guò)下面的代碼實(shí)際測(cè)試以下這個(gè)方法的效果：
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法前："+(endTime - startTime));
}
}
運(yùn)行結(jié)果：
使用ensureCapacity方法前：2158
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
}
}
運(yùn)行結(jié)果：
使用ensureCapacity方法前：1773
通過(guò)運(yùn)行結(jié)果，我們可以看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法，以減少增量重新分配的次數(shù)。
細(xì)節(jié)
JDK7
JDK1.7:ArrayList像餓漢式，直接創(chuàng)建一個(gè)初始容量為10的數(shù)組
JDK1.8:ArrayList像懶漢式，一開(kāi)始創(chuàng)建一個(gè)長(zhǎng)度為0的數(shù)組，當(dāng)添加第一個(gè)元 素時(shí)再創(chuàng)建一個(gè)始容量為10的數(shù)組
Arraylist 和 Vector 的區(qū)別?
https://www.kylin.show/60919.html
-
ArrayList是List的主要實(shí)現(xiàn)類(lèi)，底層使用Object[ ]存儲(chǔ)，適用于頻繁的查找工作，線(xiàn)程不安全 ； -
Vector是List的古老實(shí)現(xiàn)類(lèi)，底層使用Object[ ]存儲(chǔ)，線(xiàn)程安全的。(底層synchronized同步方法)
Arraylist 與 LinkedList 區(qū)別?
-
是否保證線(xiàn)程安全：
ArrayList和LinkedList都是不同步的，也就是不保證線(xiàn)程安全； -
底層數(shù)據(jù)結(jié)構(gòu)：
Arraylist底層使用的是Object數(shù)組；LinkedList底層使用的是 雙向鏈表 數(shù)據(jù)結(jié)構(gòu)（JDK1.6 之前為循環(huán)鏈表，JDK1.7 取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別，下面有介紹到?。?/li> -
插入和刪除是否受元素位置的影響： ①
ArrayList采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。 比如：執(zhí)行add(E e)方法的時(shí)候，ArrayList會(huì)默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是 O(1)。但是如果要在指定位置 i 插入和刪除元素的話(huà)（add(int index, E element)）時(shí)間復(fù)雜度就為 O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第 i 和第 i 個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作。 ②LinkedList采用鏈表存儲(chǔ)，所以對(duì)于add(E e)方法的插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，近似 O(1)，如果是要在指定位置i插入和刪除元素的話(huà)（(add(int index, E element)） 時(shí)間復(fù)雜度近似為o(n))因?yàn)樾枰纫苿?dòng)到指定位置再插入。 -
是否支持快速隨機(jī)訪(fǎng)問(wèn)：
LinkedList不支持高效的隨機(jī)元素訪(fǎng)問(wèn)，而ArrayList支持?？焖匐S機(jī)訪(fǎng)問(wèn)就是通過(guò)元素的序號(hào)快速獲取元素對(duì)象(對(duì)應(yīng)于get(int index)方法)。 -
內(nèi)存空間占用：
ArrayList的空 間浪費(fèi)主要體現(xiàn)在在 list 列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而LinkedList的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比ArrayList更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。
