ArrayList是我們開發中最常用到的集合，但是很多人對它的源碼並不了解，導致面試時，面試官問的稍微深入的問題，就無法作答，今天我們一起來探究一下ArrayList源碼。
1. 簡介
- ArrayList底層是數組，允許元素是null，能够動態擴容
- size、isEmpty、get、set、add 等方法時間複雜度都是 O (1)
- 非線程安全，並發修改時，會拋出ConcurrentModificationException
2. 初始化
// 初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空數組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默認空數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存儲元素的數組
transient Object[] elementData;
// 無參初始化，默認是空數組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 有參初始化，指定容量大小
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);
}
}
切記：無參初始化的時候，默認是空數組，並沒有初始化容量大小，容量是在第一次添加元素的才進行初始化。
3. 添加元素
public boolean add(E e) {
// 確保數組容量够用，size是元素個數
ensureCapacityInternal(size + 1);
// 直接賦值
elementData[size++] = e;
return true;
}
// 確保數組容量够用
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 計算所需最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果數組等於空數組，最小容量為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) {
int oldCapacity = elementData.length;
// oldCapacity >> 1 是把oldCapacity除以2，意思是1.5倍擴容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴容後的容量小於最小容量，擴容後的容量就等於最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果擴容後的容量大於Integer的最大值，就用Integer最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 擴容並賦值給原數組
elementData = Arrays.copyOf(elementData, newCapacity);
}
可以看到：
- 擴容是以原容量的1.5倍擴容，並不是翻倍擴容
- 最大容量是Integer的最大值
- 添加元素時，沒有對元素校驗，可以是null
再看一下數組拷貝的邏輯，這裏都是Arrays類裏面的方法了：
/**
* @param original 原數組
* @param newLength 新的容量大小
*/
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) {
// 創建一個新數組，容量是新的容量大小
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;
}
最終調用了System類的數組拷貝方法，是native方法：
/**
* @param src 原數組
* @param srcPos 原數組的開始比特置
* @param dest 目標數組
* @param destPos 目標數組的開始比特置
* @param length 被拷貝的長度
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
4. 删除單個元素
public boolean remove(Object o) {
// 判斷要删除的元素是否為null
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)
// 從index+1比特置開始拷貝，也就是後面的元素整體向左移動一個比特置
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 數組最後一個元素賦值為null，防止會導致內存泄漏
elementData[--size] = null;
}
可以知道，删除元素，就是遍曆數組，循環比較是否等於目標值。如果相等，就把該比特置後面的元素整體向左移動一個比特置，再把數組最後一個元素賦值為null。
5. 批量删除
// 批量删除ArrayList和集合c都存在的元素
public boolean removeAll(Collection<?> c) {
// 非空校驗
Objects.requireNonNull(c);
// 批量删除
return batchRemove(c, false);
}
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++)
if (c.contains(elementData[r]) == complement)
// 把需要保留的元素左移
elementData[w++] = elementData[r];
} finally {
// 當出現异常的時候，可能不相等
if (r != size) {
// 1：可能是上面的for循環出現了异常
// 2：可能是其它線程添加了元素
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 把不需要保留的元素賦值為null
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
可以知道，批量删除的時候，只會進行一次數組拷貝，比用for循環單個删除效率更高，所以删除一批元素的時候，盡量用removeAll()方法。
5. 總結
本文分析了ArrayList的初始化、put、add、remove、動態擴容等方法的底層源碼，相信大家對於ArrayList有了更深層次的了解，下篇一塊學習一下LinkedList的源碼。
竟然還有人說ArrayList是2倍擴容，今天帶你手撕ArrayList源碼的更多相關文章
- 刨死你系列——手撕ArrayList
不多BB,直接上代碼: public class MyArrayList { //創建數組對象 private Object[] elements; //已使用數組長度 private int siz ...
- Java - ArrayList源碼分析
java提高篇(二一)-----ArrayList 一.ArrayList概述 ArrayList是實現List接口的動態數組,所謂動態就是它的大小是可變的.實現了所有可選列錶操作,並允許包括 nul ...
- Java泛型底層源碼解析-ArrayList,LinkedList,HashSet和HashMap
聲明:以下源代碼使用的都是基於JDK1.8_112版本 1. ArrayList源碼解析 <1. 集合中存放的依然是對象的引用而不是對象本身,且無法放置原生數據類型,我們需要使用原生數據類型的包 ...
- Java小白集合源碼的學習系列：ArrayList
ArrayList源碼學習 本文基於JDK1.8版本,對集合中的巨頭ArrayList做一定的源碼學習,將會參考大量資料,在文章後面都將會給出參考文章鏈接,本文用以鞏固學習知識. ArrayList的 ...
- Java8集合框架——ArrayList源碼分析
java.util.ArrayList 以下為主要介紹要點,從 Java 8 出發: 一.ArrayList的特點概述 二.ArrayList的內部實現:從內部屬性和構造函數說起 三.ArrayLis ...
- 集合之ArrayList（含JDK1.8源碼分析）
一.ArrayList的數據結構 ArrayList底層的數據結構就是數組,數組元素類型為Object類型,即可以存放所有類型數據.我們對ArrayList類的實例的所有的操作(增删改查等),其底層都 ...
- JAVA面試題 手寫ArrayList的實現，在筆試中過關斬將?
面試官Q1:可以手寫一個ArrayList的簡單實現嗎? 我們都知道ArrayList是基於數組實現,如果讓你實現JDK源碼ArrayList中add().remove().get()方法,你知道如何 ...
- (一)ArrayList集合源碼解析
一.ArrayList的集合特點 問題 結 論 ArrayList是否允許空 允許 ArrayList是否允許重複數據 允許 ArrayList是否有序 有序 ArrayList是否線程安全 ...
- 源碼分析二(ArrayList與LinkedList的區別)
一:首先看一下ArrayList類的結構體系: public class ArrayList<E> extends AbstractList<E> implements Lis ...
- JDK12下的ArrayList源碼解讀 與 Vector的對比
ArrayList源碼閱讀. //測試代碼實現如下 private static void arrayList() { ArrayList<String> list = new Array ...
隨機推薦
- 在java項目中使用AES256 CBC加密
首先要注意一點,默認的JDK是不支持256比特加密的,需要到Oracle官網下載加密增强文件(Java Cryptography Extension (JCE) Unlimited Strength J ...
- HDU 4831 Scenic Popularity （段樹）
Scenic Popularity Problem Description 臨近節日,度度熊們近期計劃到室外遊玩公園.公園內部包含了非常多的旅遊景點區和歇息區,因為旅遊景點非常熱門,導致景點區和歇息區 ...
- 數據結構中，幾種樹的結構錶示方法（C語言實現）
//***************************************** //樹的多種結構定義 //***************************************** # ...
- 創建和注册自定義 HTTP 模塊
本演練演示自定義 HTTP 模塊的基本功能. 對於每個請求,都需要調用 HTTP 模塊以響應 BeginRequest 和 EndRequest 事件. 因此,該模塊在處理請求之前和之後運行. 如果 ...
- HBase快照
CDH是Cloudera的完全開源分布式Apache Hadoop及相關項目(包括Apache HBase).CDH的當前版本(4.2)引入的一個HBase新特性最近加入到了主幹中,允許用戶對指定錶進 ...
- php删除文件或文件夾
<?php function deleteDir($dir) { if (!$handle = @opendir($dir)) { return false; } while (false != ...
- Java 裁剪圖片
package com.test; import java.awt.image.BufferedImage; import java.io.File; import javax.imageio.Ima ...
- Reducing and Profiling GPU Memory Usage in Keras with TensorFlow Backend
keras 自適應分配顯存 & 清理不用的變量釋放 GPU 顯存 Intro Are you running out of GPU memory when using keras or ten ...
- transfer function
線性變化後,往往希望進行非線性變化,常用的非線性變化函數有Sigmoid,Tanh,ReLU.會發現,經過這三個函數變化後,Tensor的維度並不發生變化. tanh(雙曲正切函數):
- What’s a service mesh? And why do I need one?
https://buoyant.io/2017/04/25/whats-a-service-mesh-and-why-do-i-need-one/ Update 2018-02-06: Since t ...
