數(shù)組(Array)
數(shù)組指的就是一組相關類型的變量集合，并且這些變量可以按照統(tǒng)一的方式進行操作，數(shù)組數(shù)據(jù)引用數(shù)據(jù)類型，在堆中進行內存分配，在內存中是連續(xù)存在，大小固定的。
ArrayList
ArrayList可以算是數(shù)組的加強版，其繼承AbstractList接口，實現(xiàn)了List，RandomAccess，Cloneable接口，可序列化。在存儲方面 數(shù)組可以包含基本類型和對象類型，比如：int[],Object[]，ArrayList只能包含對象類型；在空間方面，數(shù)組的空間大小是固定的，空間不夠時不能再次申請，所以需要事前確定合適的空間大小。ArrayList的空間是動態(tài)增長的，如果空間不足，它會創(chuàng)建一個1.5倍大的新數(shù)組，然后把所有元素復制到新數(shù)組，而且每次添加新的元素時會檢測內部數(shù)組的空間是否足夠。
源碼解析
變量
//默認初始容量
private static final int DEFAULT_CAPACITY = 10;
//空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//空數(shù)組與EMPTY_ELEMENTDATA 區(qū)別在于添加第一個元素時，擴充多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//實例數(shù)組對象
transient Object[] elementData; // non-private to simplify nested class access
//數(shù)組大小
private int size;
構造函數(shù)
ArrayList的構造方法有三種：
//自定義初始容量
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//初始化容量大小
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
//容量初始值不能 < 0 小于零會拋出異常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//常用無參構造函數(shù)，默認數(shù)組大小為 10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//創(chuàng)建一個包含collection的ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
//構造大小為size的Object[]數(shù)組賦值給elementData
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 替換空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
}
}
常用函數(shù)(方法)
add函數(shù)
ArrayList調用add()方法添加函數(shù)，源碼為
//在數(shù)組尾部添加元素
public boolean add(E e) {
//長度+1，也就是修改次數(shù)+1 確保內部容量
ensureCapacityInternal(size + 1); // Increments modCount!!
//數(shù)組下標+1 并賦值
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//若數(shù)組元素為空，取最小容量，與默認容量的最大值做為最小容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//明確ArrayList的最小容量
ensureExplicitCapacity(minCapacity);
}
//用于內部優(yōu)化確保空間資源不被浪費
private void ensureExplicitCapacity(int minCapacity) {
//修改統(tǒng)計數(shù)+1，主要用來實現(xiàn)fail-fast機制
modCount++;
// 防止溢出，保證最小容量 > 數(shù)組緩沖區(qū)當前長度
if (minCapacity - elementData.length > 0)
//增加容量
grow(minCapacity);
}
//增加容量以確保它至少可以容納最小容量參數(shù)指定的元素數(shù)量。
private void grow(int minCapacity) {
// 元素長度為舊容量大小
int oldCapacity = elementData.length;
// 新容量= 舊容量 + 舊容量右移一位（舊容量/2）
int newCapacity = oldCapacity + (oldCapacity >> 1);
//判斷新容量與最小容量大小
if (newCapacity - minCapacity < 0)
//最小容量>新容量 ，則新容量為最小容量
newCapacity = minCapacity;
//若新容量 > 最大容量 ，對新容量重新計算
if (newCapacity - MAX_ARRAY_SIZE > 0)
//重新計算新容量
newCapacity = hugeCapacity(minCapacity);
// 擴容并賦值數(shù)組元素
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//若最小容量 < 0 則拋出異常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//最小容量大于 最大數(shù)組長度，則返回int最大值作為容量大小
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
查看復制數(shù)組方法
Arrays.copyOf(elementData, newCapacity)
//Arrays.java類中的方法
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
//復制指定的數(shù)組，截斷或使用null填充（如果需要），以便副本具有指定的長度。
// 對于在原始數(shù)組和副本中均有效的所有索引，兩個數(shù)組將包含相同的值
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);
//從指定的源數(shù)組開始復制數(shù)組，從指定的位置開始到目標數(shù)組的指定位置
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
//內部調用System.arraycopy方法
@FastNative
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
在對應下標出添加數(shù)據(jù)元素
public void add(int index, E element) {
//超出數(shù)據(jù)長度或 小于0 ，則拋出數(shù)組越界異常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
///增加容量以確保它至少可以容納最小容量參數(shù)指定的元素數(shù)量，修改次數(shù)+1
ensureCapacityInternal(size + 1); // Increments modCount!!
//數(shù)組拷貝賦值
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//添加數(shù)組集合
public boolean addAll(Collection<? extends E> c) {
//轉化數(shù)據(jù)
Object[] a = c.toArray();
int numNew = a.length;
//修改次數(shù)+1
ensureCapacityInternal(size + numNew); // Increments modCount
//數(shù)組拷貝賦值
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
通過分析add方法可以發(fā)現(xiàn)ArrayList內部是調用System.arraycopy方法復制數(shù)組。
set函數(shù)
//對應下標設置對應的數(shù)組元素，原來的元素被替換掉并返回替換的數(shù)組元素
public E set(int index, E element) {
//下標 >數(shù)組長度， 則拋出數(shù)組越界異常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//查找索引對應數(shù)組元素
E oldValue = (E) elementData[index];
//數(shù)組元素重新賦值
elementData[index] = element;
return oldValue;
}
get函數(shù)
public E get(int index) {
//下標 >數(shù)組長度， 則拋出數(shù)組越界異常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//根據(jù)下標直接返回對應數(shù)組元素，查找速度快
return (E) elementData[index];
}
remove函數(shù)
//移除數(shù)組下標對應的數(shù)組元素,返回刪除的數(shù)組元素
public E remove(int index) {
//下標 >數(shù)組長度， 則拋出數(shù)組越界異常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//修改次數(shù)統(tǒng)計 +1
modCount++;
//通過索引下標查找對應數(shù)組元素
E oldValue = (E) elementData[index];
//數(shù)組移動個數(shù)
int numMoved = size - index - 1;
if (numMoved > 0)
//后續(xù)數(shù)組元素整體往前移動
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//數(shù)組最后一位元素置空，且長度-1
elementData[--size] = null; // clear to let GC do its work
//返回移除對應數(shù)組元素
return oldValue;
}
//刪除對應元素，如果刪除成功返回true
public boolean remove(Object o) {
if (o == null) { //判斷是否為空
for (int index = 0; index < size; index++)
if (elementData[index] == null) { //若數(shù)組下標對應元素為空則移除null元素
fastRemove(index);
return true;
}
} else {//不為空
for (int index = 0; index < size; index++)
//判斷要刪除的對象在數(shù)組是否存在，存在則刪除
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//私有方法快速刪除數(shù)組元素，該方法與remove(int index)方法類似
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
}
indexof函數(shù)
//查找數(shù)組元素對應下標 ，數(shù)組元素
public int indexOf(Object o) {
if (o == null) { //判斷是否為空
for (int i = 0; i < size; i++)//遍歷
//數(shù)組元素為null返回對應下標
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
//遍歷存在對象o 則返回對應下標
if (o.equals(elementData[i]))
return i;
}
//數(shù)組中不存在，則返回-1
return -1;
}
subList方法
//從ArrayList中截取子列表集合
public List<E> subList(int fromIndex, int toIndex) {
//子列表集合范圍檢測
subListRangeCheck(fromIndex, toIndex, size);
//返回值為一個SubList對象
return new SubList(this, 0, fromIndex, toIndex);
}
SubList為ArrayList的一個內部類
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
//該參數(shù)為父類ArrayList 把自身傳了進來
this.parent = parent;
//開始截取的位置索引
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
//截取后得到的ArrayList長度
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public void add(int index, E e) {
//檢測索引是否越界，越界則拋出異常
rangeCheckForAdd(index);
//檢測數(shù)組列表是否被修改
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
private void checkForComodification() {
//判斷ArrayList的修改次數(shù)與子類的修改次數(shù)是否相等，否則拋出并發(fā)修改異常
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
.....
}
舉個例子：
ArrayList<String> list = new ArrayList<>();
list.add("f1");
list.add("f2");
list.add("f3");
List<String> subList =list.subList(0,2);
subList.add("s1");
subList.remove(1);
System.out.println("list = " + list);
System.out.println("subList = " + subList);
輸出為：
list = [f1, s1, f3]
subList = [f1, s1]
從輸出結果可以看出，截取后的subList是可以增刪查找的，而list是跟隨subList改變而改變的。原因是，在初始化SubList的時候直接把ArrayList 自身傳了進去，在subList進行增刪查找時相當于是對ArrayList自身操作。
那在subList 執(zhí)行增刪方法后還可以操作list增刪嗎？答案：是可以的，不過是有一個前提是 不能再對subList進行任何操作，包括輸出subList對象。
緊接上面的例子
subList.add("s2");
list.add("f4");
System.out.println("list = " + list);
list.remove("s1");
System.out.println("list = " + list);
輸出結果為：
list = [f1, s1, f3]
subList = [f1, s1]
list = [f1, s1, s2, f3, f4]
list = [f1, s2, f3, f4]
如果對list進行操作后又對subList操作將會拋出ConcurrentModificationException,原因是ArrayList進行增刪時修改了modCount ，而 SubList的modCount并沒有被修改，檢測的時候二者不相等所以拋出異常。
總結
- 數(shù)組與ArrayList之間的區(qū)別
- 本文主要分析了ArrayList的常用add，remove等方法的源碼，以及子類SubList的使用方法。
相關文章閱讀
Java集合系列之HashMap源碼分析
Android 源碼解析系列分析
自定義View繪制過程源碼分析
ViewGroup繪制過程源碼分析
ThreadLocal 源碼分析
Handler消息機制源碼分析
Android 事件分發(fā)機制源碼分析
Activity啟動過程源碼分析
Activity中View創(chuàng)建到添加在Window窗口上到顯示的過程源碼分析
