JDK源碼閲讀:ArrayList原理
持續創作,加速成長!這是我參與「掘金日新計劃 · 10 月更文挑戰」的第9天,點擊查看活動詳情
ArrayList
原理
ArrayList
集合底層數據結構
ArrayList
集合介紹
List
接口的可調整大小的數組實現。
數組:一旦初始化長度就不可以發生改變
數組結構特性
增刪慢:每次刪除元素,都需要更改數組長度、拷貝以及移動元素位置。
查詢快:由於數組在內存中是一塊連續空間,因此可以根據地址+索引的方式快速獲取對應位置上的元素。
ArrayList
繼承關係
Serializable
序列化接口
類的序列化由實現java.io.Serializable
接口的類啟用。 不實現此接口的類將不會使任何狀態序列化或反序列化。 可序列化類的所有子類型都是可序列化的。 序列化接口沒有方法或字段,僅用於標識可串行化的語義。
序列化是將對象狀態轉換為可保持或傳輸的格式的過程。
與序列化相對的是反序列化,它將流轉換為對象。
比如將對象的數據序列化後寫入到文件;
將文件中對象的數據讀取出來後反序列化解析成對象。
在需要進行對象數據網絡傳輸或持久化時,需要將對象進行序列化
源碼
public interface Serializable {
}
從源碼上看Serializable
是一個空接口,Java裏稱為標識接口,當類實現Serializable
接口,相當於給該類標記了“可被序列化”的元數據,打上了“可被序列化”的標籤。
序列化/反序列化測試
static class SerTest01 {
public static void main(String[] args) throws IOException, ClassNotFoundException {
// 測試序列化寫入文件
writeObject();
// 測試反序列化文件讀取
readObject();
}
// 將對象數據寫入文件
private static void writeObject() throws IOException {
// 序列化:將對象的數據寫入到文件(寫對象)
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("testoutfile\obj.txt"));
User user = new User("李四", 78);
// 將對象數據寫入文件
oos.writeObject(user);
// 關閉流
oos.close();
}
// 將對象數據寫入文件
private static void readObject() throws IOException, ClassNotFoundException {
// 反序列化:將文件中對象的數據讀取出來(讀對象)
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("..\obj.txt"));
User user = (User) ois.readObject();
// 將對象數據寫入文件
System.out.println(user.toString());
// 關閉流
ois.close();
}
}
// User實體類
public class User implements Serializable {
/**
* 類的序列化由實現`java.io.Serializable`接口的類啟用。
* 不實現此接口的類將不會使任何狀態序列化或反序列化。
* 可序列化類的所有子類型都是可序列化的。
* 序列化接口沒有方法或字段,僅用於標識可串行化的語義。
*/
public final long serialVersionUID = 1510141000893066237L;
private String name;
private Integer age;
public User() {
}
public User(String name, Integer age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age).append("]");
return sb.toString();
}
}
實現了Serializable
接口的User
類可以被ObjectOutputStream
轉換為字節流寫入文件,同時也可以通過ObjectInputStream
再將其從文件讀取並解析為對象。
如果User
實體類不實現Serializable
則無法序列化或反序列化,就會拋出異常NotSerializableException
。運行會出現下圖報錯
判斷是否實現Serializable
的源碼
if (obj instanceof String) {
writeString((String) obj, unshared);
} else if (cl.isArray()) {
writeArray(obj, desc, unshared);
} else if (obj instanceof Enum) {
writeEnum((Enum<?>) obj, desc, unshared);
} else if (obj instanceof Serializable) {
writeOrdinaryObject(obj, desc, unshared);
} else {
if (extendedDebugInfo) {
throw new NotSerializableException(
cl.getName() + "\n" + debugInfoStack.toString());
} else {
throw new NotSerializableException(cl.getName());
}
}
這裏可以看到,Java對字符串、數組、枚舉類、普通類進行序列化時單獨判斷的,當普通類沒有實現Serializable
接口就會拋出異常NotSerializableException
。
RandomAccess
隨機訪問
List
實現使用的標記接口,表明它們支持快速(通常是恆定時間)隨機訪問。此接口的主要目的是允許通用算法更改其行為,以便在應用於隨機訪問列表或順序訪問列表時提供良好的性能。
用於操作隨機訪問列表(例如ArrayList
)的最佳算法在應用於順序訪問列表(例如LinkedList
)時會產生二次行為。鼓勵通用列表算法在應用算法之前檢查給定列表是否是此接口的實例,如果將其應用於順序訪問列表會提供較差的性能,並在必要時更改它們的行為以保證可接受的性能。
眾所周知,隨機訪問和順序訪問之間的區別通常是模糊的。例如,如果某些List
實現變得很大,則提供漸近線性訪問時間,但在實踐中訪問時間是恆定的。這樣的List實現一般應該實現這個接口。根據經驗,如果對於類的典型實例,如果出現以下循環,則List
實現應該實現此接口:
// 隨機訪問,list.get(i)根據索引遍歷
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
運行速度比這個循環快:
// 順序訪問,迭代器進行遍歷
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
源碼
public interface RandomAccess {
}
測試順序訪問和隨機訪問速度
/**
* 測試隨機訪問比順序訪問快,這裏僅對ArrayList做遍歷操作
*
* @param args
*/
public static void main(String[] args) {
// 創建ArrayList集合
List<String> list = new ArrayList<>();
// 添加50W條數據
for (int i = 0; i < 500000; i++) {
list.add(i + "a");
}
System.out.println("----通過索引(隨機訪問)----");
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("隨機訪問用時: " + (endTime - startTime));
System.out.println("----通過迭代器(順序訪問)----");
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("順序訪問用時: " + (endTime - startTime));
}
//----通過索引(隨機訪問)----
//隨機訪問用時: 3
//----通過迭代器(順序訪問)----
//順序訪問用時: 4
從輸出結果來看ArrayList
隨機訪問比順序訪問快,接下來對比下LinkedList
```
public static void main(String[] args) {
// 創建ArrayList集合
List
從輸出結果來看LinkedList
的順序遍歷比隨機訪問快。
LinkedList
源碼
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 具體實現源碼此處不進行討論,省略...
}
可以看到LinkedList
並沒有實現RandomAccess
接口,符合RandomAccess
接口介紹內容,此外LinkedList
結構也確定了它的順序遍歷比隨機訪問快。
實際應用場景中建議使用instanceof
判斷集合是否實現了RandomAccess
接口,再根據實際情況使用隨機訪問或順序訪問。
if(list instanceof RandomAccess)
// 隨機訪問
else
// 順序訪問
Cloneable克隆接口
一個類實現了Cloneable
接口,以向Object.clone()
方法指示該方法可以合法地對該類的實例進行逐個字段的複製。
在未實現Cloneable
接口的實例上調用 Object.clone()
方法會導致拋出異常CloneNotSupportedException
。
源碼
public interface Cloneable {
}
Cloneable
也是一個標識接口,此接口不包含clone方法。因此,不可能僅憑藉實現該接口的實例來克隆對象。即使以反射方式調用 clone 方法,也不能保證它會成功。
clone()使用實例
public static void main(String[] args) {
// 創建用户對象集合
ArrayList<User> list = new ArrayList<User>();
list.add(new User("李四", 78));
list.add(new User("張三", 28));
Object o = list.clone();
System.out.println(o);
System.out.println(list);
System.out.println(o == list);
}
// false
// [[name = 李四, age = 78], [name = 張三, age = 28]]
// [[name = 李四, age = 78], [name = 張三, age = 28]]
從輸出看,clone()
創建了一個新的對象,內容與原對象一致。
ArrayList
實現了Cloneable
接口,故而該類可以可以調用Object.clone()
方法實現對象克隆。
若類沒有實現Cloneable
接口,該實例調用 Object.clone()
方法會導致拋出異常CloneNotSupportedException
。
clone
源碼
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);
}
}
普通類支持 Object.clone()
方法
修改User
類,使得支持 Object.clone()
方法
public class User implements Serializable, Cloneable {
public final long serialVersionUID = 1510141000893066237L;
// 屬性 getter setter toString...
// 重寫clone
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
User
類實現Cloneable
接口,並重寫 Object.clone()
方法。
重寫原則
- 子類返回類型小於等於父類方法返回類型
- 子類拋出異常小於等於父類方法拋出異常
- 子類訪問權限大於等於父類方法訪問權限(public>protected>friendly,private不能被繼承)
static class Cloneable01 {
public static void main(String[] args) throws CloneNotSupportedException {
User user1 = new User("張", 12);
Object user2 = user1.clone();
System.out.println(user1);
System.out.println(user2);
System.out.println(user1 == user2);
}
}
// [name = 張, age = 12]
// [name = 張, age = 12]
// false
淺拷貝
新建Address
類,如下所示
public class Address implements Serializable {
public final long serialVersionUID = 1578511564815489L;
private String city;
public Address() {
}
public Address(String city) {
this.city = city;
}
public String getCity() {
return city;
}
public void setCity(String city) {
this.city = city;
}
@Override
public String toString() {
return city;
}
}
修改User
類如下所示
public class User implements Serializable, Cloneable {
public final long serialVersionUID = 1510141000893066237L;
private String name;
private Integer age;
private Address address;
// setter getter...
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age);
if (address != null)
sb.append(", address = ").append(this.address.toString());
sb.append("]");
return sb.toString();
}
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
淺拷貝測試類
/**
* 淺拷貝
*/
static class Cloneable02 {
public static void main(String[] args) throws CloneNotSupportedException {
Address address = new Address("北京");
User user1 = new User("張", 12, address);
User user2 = (User)user1.clone();
System.out.println(user1);
System.out.println(user2);
System.out.println(user1 == user2);
System.out.println(user2.getAddress() == user1.getAddress());
address.setCity("海口");
user1.setAddress(address);
System.out.println(user1);
System.out.println(user2);
}
}
//[name = 張, age = 12, address = 北京]
//[name = 張, age = 12, address = 北京]
//false
//true
//[name = 張, age = 12, address = 海口]
//[name = 張, age = 12, address = 海口]
從輸出結果可以得知User
類的基本數據類型可以達到完全複製,引用數據類型卻不可以。
原因在於在User
對象user1
被克隆的時候,其屬性address
作為引用類型僅僅是拷貝了一份引用,兩者指向的地址仍是一致的。因此當address
的值發生改變時,被克隆對象user2
的屬性address
的值也會改變。
深拷貝
修改Address
類,如下所示
public class Address implements Serializable, Cloneable {
public final long serialVersionUID = 1578511564815489L;
// getter setter toString...
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
Address
類實現Cloneable
接口,並重寫 Object.clone()
方法。
修改User
類如下所示
public class User implements Serializable, Cloneable {
// 屬性 setter getter toString...
/**
* 調用引用對象的clone(),實現深拷貝
*
* @return
* @throws CloneNotSupportedException
*/
@Override
public Object clone() throws CloneNotSupportedException {
User user = (User) super.clone();
Address address = (Address) this.address.clone();
user.setAddress(address);
return user;
}
}
之前重寫的super.clone()
是不能拷貝引用對象的,那麼調用Address
類的clone()
方法,拷貝address
屬性後再賦值給user
對象。
深拷貝測試類
/**
* 深拷貝 實現地方在User、Address類
*/
static class Cloneable03 {
public static void main(String[] args) throws CloneNotSupportedException {
Address address = new Address("北京");
User user1 = new User("張", 12, address);
User user2 = (User) user1.clone();
System.out.println(user1);
System.out.println(user2);
System.out.println(user1 == user2);
System.out.println(user2.getAddress() == user1.getAddress());
address.setCity("海口");
user1.setAddress(address);
System.out.println(user1);
System.out.println(user2);
}
}
//[name = 張, age = 12, address = 北京]
//[name = 張, age = 12, address = 北京]
//false
//false
//[name = 張, age = 12, address = 海口]
//[name = 張, age = 12, address = 北京]
測試類沒有代碼修改,主要修改在User
、Address
類。
從輸出結果來看,已經實現對address
引用對象的深拷貝。
ArrayList源碼
構造方法
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 默認長度為0的數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存儲 ArrayList 元素的數組緩衝區。 ArrayList 的容量就是這個數組緩衝區的長度。
transient Object[] elementData;
// 給elementData賦值
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}
通過無參構造方法創建集合對象,僅僅將DEFAULTCAPACITY_EMPTY_ELEMENTDATA
(一個默認長度為0的數組)的地址賦值給elementData
(存儲ArrayList元素的數組緩衝區)
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 用於空實例的共享空數組實例。
private static final Object[] EMPTY_ELEMENTDATA = {};
// 構造一個具有指定初始容量的空列表。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 長度大於0,創建指定長度的數組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 長度為0,將空數組的地址賦值給elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
}
根據 ArrayList
構造方法參數創建指定長度的數組,如果指定長度等於0,直接給elementData
賦值EMPTY_ELEMENTDATA
(空數組實例)
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 按照集合的迭代器返回的順序構造一個包含指定集合元素的列表
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;
}
}
// 實現Collection接口
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
}
class Arrays {
// 複製指定的數組,截斷或填充空值(如有必要),使副本具有指定的長度。
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
// 複製指定的數組,截斷或填充空值(如有必要),使副本具有指定的長度。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
// 不管三元運算符的結果如何,都會創建一個新的數組
// 新數組的長度一定是和集合的size一樣
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;
}
// 創建具有指定組件類型和長度的新數組。
public static Object newInstance(Class<?> componentType, int length)
throws NegativeArraySizeException {
return newArray(componentType, length);
}
}
使用ArrayList<User> userList = new ArrayList<User>(list)
構造一個集合時,會進入到此構造方法,通過一個三目表達式判斷是構建一個Object
集合還是newType
中元素類型的集合。
add()
方法
添加單個元素
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// ArrayList的大小
private int size;
// 默認大小為空的實例,共享空數組實例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 集合存元素的數組
Object[] elementData;
// 默認的容量
private static final int DEFAULT_CAPACITY = 10;
// 數組的最大大小,2^31-1-8 = 2147483647-8,一些 VM 在數組中保留一些標題字。嘗試分配更大的數組可能會導致 OutOfMemoryError:請求的數組大小超過 VM 限制
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 將指定元素附加到此列表的末尾
public boolean add(E e) {
// 每次添加元素之前先動態調整數組大小,避免溢出
ensureCapacityInternal(size + 1); // Increments modCount!!
// 每次都會把新添加的元素放到數組末尾,ArrayList順序存放的原因
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 這裏會判斷下當前ArrayList是否為空,為空則先初始化數組,
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 計算ArrayList容量,🍀這裏可以看到當ArrayList為空,且第一次向容器添加元素時,會對ArrayList進行擴容,最小容量為10。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果當前容器為空,那麼獲取初始化數組的大小,數組大小不能小於DEFAULT_CAPACITY(10)
if (elementData == 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) {
// oldCapacity為當前容器大小
int oldCapacity = elementData.length;
// 擴容的核心算法,擴容為原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 因為第一次容器有可能為空,elementData.length==0,newCapacity會小於minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// newCapacity不能大於MAX_ARRAY_SIZE,因為數組能分配的最大空間就是Integer.MAX_VALUE,
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 確定好數組大小後,對數組進行拷貝,Arrays.copyOf的底層是一個native(非Java實現)方法。
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 有些VM會在數組中保留一些標題字,當仍需要更大容量時,則會賦予Integer.MAX_VALUE;當超出時會溢出,報錯OOM。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
}
在指定索引處添加元素
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++;
}
添加元素的時候,首先都要檢查擴容,在add(int index, E element)
方法中多一步操作,就是將指定位置以後的所有元素向後移動一位,留出當前位置用來存放添加的元素。
將集合的所有元素一次性添加到集合
public boolean addAll(Collection<? extends E> c) {
//把有數據的集合轉成數組
Object[] a = c.toArray();
//有數據集合長度賦值給numNew
int numNew = a.length;
//校驗以及擴容
ensureCapacityInternal(size + numNew); // Increments modCount
//真正拷貝的代碼
System.arraycopy(a, 0, elementData, size, numNew);
//集合的長度進行更改
size += numNew;
//根據numNew的值返回是否添加成功
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
//校驗索引
rangeCheckForAdd(index);
//將數據源轉成數組
Object[] a = c.toArray();
//記錄數據源的長度 3
int numNew = a.length;
//目的就是為了給集合存儲數據的數組進行擴容
ensureCapacityInternal(size + numNew);
//numMoved:代表要移動元素的個數 --> 1個
//numMoved: 數據目的(集合list1)的長度-調用addAll的第一個參數 (索引1)
int numMoved = size - index;
//判斷需要移動的個數是否大於0
if (numMoved > 0)
//使用System中的方法arraycopy進行移動
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//才是真正將數據源(list)中的所有數據添加到數據目的(lsit1)
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
addAll
方法原理也是一樣的,多了一步將集合元素添加過程。
set
方法
public E set(int index, E element) {
//校驗索引
rangeCheck(index);
//根據索引取出元素 --> 被替換的元素
E oldValue = elementData(index);
//把element存入到elementData數組中
elementData[index] = element;
//返回被替換的元素
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
set
方法根據索引將元素取出後,再數組中元素替換掉。
get
方法
public E get(int index) {
//校驗索引
rangeCheck(index);
//根據索引獲取數組(集合)中的元素
return elementData(index);
}
get
方法根據索引將元素取出後,直接返回。
remove
方法
remove單個元素
// 🐊移除此列表中指定位置的元素。將任何後續元素向左移動(從它們的索引中減去 1)
public E remove(int index) {
// 索引範圍判斷,超出報IndexOutOfBoundsException
rangeCheck(index);
// 操作數自增1
modCount++;
// oldValue記錄index索引當前值
E oldValue = elementData(index);
// 計算集合需要移動元素的個數
int numMoved = size - index - 1;
if (numMoved > 0)
// 進行數組拷貝,把索引位index後的元素向前移動一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 把集合最後一位元素賦null,儘早讓垃圾回收機制回收
elementData[--size] = null; // clear to let GC do its work
// 將記錄的原索引位元素值返回
return oldValue;
}
// 🐊從此列表中刪除第一次出現的指定元素(如果存在)。如果列表不包含該元素,則它不變。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
// 用==比較null元素
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 用equals比較非null元素
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
// 不存在該元素,不修改本列表,直接返回false
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
}
刪除集合元素
``` // 從此列表中刪除包含在指定集合中的所有元素 public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } // 僅保留此列表中包含在指定集合中的元素。換句話説,從這個列表中刪除所有不包含在指定集合中的元素。 public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); }
// 批量刪除集合元素 private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) // 判斷集合包含元素,刪除集合c外的其他元素 if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. // 當r!=size時,判定上一步出現異常,需要將之前修改過的數組再還原 if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; } ```
removeAll
和retainAll
通過調用的方法是一個,僅通過一個開關實現截然相反的操作,
從Java源碼上分析為什麼LinkedList
隨機訪問比順序訪問要慢這麼多?
// 隨機訪問
for(int i=0;i<list.size();i++) {
list.get(i);
}
// 順序訪問
Iterator<E> it = list.iterator();
while(it.hasNext()){
it.next();
}
LinkedList
的get()
方法源碼
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 返回此列表中指定位置的元素。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 判斷參數是否是現有元素的索引。
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
// ArrayList 的大小
private int size;
// 存儲 ArrayList 元素的數組緩衝區。
transient Object[] elementData;
// 返回指定元素索引處的(非空)節點。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
// index小於長度一半時,是從鏈表頭部往後找
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
// index大於長度一半時,是從鏈表尾部往前找
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
隨機訪問使用list.get(i)
方法,從源碼中我們可以得知,每次list.get(i)
都遍歷找到該元素位置再返回,當我們需要遍歷一次list
,其實list.get(i)
會遍歷很多次,做了重複性工作。
list.iterator()
源碼
```
Iterator
// 判斷nextIndex是否在範圍內 public boolean hasNext() { return nextIndex < size; }
// 獲取下一個元素
public E next() {
// 檢查集合實際修改次數和預期次數是否一樣
checkForComodification();
// 再次判斷是否有元素
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
// 檢查集合實際修改次數和預期次數是否一樣
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
// 🍀在獲取迭代器的時候也會進行折半判斷的過程,但index=0
Node
從迭代器源碼中我們得知,在進行順序訪問時,只在第一次,index=0時進行了一個折半判斷,此後按照順序依次向後傳遞獲取元素,實際只進行了一次遍歷過程。由此可見,LinkedList
的順序遍歷比隨機遍歷快很多。