網站首頁 編程語言 正文
簡介
ArrayList是List接口的一個實現類，它是一個集合容器，我們通常會通過指定泛型來存儲同一類數據，ArrayList默認容器大小為10，自身可以自動擴容，當容量不足時，擴大為原來的1.5倍，和上篇文章的Vector的最大區別應該就是線程安全了，ArrayList不能保證線程安全，但我們也可以通過其他方式來實現線程安全。
ArrayList源碼講解
開頭部分代碼
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
@java.io.Serial
//序列化uid
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; //其他代碼}
這部分可做出有關ArrayList的相關結構，如下圖所示
初始化
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 {
elementData = EMPTY_ELEMENTDATA;
}
} //此處為copyOf運行代碼
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")
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;
}
以上代碼為ArrayList的初始化，分為三種方式：
1.為給定容量的初始化，傳入參數為數組的初始化長度，當該參數大于等于0時，進行初始化，當該參數小于0時，拋出異常
2.過于簡單
3.首先通過c.toArray()得到了集合c對應的數據數組，如果c也是ArrayList，直接將c.toArray()賦給elementData，而關于toArray的關鍵代碼如上代碼中關于copyOf的部分所示，從該段代碼中可知此處的Arrays.copyOf調用的是三參數版本的函數。這個三參數的copyOf函數比較復雜，作用就是返回一個指定的newType類型的數組，這個數組的長度是newLength，值從original拷貝而來。拷貝的功能由System.arraycopy( )完成：如果newLength大于原數組的長度，多出來的元素初始化為null；如果小于原數組長度，將會進行截斷操作。在這里，兩參版本調用三參版本的三個參數為original, newLength, original.getClass()，故得到的數組元素類型和原數組類型一致，長度為newLength，數據由原數組復制而來。
總之，ArrayList的無參版toArray( )返回了一個和elemantData一模一樣的拷貝數組。所以判斷c也是ArrayList對象時，直接令elemantData 為c.toArray( )了。否則，會執行elementData = Arrays.copyOf(a, size, Object[].class)。經過上面的分析，三參的copyOf( )是返回一個數據內容和a一模一樣的數組，但是數組類型轉為Object[ ]類型。之所以有這條語句，猜想可能是某些集合的toArray( )方法，返回的數組不是Object[ ]類型，比方說用一個類繼承ArrayList，并且重寫toArray( )方法，讓它返回一些別的類型。
擴容
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
//核心部分
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
private Object[] grow() {
return grow(size + 1);
}
//newLength部分
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
// put code cold in a separate method
return hugeLength(oldLength, minGrowth);
}
}
private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength + minGrowth;
if (minLength < 0) { // overflow
throw new OutOfMemoryError(
"Required array length " + oldLength + " + " + minGrowth + " is too large");
} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
return SOFT_MAX_ARRAY_LENGTH;
} else {
return minLength;
}
} public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
關于擴容部分，private Object[] grow(int minCapacity)為核心部分，故我們先看這部分，if(oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)部分說明當該數組不是還未初始化的數組時，用newLength以及位運算來進行相應的擴容，而newLength相應的代碼已經貼在了上面，讓我們來進行具體分析：此處的minGrowth在grow部分為“minCapacity - oldCapacity”，即滿足我們需要的容量，此處的prefGrowth在grow部分為“oldCapacity >> 1”，即原來容量的一半，當沒有溢出時，擴容時所擴的容量就是這兩者中最大的那個，而當溢出時，調用hugeLength()來滿足minGrowth，如果還時溢出則最多只能給到 Integer.MAX_VALUE - 8 這個量。
那么當計算好長度之后，return elementData = Arrays.copyOf(elementData, newCapacity)，即得到一個長度改變，元素類型和原數組相同的新數組。而當該數組不滿足oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA這個條件時，進行數組的初始化。
增加元素
一個元素
//在尾部添加一個元素
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length) //此處s為size的意思
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
} //在指定位置添加元素
public void add(int index, E element) {
rangeCheckForAdd(index); modCount++;
final int s; Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1, s - index);
elementData[index] = element; size = s + 1;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
此處分為兩個部分，一是向尾部添加一個元素的add()，如上面所示，當size與elementData.length相等時，說明數組中無多余空間進行添加，故進行擴容操作。將你要添加的值放入elementData[s]即數組的尾部，然后將size加一，這里的modCount是用來計算ArrayList中的結構性變化次數。
二是在指定位置添加元素的add()，如上面所示，首先對你想要添加的元素的位置進行判定
一堆元素
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
//elementData剩余容量不足則進行擴容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
//上文有提到的關于arraycopy的代碼，此處為從數組尾部添加元素
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
public boolean addAll(int index, Collection<? extends E> c) {
//上文提到的判定語句
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
//要添加進來的元素的數量
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
//計算要將多少元素向后移動
int numMoved = s - index;
if (numMoved > 0)
//要在index位置，新增numNew個元素，所以從index位置開始，往后挪numNew位，一共有numMoved個元素需要挪動
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
//空出來的位置即為要添加的元素的位置
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
關于添加一堆元素時的代碼與之前的代碼較為相似，故此處直接在代碼中注釋標出，應該很好理解。
刪除元素
一個元素
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
public staticint checkIndex(int index, int length) { return Preconditions.checkIndex(index, length, null);}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}//刪除指定元素方法
public boolean remove(Object o) { final Object[] es = elementData; final int size = this.size; int i = 0; // 正序找對應元素下標 found: { if (o == null) { for (; i < size; i++) if (es[i] == null) break found; } else { for (; i < size; i++) if (o.equals(es[i])) break found; } return false; } // 找到了，調用fastRemove，進行刪除 fastRemove(es, i); return true;}
此處的刪除是按照下標刪，首先檢查index是否合法，接著取到oldValue值也就是要刪的元素值，然后調用fastRemove( )函數。在fastRemove里，首先自增modCount，再判斷要刪的元素是不是elemantData的第size個元素（也就是實際上的最后一個元素），如果是，不需要挪動元素操作，直接賦值為null即可，否則，還需要將刪除位置之后的元素都往前挪一位。
當然也有個刪除指定元素的方法，具體如上面**public boolean remove(Object o)**所示。
一堆元素
//刪除集合c中的所有元素public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}//保留集合c中的所有元素
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true, 0, size);
}//核心代碼
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) { //判斷集合c是否為空
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
} //w用于寫入保留的元素
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e; //當這個元素可以保留時，將其賦給es[]
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally { //相關善后工作
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
private void shiftTailOverGap(Object[] es, int lo, int hi) { //善后工作相關代碼 System.arraycopy(es, hi, es, lo, size - hi);
// 從索引hi開始，有size-hi個元素需要往左挪，這些元素依次挪到lo以及lo之后的位置
// 它們都向左挪了hi-lo個單位
// 挪動之后，原先的索引size-1的元素，對應的是size-1-(hi-lo)，這個索引之后的元素都賦值為null for (int to = size, i = (size -= hi - lo); i < to; i++) es[i] = null;}
此處的關于多個元素的操作分為刪除多個元素和保留多個元素，而這兩個操作均需要調用 “batchRemove“ ，故進行關于其的具體分析。
“batchRemove“ 首先進行了變量”r“的聲明，接著是一段for循環，而不管是“removeAll”還是“retainAll”都是from = 0 ，end = size，即從頭到尾用r作為索引遍歷數組，當c.contains(es[r]) != complement時break出去。對于“removeAll”，其complement為false，故當c.contains(es[r])為true的時候退出循環，即c中包含es[r]，即找到了要刪除的元素，此時的r為第一個要刪除的元素的索引。
以此類推，對于“retainAll”，r為要保留的第一個元素的索引。關于后面w的部分，w是第一個要刪的元素索引，找到要保留的元素，則把索引w的元素賦值為此元素，再自增w。這樣子r一遍遍歷完成后，要保留的元素也都向前移動好了。最后再進行善后工作，具體代碼如上所示，詳細過程已做注釋。
修改元素
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public static
int checkIndex(int index, int length) {
return Preconditions.checkIndex(index, length, null);
}
public static <X extends RuntimeException>
int checkIndex(int index, int length,
BiFunction<String, List<Number>, X> oobef) {
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
return index;
}
修改元素部分也與之前大同小異，首先對index是否合法進行判斷，成功后再對這個元素的值進行修改，并返回舊值
查詢元素
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
關于此處，首先是indexOf函數，就是根據元素找索引，調用”indexOfRange“，從左往右找，找到第一個索引就返回；在ArrayList中還有個lastIndexOf，與前面提到的查找正好相反，為從右往左找。
還有一些其他較為簡單的函數，這里就不一一列出了，下一篇試著分析下迭代器。格式沒怎么調。
以上就是Android開發中的部分技術點，屬于數據結構與算法這塊。Android開發需要進階的東西有很多，我們該如何讓進階自己必須了解自己技術層在那個位置；
總結
ArrayList優點
- ArrayList底層以數組實現，是一種隨機訪問模式，再加上它實現了
- RandomAccess接口，因此查找也就是get的時候非常快。
- ArrayList在順序添加一個元素的時候非常方便，只是往數組里面添加了一個元素而已。
- 根據下標遍歷元素，效率高
- 根據下標訪問元素，效率高
- 可以自動擴容，默認為每次擴容為原來的1.5倍
ArrayList的缺點
- 插入和刪除元素的效率不高
- 根據元素的值查找元素的下標需要遍歷整個元素數組，效率不高
- 線程不安全
原文鏈接：https://juejin.cn/post/7160285079657250846
相關推薦
- 2021-11-25 vc控制臺程序關閉事件時的處理方式及注意點詳解_C 語言
- 2022-08-01 MongoDB基礎之文檔操作_MongoDB
- 2022-06-09 ASP.NET?Core使用EF創建模型(必需和可選屬性、最大長度、并發標記、陰影屬性)_實用技巧
- 2023-07-27 px自動轉rem
- 2022-05-28 Golang空接口與類型斷言的實現_Golang
- 2023-06-17 Flask中特殊裝飾器的使用_python
- 2022-08-21 Mac包管理器Homebrew的安裝方法_其它綜合
- 2022-09-08 Pandas如何將Timestamp轉為datetime類型_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速