一. 知識點概述
ArrayList 是 Java 中的一種集合（Collection）類，它可以用來存儲一組對象。下面是一些 ArrayList 的重要知識點：
- ArrayList 是動態(tài)數(shù)組，它的大小可以根據(jù)需要自動增長或縮小。
- ArrayList 是通過數(shù)組實現(xiàn)的，每個元素可以通過其索引進(jìn)行訪問。
- ArrayList 可以存儲任意類型的對象，包括基本類型的包裝器類和自定義對象。
- ArrayList 可以使用泛型來指定存儲的對象類型，以增加類型安全性。
- ArrayList 可以使用 add() 方法添加元素，remove() 方法刪除元素，get() 方法獲取元素，set() 方法更新元素等。
- ArrayList 支持隨機(jī)訪問，它的 get() 方法的時間復(fù)雜度為 O(1)。
- ArrayList 是非線程安全的，多線程環(huán)境下應(yīng)該使用線程安全的類或進(jìn)行同步控制。
- ArrayList 與數(shù)組相比，它具有更強(qiáng)的靈活性和更多的功能，但在某些情況下可能會比數(shù)組效率低。
- ArrayList 可以使用迭代器（Iterator）來遍歷集合中的元素。
- ArrayList 可以使用 toArray() 方法將集合轉(zhuǎn)換為數(shù)組。
總之，ArrayList 是 Java 中常用的一種集合類，它具有動態(tài)數(shù)組的特點，并提供了豐富的操作和功能，可以方便地操作集合中的元素。
二. 源碼閱讀
1. 類成員變量解釋
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
serialVersionUID：Serializable的版本控制號DEFAULT_CAPACITY：默認(rèn)初始化容量transient：java 的transient關(guān)鍵字為我們提供了便利，你只需要實現(xiàn)Serilizable接口，將不需要序列化的屬性前添加關(guān)鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目的地中。size：用來記錄數(shù)組中的元素數(shù)
2. 重要方法分析
- 構(gòu)造方法
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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;
}
}
- 第一個構(gòu)造函數(shù)，參數(shù)為用戶傳遞的容量，如果容量大于0則創(chuàng)建一個指定容量的Object數(shù)組，如果是0則使用前面定義的EMPTY_ELEMENTDATA空數(shù)組，小于0則拋出
IllegalArgumentException異常- 第二個構(gòu)造函數(shù)為默認(rèn)構(gòu)造函數(shù)，直接使用前面定義的
DEFAULTCAPACITY_EMPTY_ELEMENTDATA空數(shù)組- 第三個構(gòu)造函數(shù)，參數(shù)為其它集合數(shù)組 ，使用范型限定量集合數(shù)組的元素類型
<? extends E>，其構(gòu)造的原理是如果c類型是ArrayList類型直接賦值即可，否則使用Arrays.copy()方法將元素拷貝過來，Arrays.copy()方法的源碼如下：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
- 參數(shù) ：
original原始數(shù)組，newLength新數(shù)組長度，newType新數(shù)組類型- 邏輯：該方法首先根據(jù)新數(shù)組類型創(chuàng)建一個新的數(shù)組對象，然后將原始數(shù)組中的元素復(fù)制到新數(shù)組中。如果新數(shù)組類型是Object[]，則直接創(chuàng)建一個Object類型的數(shù)組；否則，使用Array.newInstance()方法創(chuàng)建指定類型的數(shù)組。最后，將新數(shù)組返回。原始數(shù)組中從下標(biāo)0開始的一部分元素會被復(fù)制到新數(shù)組中從下標(biāo)0開始的位置。其中，Math.min(original.length, newLength)用于計算要復(fù)制的元素數(shù)量，取原始數(shù)組長度和新數(shù)組長度的最小值，以避免復(fù)制超出原始數(shù)組范圍的元素。
- trimToSize函數(shù)
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
- 介紹：將此 ArrayList 實例的容量修剪為列表的當(dāng)前大小。應(yīng)用程序可以使用此操作來最小化 ArrayList 實例的存儲。
-modCount介紹：該變量的作用是用于支持集合類的fail-fast機(jī)制，當(dāng)多個線程同時對同一個集合進(jìn)行修改時，可能會導(dǎo)致集合狀態(tài)不一致的情況。為了避免這種情況，Java集合類通常會在集合結(jié)構(gòu)發(fā)生變化時，立即拋出ConcurrentModificationException異常。當(dāng)集合類中的數(shù)據(jù)結(jié)構(gòu)被修改時，modCount值會自增，用于表示集合被修改的次數(shù)。在遍歷集合元素時，集合類會檢查modCount值是否與預(yù)期值相等，如果不相等則表示集合已經(jīng)被修改過，拋出ConcurrentModificationException異常。因此，該變量的作用是記錄集合被修改的次數(shù)，以支持集合類的fail-fast機(jī)制。
fail-fast機(jī)制：fail-fast機(jī)制是Java集合框架中一種用于檢測并發(fā)修改的機(jī)制，它的主要思想是：當(dāng)多個線程對同一個集合進(jìn)行并發(fā)修改時，如果有一個線程對集合進(jìn)行了修改，那么其他線程訪問集合時就有可能會拋出ConcurrentModificationException異常，以保證集合的數(shù)據(jù)一致性。Java集合類通常使用一個叫做“修改次數(shù)”的計數(shù)器來實現(xiàn)fail-fast機(jī)制。這個計數(shù)器會記錄集合的修改次數(shù)，當(dāng)集合的結(jié)構(gòu)發(fā)生變化時，計數(shù)器的值會自增。在遍歷集合時，Java集合類會檢查計數(shù)器的值是否與預(yù)期值相等，如果不相等就會拋出ConcurrentModificationException異常。modCount就是Java集合框架中用來記錄集合被修改次數(shù)的計數(shù)器，它在Java集合類中的具體實現(xiàn)可能會略有不同。在大部分集合類中，當(dāng)集合發(fā)生結(jié)構(gòu)性修改時（比如添加或刪除元素），modCount就會自增，而在遍歷集合時，集合類會記錄modCount的值，并在每次遍歷元素前檢查modCount是否與之前記錄的值相等。如果不相等，就表示集合被修改過，就會拋出ConcurrentModificationException異常，以保證集合的數(shù)據(jù)一致性?？傊?，Java集合框架中的fail-fast機(jī)制是通過修改次數(shù)計數(shù)器（如modCount）和檢查機(jī)制來實現(xiàn)的，以保證多線程并發(fā)修改集合時的數(shù)據(jù)一致性和安全性。
- ArrayList自動增長和縮小功能實現(xiàn)的源碼
我們知道 ArrayList 是動態(tài)數(shù)組，它的大小可以根據(jù)需要自動增長或縮小。
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;
//如果指定的容量大于，擴(kuò)容操作的最小容量
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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;
}
ensureCapacity函數(shù)的作用是設(shè)置我們指定容量的動態(tài)數(shù)組，如果元素超過指定容量，就會自動調(diào)整大小這段代碼方法中的參數(shù)minCapacity表示要確保ArrayList對象至少能夠容納minCapacity個元素。該方法首先會根據(jù)ArrayList對象的當(dāng)前元素容量，判斷是否需要進(jìn)行擴(kuò)容操作。如果ArrayList對象的元素容量已經(jīng)大于指定容量minCapacity，則不需要進(jìn)行任何操作；否則，就需要進(jìn)行擴(kuò)容操作。在這里，minExpand變量的值表示需要進(jìn)行擴(kuò)容操作的最小容量，它的計算方式是：如果ArrayList對象的elementData數(shù)組不是默認(rèn)的空數(shù)組（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），則可以容納任意數(shù)量的元素，因此minExpand的值為0；否則，如果ArrayList對象的elementData數(shù)組是默認(rèn)的空數(shù)組，則minExpand的值為DEFAULT_CAPACITY，表示需要擴(kuò)容到默認(rèn)的初始容量。如果指定的minCapacity大于minExpand，則需要調(diào)用ensureExplicitCapacity()方法進(jìn)行實際的擴(kuò)容操作。否則，不需要進(jìn)行擴(kuò)容操作。總之，該方法的作用是確保ArrayList對象能夠容納指定數(shù)量的元素，并在需要時進(jìn)行擴(kuò)容操作。ensureExplicitCapacity：用來進(jìn)行擴(kuò)容操作，如果指定容納的元素minCapacity大于當(dāng)前數(shù)組中的元素個數(shù)，則調(diào)用grow方法實現(xiàn)擴(kuò)容操作grow方法就是擴(kuò)容的主體函數(shù)了，它的邏輯是首先使用oldCapacity記錄當(dāng)前數(shù)組的容量，然后定義newCapacity為原來容量的1.5倍（右移一位相當(dāng)于翻一倍），然后如果用戶指定的最小容量newCapacity大于newCapacity，就將newCapacity設(shè)置為minCapacity，如果newCapacity大于MAX_ARRAY_SIZE則調(diào)用hugeCapacity設(shè)置容量。最后調(diào)用Arrays.copyOf實現(xiàn)擴(kuò)容
- ArrayList常見的增、刪、改、查功能等其它功能源碼
- 返回ArrayList的元素個數(shù)
public int size() {
return size;
}
- 判空
public boolean isEmpty() {
return size == 0;
}
- 判斷集合中是否有某個元素，以及某個元素在數(shù)組中的索引
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
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;
}
還有一個
lastIndexOf，即返回指定元素在ArrayList中的最后出現(xiàn)的位置，其實就是for反向遍歷即可
- ArrayList克隆
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);
}
}
具體來說，該方法首先調(diào)用 Object 類的 clone() 方法創(chuàng)建一個當(dāng)前 ArrayList 實例的淺拷貝，即復(fù)制當(dāng)前 ArrayList 實例的字段值（包括 elementData 數(shù)組和 size 等）到一個新的 ArrayList 實例中。然后，該方法使用 Arrays.copyOf(Object[] original, int newLength) 方法將 elementData 數(shù)組復(fù)制到新的 ArrayList 實例中，并將新 ArrayList 實例的 modCount 值設(shè)為 0，以確保新 ArrayList 實例的修改次數(shù)與原始 ArrayList 實例相同。最后，該方法返回新的 ArrayList 實例，即當(dāng)前 ArrayList 實例的副本。需要注意的是，該方法只是創(chuàng)建了當(dāng)前 ArrayList 實例的副本，并不會對其中的元素進(jìn)行深度拷貝。因此，如果原始 ArrayList 實例中包含可變對象（如 ArrayList 或 HashMap 等），則對副本進(jìn)行修改可能會影響原始 ArrayList 實例。
淺拷貝和深拷貝
Java 中的淺拷貝和深拷貝是指對象復(fù)制時所采用的不同策略。淺拷貝：淺拷貝是指將一個對象復(fù)制到一個新的對象中，但是新對象與原始對象共享相同的子對象。簡單來說，淺拷貝只復(fù)制對象本身，不會對對象內(nèi)部的引用類型屬性進(jìn)行復(fù)制，新對象與原始對象共享同一個引用類型屬性的內(nèi)存地址。這意味著，如果對新對象的引用類型屬性進(jìn)行修改，原始對象也會受到影響。
Java 中的 Object 類提供了一個默認(rèn)的淺拷貝方法 clone()，可以通過重寫該方法實現(xiàn)淺拷貝。深拷貝：深拷貝是指將一個對象復(fù)制到一個新的對象中，但是新對象與原始對象不共享任何子對象。簡單來說，深拷貝會復(fù)制對象本身和對象內(nèi)部所有的引用類型屬性，新對象與原始對象之間互相獨立，對新對象的任何修改都不會影響原始對象。Java 中實現(xiàn)深拷貝的方式有很多，常用的方法包括序列化和反序列化、遞歸遍歷對象并創(chuàng)建一個新的對象等。需要注意的是，在對對象進(jìn)行拷貝時，淺拷貝雖然比較簡單高效，但是由于共享內(nèi)存地址的關(guān)系，可能會出現(xiàn)對原始對象產(chǎn)生不可預(yù)測的影響，因此在需要完全獨立的新對象時，應(yīng)該采用深拷貝。
- 將ArrayList轉(zhuǎn)換為普通數(shù)組對象
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
- 獲得指定索引位置的元素
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
底層原理就是返回數(shù)組指定下標(biāo)的元素，
rangeCheck就是檢查給定的index是否超出了數(shù)組的大小，是則拋出IndexOutOfBoundsException異常
- 更改指定位置的元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- 添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
首先調(diào)用
ensureCapacityInternal來對數(shù)組擴(kuò)容，然后加到數(shù)組最后面
- 指定位置添加元素
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++;
}
原理就是，將原來數(shù)組的index后面的元素利用拷貝向后面移動一位，將index位置空出來，然后再把新的元素加入到這個位置即可
System.arraycopy它的作用是將一個數(shù)組中的指定范圍的元素復(fù)制到另一個數(shù)組中的指定位置，參數(shù)介紹：
1.源數(shù)組(Object src)：需要拷貝的源數(shù)組。
2.源數(shù)組中的拷貝起始位置(int srcPos)：源數(shù)組中需要拷貝的起始位置，拷貝從該位置開始。
3.目標(biāo)數(shù)組(Object dest)：拷貝到目標(biāo)數(shù)組中的目標(biāo)數(shù)組。
4.目標(biāo)數(shù)組中的拷貝起始位置(int destPos)：目標(biāo)數(shù)組中需要拷貝到的起始位置，拷貝從該位置開始。
5.需要拷貝的元素個數(shù)(int length)：拷貝的元素個數(shù)，即從源數(shù)組中拷貝的元素個數(shù)。
- 刪除指定位置的元素
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;
}
- 參數(shù)為數(shù)組下標(biāo)，首先記錄要刪除的元素，然后同樣使用
System.arraycopy將index+1后面的元素拷貝到index開始的位置，即覆蓋了index出的元素，同時將數(shù)組最后一個元素設(shè)置為null，然后返回刪除的元素即可
- 按照元素內(nèi)容刪除元素
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 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
}
- 該函數(shù)會刪除所有與參數(shù)匹配的元素，其原理是首先找到的指定元素在數(shù)組中的索引，然后調(diào)用
fastRemove函數(shù)，按照鎖索引對元素進(jìn)行刪除
- 刪除集合中所有元素
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
它將所有元素設(shè)置為空值，同時size設(shè)置為0
當(dāng)然還有其它重要的方法，具體的原理實現(xiàn)方法都和上面介紹的類似，下面只做簡單介紹：public boolean addAll(int index, Collection<? extends E> c)：在指定索引位置加入一個集合中所有元素，也是用的System.arraycopy方法protected void removeRange(int fromIndex, int toIndex)：刪除指定范圍的元素，也是System.arraycopy方法文章來源：http://www.zghlxwxcb.cn/news/detail-424841.html
3. 迭代器方法
- 獲取一個迭代器對象
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
第一個：指定index位置的對象為迭代器指向的第一個元素
第二個：指定0位置的對象為迭代器指向的第一個元素文章來源地址http://www.zghlxwxcb.cn/news/detail-424841.html
- 內(nèi)部類實現(xiàn)
Iterator接口
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
- 自定義迭代器對象
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
到了這里，關(guān)于ArrayList集合源碼閱讀的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
