一挟纱、概要
- ArrayList是一個 動態(tài)數(shù)組，線程不安全的黄琼，允許值為null
- 底層數(shù)據(jù)結構是數(shù)組樊销，采用默認構造方法創(chuàng)建時，創(chuàng)建的數(shù)組是默認長度為0的數(shù)組脏款，第一次添加數(shù)據(jù)時會進行判斷，如果數(shù)組長度為默認的空數(shù)組,則創(chuàng)建一個新的數(shù)組裤园，數(shù)組長度為默認值MAX[10撤师，新的長度]，而在Android中數(shù)組的默認最小增加長度為12,當數(shù)組長度需要增加時如果數(shù)組的長度小于12則一次性增加到12拧揽。
- 繼承抽象類AbstractList剃盾，實現(xiàn)了List，RandomAccess淤袜，Cloneable痒谴，Serializable，其中RandomAccess表示快速訪問的能力铡羡。
- 由于是底層結構是數(shù)組积蔚，所以在使用get(i)/set(index, object) 訪問速度較快，時間復雜度為O(1)烦周，但是也是因為數(shù)組的原因尽爆，導致空間效率不高怎顾。
- 添加元素和刪除元素時效率都不高。如果數(shù)組是在最后的位置增加時漱贱，并沒有明顯的效率變化槐雾。當數(shù)組長度需要變化時，則會新創(chuàng)建一個原有長度1.5倍的數(shù)組幅狮，然后將原來的數(shù)組中的元素通過Arrays.copyOf()方法拷貝到新數(shù)組(實際使用的System.arraycopy()方法)募强，此時效率比較低。如果在其他位置添加元素崇摄，添加位置及后面的元素都需要向后移動一位钻注，則有可能涉及到兩次arraycopy，此時效率最低配猫。在刪除時幅恋，則需要將刪除位置以后的元素向前移動一位，則必用到System.arraycopy泵肄。效率低下的原因則是主要受到System.arraycopy()方法的影響捆交。
- 源碼參考的Android-23和Java 1.8
二、構造函數(shù)
Java
一共三個構造函數(shù)
- 默認構造函數(shù)：數(shù)組初始化為長度為0的數(shù)組
- 參數(shù)為initialCapacity的構造函數(shù)：參數(shù)為默認初始化數(shù)組的長度
- 參數(shù)為集合的構造函數(shù)：將數(shù)組為集合轉(zhuǎn)換的數(shù)組腐巢，如果轉(zhuǎn)換的數(shù)組不是Object對象品追，就將數(shù)組轉(zhuǎn)換成Object數(shù)組
//存儲元素的數(shù)組
transient Object[] elementData; // non-private to simplify nested class access
//數(shù)組的長度
private int size;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 默認的數(shù)組 ，這個數(shù)組為了區(qū)分容量為0創(chuàng)建的數(shù)組EMPTY_ELEMENTDATA
* 在添加的時候進行了區(qū)分冯丙，如果是這個數(shù)組肉瓦，則將數(shù)組重新?lián)Q成相應長度的空數(shù)組
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with the specified initial capacity.
* 帶有初始容量的構造函數(shù)
* @param initialCapacity the initial capacity of the list：初始化數(shù)組容量
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
//初始化容量必須大于0
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
* 默認的構造函數(shù)，創(chuàng)建了一個空數(shù)組胃惜，
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 將數(shù)組轉(zhuǎn)換成Object數(shù)組
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
//本質(zhì)還是調(diào)用System.arraycopy
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
//上述 Arrays.copyOf調(diào)用的方法
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
//判斷是否是Object方法泞莉，如果不是Object，則調(diào)用反射創(chuàng)建數(shù)組
@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;
}
Android
- 還是三個構造函數(shù)船殉，但是構造函數(shù)具體實現(xiàn)不太一樣
- 關于EmptyArray 可以參考：鏈接
/**
* Constructs a new instance of {@code ArrayList} with the specified
* initial capacity.
*
* @param capacity
* the initial capacity of this {@code ArrayList}.
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
/**
* Constructs a new {@code ArrayList} instance with zero initial capacity.
*/
public ArrayList() {
array = EmptyArray.OBJECT;
}
/**
* Constructs a new instance of {@code ArrayList} containing the elements of
* the specified collection.
*
* @param collection
* the collection of elements to add.
*/
public ArrayList(Collection<? extends E> collection) {
if (collection == null) {
throw new NullPointerException("collection == null");
}
Object[] a = collection.toArray();
//判斷轉(zhuǎn)換后的數(shù)組是否是Object數(shù)組
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
都調(diào)用的System.arraycopy方法鲫趁，該方法是native方法，針對基本數(shù)據(jù)類型(非String)在Android的System中有相應的重載類型利虫，重載算法只針對了copy長度小于等于32時挨厚，使用了java代碼進行copy，如果大于32時糠惫，依然使用了相應的native的算法。
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
三硼讽、增加元素
3.1 增加一個元素
Java
核心點在于容量超過時巢价，新容量的計算，一般為老容量的1.5倍、或者是默認容量蹄溉、或者是老容量+1想罕、或者是Integer.MAX_VALUE - 8傀缩，或者是Integer.MAX_VALUE
//添加一個元素
public boolean add(E e) {
//確保內(nèi)部容量(為當前的size+1)
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Android
與java代碼中的差異在于容量的擴充饭宾，以及空數(shù)組變成有值數(shù)組的數(shù)組的默認容量
//數(shù)組的最小擴充容量
private static final int MIN_CAPACITY_INCREMENT = 12;
@Override
public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {//如果數(shù)組已經(jīng)滿了
//新創(chuàng)建一個數(shù)組彤叉，數(shù)組長度為老容量+[最小擴充容量或老容量的一半]
//s<(MIN_CAPACITY_INCREMENT/2)一般只有【空數(shù)組、默認容量比較小棉胀、默認構造函數(shù)參數(shù)是collection的情況下發(fā)生】
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
//將老數(shù)組元素copy到新數(shù)組中
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;//修改次數(shù)法瑟，該屬性是在AbstractList中。唁奢。霎挟。
return true;
}
3.2 在相應位置增加一個元素
Java
核心點在于數(shù)組的copy
public void add(int index, E element) {
rangeCheckForAdd(index);//檢查index是否越界
//容量判斷，并未修改size
ensureCapacityInternal(size + 1); // Increments modCount!!
//從index位置開始麻掸，長度為size-index酥夭，size為數(shù)組中有意義的元素個數(shù)，copy到數(shù)組的index+1位置脊奋。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;//容量相加
}
Android
與Java的區(qū)別在于數(shù)組擴容之后元素的copy熬北，java是擴容是就將數(shù)組元素copy到新數(shù)組，然后將index位置及之后的元素依次向后移動一個位置诚隙，而Android代碼就是在新建一個數(shù)組讶隐，然后從index開始分成兩部分copy
@Override
public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {//判斷是否越界
throwIndexOutOfBoundsException(index, s);
}
//如果數(shù)組容量足夠，直接copy即可
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
//數(shù)組的容量不夠久又，將數(shù)組擴展到新容量
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
//將老數(shù)組數(shù)據(jù)copy到新數(shù)組中
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
3.3 將集合中的元素全部添加到末尾
Java
如果添加c的容量超過了老的數(shù)組的一般大小巫延，那么直接擴容到新的最小容量[old容量+c的容量]，但是有新問題就是地消，如果隨后還添加的話炉峰，那么還需要擴容。
另外就是集合長度為0的情況犯建，也進行了相應的數(shù)據(jù)copy
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();//將集合轉(zhuǎn)換成數(shù)組
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount讲冠，確保數(shù)組容量足夠
System.arraycopy(a, 0, elementData, size, numNew);//將元素copy到新的數(shù)組里
size += numNew;//更新size
return numNew != 0;
}
Android
解決了java代碼中存在的問題
@Override
public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();//轉(zhuǎn)換成數(shù)組
int newPartSize = newPart.length;//新部分的大小
if (newPartSize == 0) {//新長度為0直接返回
return false;
}
Object[] a = array;//原有數(shù)據(jù)
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {//新的長度，大于原有長度
//容量擴充為适瓦，總容量-1的1.5倍，不知道為什么使用總容量-1,也有可能是將下標放置進去了谱仪。玻熙。。
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];//創(chuàng)建新數(shù)組
System.arraycopy(a, 0, newArray, 0, s);//將老數(shù)據(jù)copy到新數(shù)組中
array = a = newArray;//數(shù)組賦值
}
System.arraycopy(newPart, 0, a, s, newPartSize);//將添加的數(shù)據(jù)copy到新數(shù)組中
size = newSize;
modCount++;
return true;
}
3.4 將集合中的元素添加到相應的位置
Java
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);//檢查是否越界
Object[] a = c.toArray();
int numNew = a.length;
//保證數(shù)組內(nèi)部容量
ensureCapacityInternal(size + numNew); // Increments modCount疯攒，
//需要移動的數(shù)量
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);//移動或者復制數(shù)組
//將新的數(shù)據(jù)a copy到集合對應的數(shù)據(jù)中
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
Android
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {//判斷數(shù)組是否越界
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();//將添加的集合轉(zhuǎn)換成數(shù)組
int newPartSize = newPart.length;
if (newPartSize == 0) {//如果添加的數(shù)據(jù)集合的長度為0就返回
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {//判斷是否有足夠的容量嗦随，如果有直接將后面的數(shù)據(jù)移動到新的位置
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
// 擴充后的容量
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];//新的數(shù)組
//分兩段copy數(shù)據(jù)
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
//copy新數(shù)據(jù)
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}
3.5 公共方法
Java
//默認的容量
private static final int DEFAULT_CAPACITY = 10;
//確保內(nèi)部容量為最小容量minCapacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//如果是使用空參數(shù)構造函數(shù)創(chuàng)建的數(shù)組，則將容量修改為【默認容量、當前容量】中的最小值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//確保明確容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//修改次數(shù)枚尼，在迭代器中使用贴浙，如果修改次數(shù)不明確，那么會發(fā)生一個異呈鸹校【ConcurrentModificationException】,想了解具體的作用可以看源碼的注釋, 該屬性是在AbstractList中崎溃，感覺是在迭代器循環(huán)查找時，插入和刪除操作可能會報錯
// overflow-conscious code
//如果最小容量大于數(shù)組的長度盯质，需要增加容器的容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//數(shù)組的最大數(shù)值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//增加數(shù)組容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//老容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量為老容量的1.5倍
if (newCapacity - minCapacity < 0)//新容量小于最小容量袁串，當老容量為0時
newCapacity = minCapacity;//新容量賦值為最小容量
if (newCapacity - MAX_ARRAY_SIZE > 0)//新容量大于最大容量時
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//將元素copy到新容量的數(shù)組中
elementData = Arrays.copyOf(elementData, newCapacity);
}
//巨大容量
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//最大容量大于設定的上限時，將容量修改為Integer.MAX_VALUE
// 一般都不會超呼巷，如果超過了囱修，此時的ArrayList計算就會比較慢了。王悍。破镰。可以考慮換種集合用了压储。鲜漩。。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Android
private static int newCapacity(int currentCapacity) {
//容量擴展
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
3.6 總結
共有add(E e)渠脉，add(int index,E e) 宇整，addAll(Collection<? extends E> c)，allAll(int index,Collection<? extends E> c)
步驟
- 判斷index是否越界(有index參數(shù))
- 判斷是否需要擴容芋膘，如果需要就將容量擴展為原來總容量一半鳞青，如果不滿足需求，就擴容到總容量为朋，在Android中則是擴容到總容量-1的一半臂拓。。习寸。胶惰，擴容后復制數(shù)組
- 關于擴容后復制數(shù)組，在add(int index,...)中Android和Java有實現(xiàn)差異霞溪，主要差異在數(shù)組是否是分段復制孵滞。Java在復制數(shù)組時直接擴容后復制完，然后再將index及后續(xù)后移鸯匹，相當于后半段的數(shù)據(jù)復制了兩遍坊饶，Android中的實現(xiàn)解決了這個問題。
- 關于modCount殴蓬，Java是在判斷是否需要擴容就增加匿级，Android一般是在新的數(shù)據(jù)賦值后增加。
四、刪除元素
4.1 移除一個指定位置上的元素
Java
public E remove(int index) {
rangeCheck(index);//判斷是否越界
modCount++;//修改次數(shù)
E oldValue = elementData(index);//獲取元素
int numMoved = size - index - 1;//需要移動的元素個數(shù)
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//將index位置之后的元素依次向前copy
elementData[--size] = null; // clear to let GC do its work痘绎，將最后的元素置空津函，方便回收
return oldValue;//移除的元素
}
Android
@Override
public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {//判斷是否越界
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked")
E result = (E) a[index];//獲取元素
System.arraycopy(a, index + 1, a, index, --s - index);//移動元素
a[s] = null; // Prevent memory leak，方便回收
size = s;
modCount++;
return result;//移除的元素
}
4.2 移除一個指定的元素
移除第一個相等的元素
Java
public boolean remove(Object o) {
if (o == null) {//如果為null 移除第一個null
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {//如果不為null移除第一個object孤页，通過equals判斷是否相等
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)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//移動所有的后面的元素一位
elementData[--size] = null; // clear to let GC do its work尔苦，清除最后一位元素
}
Android
@Override
public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {//元素不為空
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {//元素相等
System.arraycopy(a, i + 1, a, i, --s - i);//后置元素左移
a[s] = null; // Prevent memory leak//末尾置空
size = s;//修改size
modCount++;
return true;
}
}
} else {//元素為空
for (int i = 0; i < s; i++) {
if (a[i] == null) {//如果為空
System.arraycopy(a, i + 1, a, i, --s - i);//后置元素左移
a[s] = null; // Prevent memory leak，末尾置空
size = s;
modCount++;
return true;
}
}
}
return false;//移除失敗
}
4.3 移除某一段元素
移除一段元素
Java
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;//移動的元素個數(shù)
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);//將toIndex的后置元素左移
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);//新的size
for (int i = newSize; i < size; i++) {//從新的size開始到老的size散庶，將之間的元素置空
elementData[i] = null;
}
size = newSize;
}
Android
@Override
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex == toIndex) {//位置相等蕉堰，返回
return;
}
Object[] a = array;
int s = size;
//開始位置大于size，結束位置大于size悲龟，開始位置大于結束位置屋讶，拋出數(shù)組越界異常
if (fromIndex >= s) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " >= size " + size);
}
if (toIndex > s) {
throw new IndexOutOfBoundsException("toIndex " + toIndex
+ " > size " + size);
}
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " > toIndex " + toIndex);
}
// 將toIndex所有后置元素，向左移動须教，移動到fromIndex
System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromIndex;//移動后皿渗，最后一個有效元素的位置距離s的差
//rangeSize = s-(fromIndex+s-toIndex)
Arrays.fill(a, s - rangeSize, s, null);//將所有的無效位置置空
size = s - rangeSize;
modCount++;
}
4.4 移除集合中所有元素
Java
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 {
//如果complement為true，則是將c中包含有當前集合中的所有元素前移
//如果complement為false轻腺，則是將c中不包含當前集合中的所有元素前移
// 在循環(huán)結束后 w及之后為集合中w位置及之后的元素
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//保持兼容一致性因為contains是抽象方法乐疆，有可能為發(fā)生異常
if (r != size) {//表示發(fā)生了異常
//將異常發(fā)生位置及以后的數(shù)據(jù)移到需要的元素最后w位置
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;//修改w，后續(xù)元素因為沒有發(fā)生判斷贬养，所以也是需要的
}
if (w != size) {
//如果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;
}
Android
Android中的ArrayList沒有重寫這個方法仰美，如果調(diào)用這個API，調(diào)用的是AbstractCollection的API
public boolean removeAll(Collection<?> collection) {
boolean result = false;
Iterator<?> it = iterator();
//使用迭代器儿礼，如果包含在collection中就移除
while (it.hasNext()) {
if (collection.contains(it.next())) {
it.remove();
result = true;
}
}
return result;
}
4.5 總結
- 刪除操作一定會修改modeCount咖杂，且可能會涉及到數(shù)組的復制，相對低效
- Android 中ArrayList竟然沒有重寫RemoveAll方法
五蚊夫、修改元素
設置某一個位置的元素
不會修改modCount
Java
public E set(int index, E element) {
rangeCheck(index);//越界檢查
E oldValue = elementData(index);//獲取元素
elementData[index] = element;//將元素修改為新值
return oldValue;//返回舊值
}
Android
@Override
public E set(int index, E object) {
Object[] a = array;
if (index >= size) {//越界檢查
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked")
E result = (E) a[index];//獲取元素
a[index] = object;//將元素修改為新值
return result;//返回舊值
}
六诉字、查詢元素
獲取某一位置的元素
Java
不會修改modCount
public E get(int index) {
rangeCheck(index);//判斷是否越界
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Android
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
七、包含元素
Java
public boolean contains(Object o) {
return indexOf(o) >= 0;//看位置信息是否>-1知纷，
}
public int indexOf(Object o) {
if (o == null) {//如果為空壤圃，就查找第一個空元素的位置
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {//如果不為空，就查找第一個相等(equals)元素的位置
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//倒序查詢琅轧，包含三
public int lastIndexOf(Object o) {
if (o == null) {//如果為空埃唯，就查找第一個空元素的位置
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {//如果不為空，就查找第一個相等(equals)元素的位置
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Android
@Override
public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {//如果不為null
for (int i = 0; i < s; i++) {//循環(huán)判斷是否有有相等(equals)的元素
if (object.equals(a[i])) {
return true;
}
}
} else {//如果為null鹰晨，循環(huán)判斷數(shù)組中是有有null元素
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
@Override
public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {//如果不為null
for (int i = 0; i < s; i++) {//則正序循環(huán)判斷是否有相等(equals)的元素
if (object.equals(a[i])) {
return i;//如果有，返回位置信息
}
}
} else {//如果為null，循環(huán)判斷數(shù)組中是有有null元素
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;//如果有模蜡，返回位置信息
}
}
}
return -1;//如果沒有漠趁，返回-1
}
@Override
public int lastIndexOf(Object object) {
Object[] a = array;
if (object != null) {//如果不為null，則正序循環(huán)判斷是否有相等(equals)的元素
for (int i = size - 1; i >= 0; i--) {
if (object.equals(a[i])) {
return i;//如果有忍疾，返回位置信息
}
}
} else {//如果為null闯传，倒序循環(huán)判斷數(shù)組中是有有null元素
for (int i = size - 1; i >= 0; i--) {
if (a[i] == null) {
return i;//如果有，返回位置信息
}
}
}
return -1;//如果沒有卤妒，返回-1
}
八甥绿、集合的size
集合的size不等于集合中數(shù)組的長度
Java
public int size() {
return size;
}
Android
@Override
public int size() {
return size;
}
九、判空
判斷size是否為空
Java
public boolean isEmpty() {
return size == 0;
}
Android
@Override
public boolean isEmpty() {
return size == 0;
}
十则披、其他常用方法
10.1清空
Java
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;//循環(huán)置空
size = 0;
}
Android
@Override
public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);//使用Arrays填充空數(shù)據(jù)
size = 0;
modCount++;
}
}
10.2 轉(zhuǎn)換成數(shù)組
Java
核心點調(diào)用Arrays的copy功能
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)//如果copy到的數(shù)組長度較小共缕，重新創(chuàng)建數(shù)組copy
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);//長度足夠，直接copy
if (a.length > size)
a[size] = null;//將數(shù)組的size位置置空士复，判斷copy的數(shù)據(jù)截止位置
return a;
}
Android
@Override
public Object[] toArray() {
int s = size;
Object[] result = new Object[s];
System.arraycopy(array, 0, result, 0, s);//直接copy到新數(shù)組
return result;
}
@Override
public <T> T[] toArray(T[] contents) {
int s = size;
if (contents.length < s) {//傳入的數(shù)組長度不夠图谷，直接創(chuàng)建一個長度足夠的數(shù)組
@SuppressWarnings("unchecked") T[] newArray
= (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
contents = newArray;
}
System.arraycopy(this.array, 0, contents, 0, s);//長度足夠，直接copy
if (contents.length > s) {
//將size位置設為空阱洪，表示這個位置之前的數(shù)據(jù)是copy的數(shù)組
contents[s] = null;
}
return contents;
}
十一便贵、迭代
11.1 普通迭代器Iterator
實現(xiàn)了Iterator接口的迭代器
Java
//獲取迭代器
public Iterator<E> iterator() {
return new Itr();
}
//使用私有內(nèi)部類獲取迭代器
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
//期望的修改次數(shù)冗荸，在使用迭代器循環(huán)過程中承璃，如果調(diào)用ArrayList.remove和ArrayList.add方法，會報錯蚌本，防止在迭代器循環(huán)過程中增刪元素
int expectedModCount = modCount;
//是否有下一個
public boolean hasNext() {
return cursor != size;//游標不等于size
}
//獲取下一個元素
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//檢查是否ArrayList中元素修改過
int i = cursor;
if (i >= size)//防止游標越界
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//數(shù)組賦值
if (i >= elementData.length)//防止越界
throw new ConcurrentModificationException();
cursor = i + 1;//將游標向后移動一位
return (E) elementData[lastRet = i];//將當前位置(老游標位置)賦值給lastRet盔粹，根據(jù)當前位置取值，將該位置的值返回魂毁。
}
//移除最后一個取到的元素
public void remove() {
if (lastRet < 0)//如果沒有取過值玻佩，自然無法移除值，拋出異常
throw new IllegalStateException();
checkForComodification();
try {
//將最后取出的元素位置的元素移除席楚，會改變修改次數(shù)
ArrayList.this.remove(lastRet);
cursor = lastRet;//將游標移到上一次取出的位置
lastRet = -1;//將取出位置置為-1咬崔，防止連續(xù)移除
expectedModCount = modCount;//重新設置期望修改次數(shù)
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//配合Lambda表達式使用，遍歷
@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 = 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();
}
//檢查是否ArrayList中元素修改過烦秩，如果修改過會報異常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
Android
不采取游標方式進行迭代垮斯，而是采取剩余量這個說法
@Override
public Iterator<E> iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<E> {
/** Number of elements remaining in this iteration */
private int remaining = size;//默認剩余量為ArrayList的size
/** Index of element that remove() would remove, or -1 if no such elt */
private int removalIndex = -1;//移除的位置
/** The expected modCount value */
private int expectedModCount = modCount;//期望修改次數(shù)
public boolean hasNext() {
return remaining != 0;//剩余量不等于0
}
@SuppressWarnings("unchecked")
public E next() {
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;//剩余量
if (ourList.modCount != expectedModCount) {//判斷迭代過程中是否修改過
throw new ConcurrentModificationException();
}
if (rem == 0) {//剩余量為0
throw new NoSuchElementException();
}
remaining = rem - 1;//剩余量-1，
return (E) ourList.array[removalIndex = ourList.size - rem];//返回size-舊剩余量位置的元素只祠，將上一元素位置記錄下來兜蠕，移除時使用
}
public void remove() {
Object[] a = array;
int removalIdx = removalIndex;//上一元素位置
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (removalIdx < 0) {//上一元素位置<0，表示沒有對應元素抛寝，不可移除
throw new IllegalStateException();
}
//將移除位置后置元素copy到移除位置
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak熊杨，將最后元素置空
removalIndex = -1;//移除位置置為-1曙旭，放置連續(xù)remove
expectedModCount = ++modCount;//修改modCount
}
}
11.2 List特有迭代器ListIterator
該迭代器可以倒序遍歷，也就是向前遍歷
Java
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)//防止數(shù)組越界
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);//設置游標默認位置的迭代器
}
//返回游標位置默認為0的迭代器
public ListIterator<E> listIterator() {
return new ListItr(0);
}
//內(nèi)部類晶府，繼承普通迭代桂躏，實現(xiàn)了ListItertor接口
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;//設置游標位置
}
//是否有前置元素，游標不等于0
public boolean hasPrevious() {
return cursor != 0;
}
//下一個位置川陆，游標位置
public int nextIndex() {
return cursor;
}
//前一個位置
public int previousIndex() {
return cursor - 1;
}
//前置元素
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();//檢查是否遍歷過程中是否修改過
int i = cursor - 1;//將位置設置為游標位-1
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;//將游標移動
return (E) elementData[lastRet = i];//獲取舊游標位置元素剂习，將最后取出的位置修改為對應位置
}
//設置元素
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//檢查是否遍歷過程中，是否修改過數(shù)組
try {
ArrayList.this.set(lastRet, e);//設置最后遍歷位置的元素
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//在游標位置较沪，添加元素
public void add(E e) {
checkForComodification();
try {
int i = cursor;//將位置設為游標位
ArrayList.this.add(i, e);//在該位置添加元素
cursor = i + 1;//修改游標
lastRet = -1;//最后取出位置-1
expectedModCount = modCount;//更新修改次數(shù)
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
Android
ArrayList中沒有實現(xiàn)listIterator鳞绕，調(diào)用API則是調(diào)用AbstractList中的API
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(int location) {
return new FullListIterator(location);
}
private class SimpleListIterator implements Iterator<E> {
int pos = -1;//泛游標，不同于游標尸曼，也可以理解為游標们何，指代的是最后變化(添加、查詢骡苞、刪除)的元素
int expectedModCount;
int lastPosition = -1;//最后修改位置
SimpleListIterator() {
expectedModCount = modCount;
}
public boolean hasNext() {
return pos + 1 < size();//泛游標是否已經(jīng)指向了最后一個元素
}
public E next() {
if (expectedModCount == modCount) {
try {
E result = get(pos + 1);//獲取pos+1位置的元素
lastPosition = ++pos;//最后修改pos位置和最后修改位置
return result;
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
}
public void remove() {
if (this.lastPosition == -1) {
throw new IllegalStateException();
}
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
try {
AbstractList.this.remove(lastPosition);//移除最后修改位置的元素
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
expectedModCount = modCount;//設置修改次數(shù)
if (pos == lastPosition) {//泛游標=最后修改位置
pos--;//泛游標-1
}
lastPosition = -1;//修改最后位置
}
}
private final class FullListIterator extends SimpleListIterator implements ListIterator<E> {
FullListIterator(int start) {
//判斷最后位置垂蜗，
if (start >= 0 && start <= size()) {
pos = start - 1;//為了契合游標概念。解幽。贴见。
} else {
throw new IndexOutOfBoundsException();
}
}
public void add(E object) {
if (expectedModCount == modCount) {
try {
//在泛游標+1位置設置元素
AbstractList.this.add(pos + 1, object);
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
pos++;//泛游標移動
lastPosition = -1;//最后位置
if (modCount != expectedModCount) {
expectedModCount = modCount;
}
} else {
throw new ConcurrentModificationException();
}
}
//是否有元素
public boolean hasPrevious() {
return pos >= 0;
}
//下一個位置
public int nextIndex() {
return pos + 1;
}
//前序遍歷
public E previous() {
if (expectedModCount == modCount) {
try {
E result = get(pos);//獲取pos位置元素
lastPosition = pos;//修改最后元素位置
pos--;//游標--
return result;
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
}
//向前移動游標
public int previousIndex() {
return pos;
}
public void set(E object) {
if (expectedModCount == modCount) {
try {
AbstractList.this.set(lastPosition, object);//設置最后修改位置元素
} catch (IndexOutOfBoundsException e) {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
}
十二、遍歷
- 采用普通for循環(huán)躲株，這種遍歷方式效率最高片部，因為有了隨機快速訪問能力
ArrayList as = new ArrayList();
.......
for(int i=0;i<as.size();i++){
System.out.println(as.get(i));
}
- for-each遍歷，這種遍歷使用范圍霜定，只能是迭代數(shù)組或者實現(xiàn)了Iterable的對象
can only iterate over an array or an instance of java.lang.Iterable
ArrayList ls = new ArrayList();
......
for(Object o:ls){
System.out.println(o);
}
- 使用普通迭代器遍歷档悠，效率較低
ArrayList<String> as = new ArrayList<>();
......
Iterator<String> it = as.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
- 使用ListIterator，這個迭代器可以前后循環(huán)
ArrayList<String> as = new ArrayList<>();
......
ListIterator<String> lit = as.listIterator();
while(lit.hasNext()){
System.out.println(lit.next());
}
while(lit.hasPrevious()){
System.out.println(lit.previous());
}
十三望浩、總結
- 普通的增加辖所、刪除會修改modCount，它的主要功能是在迭代器迭代過程中判斷是否進行過增加和刪除操作磨德，因為這兩種操作會導致迭代異常缘回。
- 所有涉及到數(shù)組copy的操作都會導致效率降低，其中增加擴容典挑、中間某一位置增加元素酥宴、定點刪除、批量刪除您觉、等操作都會產(chǎn)生數(shù)組copy拙寡。所以在查詢情況比較多建議使用ArrayList，例如Android開發(fā)中的數(shù)據(jù)展示
- 和Vector的區(qū)別有以下幾點
3.1 Vector 從JDK1.0就存在琳水，ArrayList是從JDK1.2添加的
3.2 Vector是線程安全的肆糕，因為其中一些方法使用synchronized關鍵字來保證線程安全般堆。
1.0加鎖的方法有，具體如下：
public synchronized void addElement(E obj)
public synchronized void insertElementAt(E obj, int index)
public synchronized boolean removeElement(Object obj)
public synchronized void removeElementAt(int index)
public synchronized void removeAllElements()
public synchronized void setElementAt(E obj, int index)
public synchronized E elementAt(int index)
這些方法是1.0創(chuàng)建Vector就有的擎宝。
還有一些是實現(xiàn)了Collection(Since 1.2)的方法郁妈，這些方法是在1.2中實現(xiàn)的，其中加鎖的具體如下：
public synchronized boolean add(E e)
public synchronized boolean addAll(Collection<? extends E> c)
public synchronized boolean addAll(int index, Collection<? extends E> c)
public synchronized E remove(int index)
public synchronized void removeAllElements()
public synchronized E set(int index, E element)
public synchronized E get(int index)
但是有一些方法雖說表面是不加鎖的绍申，但是還是調(diào)用的加鎖方法如：
public void add(int index, E element) {
insertElementAt(element, index);
}
public boolean remove(Object o) {
return removeElement(o);
}
public void clear() {
removeAllElements();
}
3.3 擴容：Vector可以設置容量的默認增長量，如果不設置默認增長量顾彰，那么默認擴容量為原來數(shù)組的長度极阅，也就是說擴容是容量變?yōu)閮杀丁?/p>
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
