原文鏈接http://zhhll.icu/2021/01/04/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/ArrayList%E8%AF%A6%E8%A7%A3/
ArrayList詳解
List中使用最多的就是ArrayList，基本上大家在實體化一個List的時候都是
List list = new ArrayList();
所以在這里了解一下ArrayList的實作程序(以java8為例)
主要特點
- 有序存盤元素
- 允許元素重復，允許存盤null值
- 支持動態擴容
- 非執行緒安全
繼承關系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
繼承了AbstractList類，實作了List介面、RandomAccess介面、Cloneable介面和Serializable介面，所以ArrayList是支持隨機訪問、克隆和序列化的
原始碼分析
關鍵變數
/**
* 默認的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 默認的空陣列
*/
private static final Object[] EMPTY_ELEMENTDATA = https://www.cnblogs.com/life-time/p/{};
/**
* 默認無參構造器使用的空陣列
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList底層用來存盤資料的陣列
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList實際的長度
*/
private int size;
/**
* 可分配的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
建構式
/**
* 自定義初始化容量，根據傳入的初始化容量來確定elementData的陣列容量
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = https://www.cnblogs.com/life-time/p/new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 無參構造器，可以看到并沒有在實體化的時候分配陣列容量，而是使用了空陣列
* 在真正存放元素時才會分配
*/
public ArrayList() {
this.elementData = https://www.cnblogs.com/life-time/p/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 通過集合來進行初始化，使用了Arrays.copyOf來將集合中的資料copy到陣列中
*/
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;
}
}
add方法
public boolean add(E e) {
// 在添加元素之前先確認一下容量是否足夠
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// minCapacity為當前所需要的最小容量
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 計算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果在進行初始化的時候使用的無參構造器，此時才會給賦初始容量為10
if (elementData =https://www.cnblogs.com/life-time/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 計算修改次數
modCount++;
// 需要的容量大于陣列容量的話，需要進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 擴容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 當原陣列為空陣列時，newCapacity為0，是小于minCapacity 10 的
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);
}
remove方法
public E remove(int index) {
// 陣列下標檢查
rangeCheck(index);
// 計算修改次數
modCount++;
// 獲取該所索引位置下原來的的元素
E oldValue = https://www.cnblogs.com/life-time/p/elementData(index);
// 所要移動的數量
int numMoved = size - index - 1;
if (numMoved > 0)
// 第一個引數為源資料
// 第二個引數為從源資料的哪個位置開始復制
// 第三個引數為目標資料
// 第四個引數為從目標資料的哪個位置開始被復制
// 第五個引數為被復制的元素數量
System.arraycopy(elementData, index+1, elementData, index,
numMoved); // index所對應的元素被洗掉，后續所有的元素向前移動一位
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
其他的方法都是中規中矩的操作陣列
如:
// get
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// indexOf
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;
}
迭代器
在使用foreach回圈遍歷的時候實際上是使用的迭代器，對于ArrayList而言，使用普通的for回圈會比使用foreach效率更高
接下來看一下ArrayList的迭代器
public Iterator<E> iterator() {
return new Itr();
}
Itr是ArrayList的內部類，實作了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
// 當Itr被實體化的時候，記錄一下迭代器被實體化時ArrayList的修改次數(在用ArrayList進行add/remove操作時modCount每次都加一)
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 = https://www.cnblogs.com/life-time/p/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 = https://www.cnblogs.com/life-time/p/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() {
// 當修改次數與Itr被實體化時的修改次數不一致時，說明在進行迭代操作的時候其他執行緒進行了ArrrayList的add/remove操作，此時拋出ConcurrentModificationException，即為fast-fail快速失敗機制
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
使用說明
- 由于ArrayList的默認初始值為10，擴容為1.5倍，如果集合中所需要存盤的元素數量多的話，需要進行多次擴容，重新申請記憶體并進行賦值，比較耗時，所以如果在進行實體化時指定初始容量，可以減少擴容次數，提升性能
由于本身的博客百度沒有收錄，博客地址http://zhhll.icu
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/252449.html
標籤：Java