ArrayList
ArrayList是List接口的 可變數(shù)組的實現(xiàn)。實現(xiàn)了所有可選列表操作,并允許包括 null
在內(nèi)的所有元素崎页。除了實現(xiàn) List
接口外,此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小腰埂。ArrayList
繼承自 AbstractList<E>
飒焦,這是一個抽象類對一些基礎的list
操作做了一些封裝.實現(xiàn)了RandomAccess 標記接口,表明可以實現(xiàn)快速隨機訪問.實現(xiàn)了Cloneable
接口的實現(xiàn)表示該容器具有Clone函數(shù)操作盐固,Serializable
是序列化荒给。
每個ArrayList
實例都有一個容量,該容量是指用來存儲列表元素的數(shù)組的大小刁卜。它總是至少等于列表的大小志电。隨著向ArrayList
中不斷添加元素,其容量也自動增長蛔趴。自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝挑辆,因此,如果可預知數(shù)據(jù)量的大小孝情,就可在構造ArrayList
實例時指定其容量鱼蝉。
在添加大量元素前,應用程序也可以使用ensureCapacity
操作來增加ArrayList
實例的容量箫荡,這可以減少遞增式再分配的數(shù)量魁亦。
注意,此實現(xiàn)不是同步的羔挡。如果多個線程同時訪問一個ArrayList實例洁奈,而其中至少一個線程從結構上修改了列表,那么它必須保持外部同步绞灼。
ArrayList這個數(shù)據(jù)結構比較簡單利术,總體來說,ArrayList底層結構是數(shù)組低矮,他的很多方法都是從數(shù)組上面演變而來的印叁。
下面我們先來看一下ArrayList中的一些初始值
//通過ArrayList實現(xiàn)的接口可知,其支持隨機訪問,能被克隆轮蜕,支持序列化
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//序列版本號
private static final long serialVersionUID = 8683452581122892189L;
//默認初始容量
private static final int DEFAULT_CAPACITY = 10;
//空實例的共享空數(shù)組實例
private static final Object[] EMPTY_ELEMENTDATA = {};
//被用于默認大小的空實例的共享數(shù)組實例昨悼。
//與EMPTY_ELEMENTDATA的區(qū)別是:當我們向數(shù)組中添加第一個元素時,知道數(shù)組該擴充多少肠虽。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Object[]類型的數(shù)組幔戏,保存了添加到ArrayList中的元素玛追。ArrayList的容量是該Object[]類型數(shù)組的長度
* 當?shù)谝粋€元素被添加時税课,任何空ArrayList中的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA將會被
* 擴充到DEFAULT_CAPACITY(默認容量)。
*/
transient Object[] elementData; //沒有被私有化是為了簡化內(nèi)部類訪問
// ArrayList的大腥省(指其所含的元素個數(shù))
private int size;
// 記錄被修改的次數(shù)
protected transient int modCount = 0;
// 數(shù)組的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
}
elementData
是"Object[] 類型的數(shù)組"韩玩,它保存了添加到ArrayList
中的元素。實際上陆馁,elementData
是個動態(tài)數(shù)組找颓,我們能通過構造函數(shù) ArrayList(intinitialCapacity)
來執(zhí)行它的初始容量為initialCapacity
;如果通過不含參數(shù)的構造函數(shù)ArrayList()
來創(chuàng)建ArrayList
叮贩,則elementData
的容量默認是10击狮。elementData
數(shù)組的大小會根據(jù)ArrayList
容量的增長而動態(tài)的增長,具體的增長方式請看這里
構造函數(shù)
ArrayList
提供了三種方式的構造器益老”肱睿可以構造一個默認初始容量為10的空列表、構造一個指定初始容量的空列表以及構造一個包含指定collection
的元素的列表捺萌。
這些元素按照該collection的迭代器返回的順序排列的档冬。
// 構造一個指定初始容量的空列表
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);
}
}
// 構造一個默認初始容量為10的空列表
public ArrayList() { //這里并沒有初始化,jdk 1.8之后是在進行add操作后初始化
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 構造一個包含指定collection的元素的列表桃纯,這些元素按照該collection的迭代器返回的順序排列的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray()可能不會正確地返回一個 Object[]數(shù)組酷誓,那么使用Arrays.copyOf()方法
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else { // 如果指定的collection為空
this.elementData = EMPTY_ELEMENTDATA;
}
}
使用無參構造器,默認初始容量為什么是10态坦?
初始時:this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; size = 0;
向數(shù)組中添加第一個元素時盐数,add(E e)方法中調(diào)用了ensureCapacityInternal(size + 1)方法,即ensureCapacityInternal(1)伞梯;
在ensureCapacityInternal(int minCapacity)方法中玫氢,minCapacity=DEFAULT_CAPACITY=10,然后再調(diào)用ensureExplicitCapacity(minCapacity)方法壮锻,即ensureExplicitCapacity(10)琐旁;
在ensureExplicitCapacity(minCapacity)方法中調(diào)用grow(minCapacity)方法,即grow(10)猜绣,此處為真正具體的數(shù)組擴容的算法灰殴,在此方法中,通過elementData = Arrays.copyOf(elementData, 10)具體實現(xiàn)了elementData數(shù)組初始容量為10的構造。
添加元素
// 在數(shù)組末尾加上一個元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 進行擴容檢查
elementData[size++] = e;
return true;
}
// 在數(shù)組的指定位置添加元素
public void add(int index, E element) {
rangeCheckForAdd(index); // 檢查index是否越界
ensureCapacityInternal(size + 1); // 進行擴容檢查
// 對數(shù)據(jù)進行復制操作牺陶,空出index位置伟阔,并插入element,將源數(shù)組中從index位置開始后的size-index個元素統(tǒng)一后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++; // 元素個數(shù)加1
}
// 按照指定collection集合的迭代器所返回的元素順序掰伸,將該collection中的所有元素添加到列表的尾部
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); // 將collection轉換為數(shù)組類型
int numNew = a.length; // collection中的元素個數(shù)
ensureCapacityInternal(size + numNew); // 進行擴容檢查
System.arraycopy(a, 0, elementData, size, numNew); // 將數(shù)組a[0,...,numNew-1]復制到數(shù)組elementData[size,...,size+numNew-1]
size += numNew;
return numNew != 0;
}
// 按照指定collection集合的迭代器所返回的元素順序皱炉,將該collection中的所有元素添加到列表的指定位置
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); // 檢查index是否越界
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 進行擴容檢查
// 將數(shù)組elementData[index,...,index+numMoved-1]復制到elementData[index+numMoved,...,index+2*numMoved-1]
//將源數(shù)組中從index位置開始的后numMoved個元素統(tǒng)一后移numNew位
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 將數(shù)組a[0,...,numNew-1]復制到數(shù)組elementData[index,...,index+numNew-1]完成數(shù)據(jù)的插入
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
擴容相關
// 用于自定義設置ArrayList的容量
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
// 進行擴容檢查
private void ensureCapacityInternal(int minCapacity) {
//第一次add操作初始化,如果為空ArrayList狮鸭,那么初始化容量為10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//判斷是否需要擴容
ensureExplicitCapacity(minCapacity);
}
//判斷是否需要擴容
private void ensureExplicitCapacity(int minCapacity) {
//modCount這個參數(shù)運用到了 fail-fast 機制
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 擴容
}
// 擴容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//newCapacity為以前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判斷容量是否到達long int 最大臨界值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 對數(shù)組進行復制處理
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 檢查是否超過最大容量 0x7fffffff 合搅,是否拋出異常
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 E remove(int index) {
rangeCheck(index); //數(shù)組越界檢查
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1; //計算數(shù)組需要復制的數(shù)量
if (numMoved > 0) //將index后的數(shù)據(jù)都向前移一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //help GC
return oldValue;
}
// 刪除指定內(nèi)容的元素(只刪除第一個匹配成功的)
public boolean remove(Object o) {
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后面的元素整體向前移動一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // help GC
}
//清空ArrayList灾部,將全部的元素設為null
public void clear() {
modCount++;
for (int i = 0; i < size; i++) // help GC
elementData[i] = null;
size = 0;
}
//刪除ArrayList中從fromIndex到toIndex(區(qū)間--左閉右開)之間所有的元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex; //需向前移動的元素的個數(shù)
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// help GC
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
//刪除ArrayList中包含在指定容器c中的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c); //檢查指定的對象c是否為空
return batchRemove(c, false);
}
//移除ArrayList中不包含在指定容器c中的所有元素,與removeAll(Collection<?> c)正好相反
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c); //檢查指定的對象c是否為空
return batchRemove(c, true);
}
// 根據(jù)complement的值刪除元素
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0; //讀寫雙指針 w是重新存元素時的索引惯退,r是原來的索引
boolean modified = false;
try {
//遍歷數(shù)組赌髓,并檢查這個集合是否包含對應的值,移動要保留的值到數(shù)組前面催跪,w最后值為要保留的元素的數(shù)量
//簡單點:若保留锁蠕,就將相同元素移動到前段;若刪除懊蒸,就將不同元素移動到前段
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) //判斷指定容器c中是否含有elementData[r]元素
elementData[w++] = elementData[r];
}finally {//確保異常拋出前的部分可以完成期望的操作荣倾,而未被遍歷的部分會被接到后面
//r!=size表示可能出錯了:c.contains(elementData[r])拋出異常
if (r != size) {
System.arraycopy(elementData, r,elementData, w,size - r);
w += size - r;
}
//如果w==size:表示全部元素都保留了,所以也就沒有刪除操作發(fā)生榛鼎,所以會返回false逃呼;反之,返回true者娱,并更改數(shù)組
//而w!=size的時候抡笼,即使try塊拋出異常,也能正確處理異常拋出前的操作黄鳍,因為w始終為要保留的前段部分的長度推姻,數(shù)組也不會因此亂序
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;//改變的次數(shù)
size = w; //新的大小為保留的元素的個數(shù)
modified = true;
}
}
return modified;
}
removeAll和retainAll方法:實現(xiàn)刪除或保留ArrayList
中包含Collection c中的的元素。
這兩個方法都用到batchRemove
方法(boolean complement
使得batchRemove
方法得到了重用)
下面以removeAll為例框沟,分析batchRemove(c, false)
遍歷elementData
如果集合c中包含elementData
的元素e藏古,則c.contains(elementData[r])為true
,if不成立忍燥,if結束拧晕;如果c不包含elementData
的元素e,則if成立梅垄,將此元素e賦值給elementData[w++] (即elementData
保留了c中沒有的元素厂捞,也就是刪除了c中存在的所有元素。)
執(zhí)行finally
finally
是不管try中結果如何都會執(zhí)行的。if(r!=size)靡馁,則將elementData
未參加比較的元素arraycopy
到elementData
后面欲鹏;新索引w加上剛arraycopy
的數(shù)目;if (w != size)臭墨,此時w還不等于size
赔嚎,則將w后的元素移除.只有執(zhí)行了if (w != size)(事實上只要c中含有elementData的元素,w肯定不等于size)胧弛,才令modified = true尤误,才說明remove成功,返回true叶圃,否則返回false袄膏。
ArrayList中還有一個用于節(jié)約數(shù)組內(nèi)存空間,縮小容量的方法
// 因為容量常常會大于實際元素的數(shù)量掺冠。內(nèi)存緊張時,可以調(diào)用該方法刪除預留的位置码党,調(diào)整容量為元素實際數(shù)量德崭。
// 如果確定不會再有元素添加進來時也可以調(diào)用該方法來節(jié)約空間
public void trimToSize() {
modCount++;
// length是數(shù)組長度,size表示數(shù)組內(nèi)元素個數(shù)
// size<length那么就說明數(shù)組內(nèi)有空元素揖盘,進行縮小容量操作
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
去掉預留元素的位置眉厨。返回一個新數(shù)組,新數(shù)組不含null兽狭,數(shù)組的size和elementData.length相等憾股,以節(jié)省空間。此函數(shù)可避免size很小但elementData.length很大的情況箕慧。
ArrayList會每次增長會預申請多一點空間服球,1.5倍,這樣就會出現(xiàn)當size() = 10的時候颠焦,ArrayList已經(jīng)申請了15空間斩熊, trimToSize就是刪除多余的5,只留10伐庭。
或許有人會有疑問:
調(diào)用Arrays.copyOf復制size長度的元素到elementData粉渠,而且由源碼看應該是從0復制到size處,那么如果我之前調(diào)用過add(int index, E element)呢圾另?比如霸株,list={1,2集乔,3去件,null,null,4箫攀,null肠牲,null},如果調(diào)用trimToSize返回的應該是list={1靴跛,2缀雳,3,null}(因為size=4)梢睛。其實上面這種情況不會發(fā)生的肥印,因為調(diào)用add(int index, E element)時,會檢查index的合法性绝葡,所以list的元素肯定是相鄰的深碱,而不會出現(xiàn)上述這種中間出現(xiàn)null的情況。
修改元素
// 將指定位置的元素改為指定的值
public E set(int index, E element) {
rangeCheck(index); // 檢查index是否越界
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
查找元素
//判斷ArrayList中是否包含Object(o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回一個值在數(shù)組首次出現(xiàn)的位置藏畅,會根據(jù)是否為null使用不同方式判斷敷硅。不存在就返回-1。時間復雜度為O(N)
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//返回一個值在數(shù)組最后一次出現(xiàn)的位置愉阎,不存在就返回-1绞蹦。時間復雜度為O(N)
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//返回指定位置的值,因為是數(shù)組榜旦,所以速度特別快
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//返回指定位置的值幽七,但是會檢查這個位置數(shù)否超出數(shù)組長度
public E get(int index) {
rangeCheck(index);
return elementData(index); //實質(zhì)上return (E) elementData[index]
}
序列化
//保存數(shù)組實例的狀態(tài)到一個流(即它序列化)。寫入過程數(shù)組被更改會拋出異常
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
int expectedModCount = modCount;
s.defaultWriteObject(); //執(zhí)行默認的反序列化/序列化過程溅呢。將當前類的非靜態(tài)和非瞬態(tài)字段寫入此流
// 寫入大小
s.writeInt(size);
// 按順序寫入所有元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
//上面是寫澡屡,這個就是讀了。
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 執(zhí)行默認的序列化/反序列化過程
s.defaultReadObject();
// 讀入數(shù)組長度
s.readInt();
if (size > 0) {
ensureCapacityInternal(size);
Object[] a = elementData;
//讀入所有元素
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
為什么要自定義序列化咐旧、反序列化機制呢驶鹉?
由于ArrayList實質(zhì)上是一個動態(tài)數(shù)組,往往數(shù)組中會有空余的空間休偶,如果采用默認的序列化機制梁厉,那些空余的空間會作為null寫入本地文件或者在網(wǎng)絡中傳輸,耗費了不必要的資源踏兜。所以词顾,ArrayList使用自定義序列化機制,僅寫入索引為【0碱妆,size)的有效元素以節(jié)省資源
迭代器
//返回ListIterator肉盹,開始位置為指定參數(shù)
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
//返回ListIterator,開始位置為0
public ListIterator<E> listIterator() {
return new ListItr(0);
}
//返回普通迭代器
public Iterator<E> iterator() {
return new Itr();
}
//通用的迭代器實現(xiàn)
private class Itr implements Iterator<E> {
int cursor; //游標疹尾,下一個元素的索引上忍,默認初始化為0
int lastRet = -1; //上次訪問的元素的位置
int expectedModCount = modCount;//迭代過程不允許修改數(shù)組骤肛,否則就拋出異常
//是否還有下一個
public boolean hasNext() {
return cursor != size;
}
//下一個元素
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//檢查數(shù)組是否被修改
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1; //向后移動游標
return (E) elementData[lastRet = i]; //設置訪問的位置并返回這個值
}
//刪除元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//檢查數(shù)組是否被修改
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@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++]);
}
cursor = i;
lastRet = i - 1;
checkForComodification();
}
//檢查數(shù)組是否被修改
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//ListIterator迭代器實現(xiàn)
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
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;
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();
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;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
Iterator與ListIterator的區(qū)別:
- Iterator可以應用于所有的集合,Set窍蓝、List和Map和這些集合的子類型腋颠。而ListIterator只能用于List及其子類型;
- Iterator只能實現(xiàn)順序向后遍歷吓笙,ListIterator可實現(xiàn)順序向后遍歷和逆向(順序向前)遍歷淑玫;
- Iterator只能實現(xiàn)remove操作,ListIterator可以實現(xiàn)remove操作面睛,add操作絮蒿,set操作。
其他方法
//返回ArrayList的大腥(元素個數(shù))
public int size() {
return size;
}
//判斷ArrayList是否為空
public boolean isEmpty() {
return size == 0;
}
//返回此 ArrayList實例的淺拷貝(元素本身沒有被復制土涝,復制過程數(shù)組發(fā)生改變會拋出異常)
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
/*
淺克隆就是我們所看到的Arrays.copyOf, System.arraycopy幌墓,數(shù)組是新的但壮,但是里面N個元素全是引用的舊的。
淺拷貝(影子克隆):只復制基本類型克锣。
深拷貝(深度克隆):基本類+對象茵肃。
*/
//返回一個包含ArrayList中所有元素的數(shù)組
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// 返回一個數(shù)組,使用運行時確定類型袭祟,該數(shù)組包含在這個列表中的所有元素(從第一到最后一個元素)
// 返回的數(shù)組容量由參數(shù)和本數(shù)組中較大值確定
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 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);
if (a.length > size)
a[size] = null;
return a;
}
ArrayList相關問題
Integer.MAX_VALUE - 8 這里為什么要減去8?
主要是考慮到不同的JVM,有的VM會在加入一些數(shù)據(jù)頭,當擴容后的容量大于MAX_ARRAY_SIZE,我們會去比較最小需要容量和MAX_ARRAY_SIZE做比較,如果比它大, 只能取Integer.MAX_VALUE,否則是Integer.MAX_VALUE -8污茵。
這個是從jdk1.7開始才有的
jdk1.8的無參構造函數(shù)和之前版本的構造函數(shù)有什么區(qū)別?
jdk1.6
public ArrayList() {
this(10);
}
jdk1.7
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
jdk1.8
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
對比下可以看出:jdk1.6的無參構造方法(默認構造方法)構造的ArrayList的底層數(shù)組elementData大屑喊埂(容量)默認為10甚带;從1.7開始,無參構造方法構造的ArrayList的底層數(shù)組elementData大小默認為0胆绊。
java集合類在jdk1.7版本基本上都有一種改動:懶初始化。懶初始化指的是默認構造方法構造的集合類欧募,占據(jù)盡可能少的內(nèi)存空間(對于ArrayList來說压状,使用空數(shù)組來占據(jù)盡量少的空間,不使用null是為了避免null判斷)跟继,在第一次進行包含有添加語義的操作時种冬,才進行真正的初始化工作。
1.7開始的ArrayList舔糖,默認構造方法構造的實例娱两,底層數(shù)組是空數(shù)組,容量為0金吗,在進行第一次add/addAll等操作時才會真正給底層數(shù)組賦非empty的值十兢。如果add/addAll添加的元素小于10趣竣,則把elementData數(shù)組擴容為10個元素大小,否則使用剛好合適的大泻滴铩(例如遥缕,第一次addAll添加6個,那么擴容為10個宵呛,第一次添加大于10個的单匣,比如24個,擴容為24個烤蜕,剛好合適)
1.8版本封孙,默認構造的實例這個行為沒有改變,只是用的數(shù)組名字變了讽营。
jdk1.6中擴容算法的缺陷
(由于jdk1.7和jdk1.8在擴容算法方面差別不大虎忌,所以下面沒有嚴格區(qū)分)
jdk1.6
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
從上面的代碼可以看出jdk1.6的ensureCapacity方法只是簡單進行了邏輯上的操作,沒有過多考慮int型溢出的問題橱鹏,從1.7開始對這個進行了完善膜蠢。
而且沒考慮入?yún)inCapacity可能因為int溢出變?yōu)樨摂?shù)。這個方法可以外部手動調(diào)用莉兰,手動擴容傳入負數(shù)這個肯定是應該攔截掉的挑围。但是自動擴容會因為int溢出產(chǎn)生負數(shù),碰到這種情況時應該特殊處理糖荒,而不是什么都不做杉辙,等著后面拋出一個ArrayIndexOutOfBoundsException。
還有就是下面這句代碼會造成過早溢出
int newCapacity = (oldCapacity * 3)/2 + 1;
雖然上面這行代碼和1.7開始的oldCapacity + (oldCapacity >> 1) 差不多捶朵,都是相當于1.5倍蜘矢,但實際上是有
區(qū)別的。
這里主要有兩個區(qū)別
第一個區(qū)別是jdk1.6的乘除運算的數(shù)學結果比后面一個大1比如oldCapacity=10综看,1.6的
算法得到16品腹,1.7開始的算法得到15,這個影響不大红碑;
第二個區(qū)別就是兩者在數(shù)字比較大時運算結果不一樣舞吭,比如
oldCapacity=10^9,這個數(shù)和Integer.MAX_VALUE位數(shù)一樣析珊,用1.6的算法得到的會是錯誤的-647483647羡鸥,用
1.7的則是正確的1500000000,這時候明明可以1.5倍擴容唾琼,但是jdk1.6卻用的是按需擴容兄春。
ensureCapacity(稱之為手動,是因為此方法是public的锡溯,可以外部手動調(diào)用)赶舆。
在1.6版本是只有這個手動的方法哑姚,內(nèi)部自動操作也是調(diào)用這個方法,1.7開始進行了區(qū)分芜茵,并且進一步改進了擴容操作叙量。
從1.7開始將內(nèi)部擴容和外部可以調(diào)用的擴容方法分開了,通過源碼可以看出:外部調(diào)用的手動擴容方法ensureCapacity要多一個判斷條件 minCapacity > minExpand九串,這個判斷條件攔截掉負數(shù)的minCapacity绞佩,這樣調(diào)用內(nèi)部擴容ensureCapacityInternal方法時,minCapacity一定是正數(shù)猪钮;內(nèi)部擴容方法直接就用minCapacity - elementData.length > 0判斷品山,此條件可以檢測出int型溢出,碰到溢出最后會拋出一個OOM錯誤烤低。jdk1.7用OOM肘交,這比jdk1.6用ArrayIndexOutOfBoundsException更好,因為此時數(shù)組大小超出了虛擬機對數(shù)組的限制扑馁,虛擬機無法處理這種情況了涯呻,拋出一個ERROR是合理的。
使用這行代碼
newCapacity = oldCapacity + (oldCapacity >> 1);
這行代碼不僅僅是使用位運算加快執(zhí)行速度腻要,上面說了复罐,這種做法才是對的,是真正的1.5倍雄家。不僅僅因為那一個大小的差別效诅,更重要的是避免過早出現(xiàn)int溢出的情況,保證了內(nèi)部自動擴容會盡量按規(guī)定的策略執(zhí)行趟济。同時整個擴容處理流程中多增加了幾處if判斷填帽,對各種情況處理更加完善。
為什么ArrayList自動容量擴充選擇擴充1.5倍咙好?
這種算法構造出來的新的數(shù)組長度的增量都會比上一次大( 而且是越來越大) ,避免頻繁newInstance 的情況褐荷。
為什么ArrayList 不適合頻繁插入和刪除操作勾效?
由上面分析的增加刪除方法可以看出在ArrayList中經(jīng)常會調(diào)用 System.arraycopy 這個效率很低的操作來復制數(shù)組,所以導致ArrayList在插入和刪除操作中效率不高叛甫。