国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Java集合之ArrayList源碼解析

W4n9Hu1 / 1948人閱讀

摘要:數組的大小會根據容量的增長而動態的增長,具體的增長方式請看這里構造函數提供了三種方式的構造器。這些元素按照該的迭代器返回的順序排列的。

原文地址

ArrayList

ArrayListList接口的 可變數組的實現。實現了所有可選列表操作,并允許包括 null 在內的所有元素。除了實現 List接口外,此類還提供一些方法來操作內部用來存儲列表的數組的大小。ArrayList繼承自 AbstractList,這是一個抽象類對一些基礎的list操作做了一些封裝.實現了RandomAccess 標記接口,表明可以實現快速隨機訪問.實現了Cloneable接口的實現表示該容器具有Clone函數操作,Serializable是序列化。

每個ArrayList實例都有一個容量,該容量是指用來存儲列表元素的數組的大小。它總是至少等于列表的大小。隨著向ArrayList中不斷添加元素,其容量也自動增長。自動增長會帶來數據向新數組的重新拷貝,因此,如果可預知數據量的大小,就可在構造ArrayList實例時指定其容量。

在添加大量元素前,應用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量,這可以減少遞增式再分配的數量。

注意,此實現不是同步的。如果多個線程同時訪問一個ArrayList實例,而其中至少一個線程從結構上修改了列表,那么它必須保持外部同步。

ArrayList這個數據結構比較簡單,總體來說,ArrayList底層結構是數組,他的很多方法都是從數組上面演變而來的。

下面我們先來看一下ArrayList中的一些初始值

//通過ArrayList實現的接口可知,其支持隨機訪問,能被克隆,支持序列化
public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
{
    //序列版本號
    private static final long serialVersionUID = 8683452581122892189L;

  //默認初始容量
    private static final int DEFAULT_CAPACITY = 10;

    //空實例的共享空數組實例
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //被用于默認大小的空實例的共享數組實例。
    //與EMPTY_ELEMENTDATA的區別是:當我們向數組中添加第一個元素時,知道數組該擴充多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * Object[]類型的數組,保存了添加到ArrayList中的元素。ArrayList的容量是該Object[]類型數組的長度
     * 當第一個元素被添加時,任何空ArrayList中的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA將會被
     * 擴充到DEFAULT_CAPACITY(默認容量)。
     */
     transient Object[] elementData; //沒有被私有化是為了簡化內部類訪問

    // ArrayList的大小(指其所含的元素個數)
    private int size;
    
    // 記錄被修改的次數  
    protected transient int modCount = 0;  
    
    // 數組的最大值  
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8  

}

elementData 是"Object[] 類型的數組",它保存了添加到ArrayList中的元素。實際上,elementData是個動態數組,我們能通過構造函數 ArrayList(intinitialCapacity)來執行它的初始容量為initialCapacity;如果通過不含參數的構造函數ArrayList()來創建ArrayList,則elementData的容量默認是10。elementData數組的大小會根據ArrayList容量的增長而動態的增長,具體的增長方式請看這里

構造函數

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 c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) { 
        // c.toArray()可能不會正確地返回一個 Object[]數組,那么使用Arrays.copyOf()方法
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {     // 如果指定的collection為空
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

使用無參構造器,默認初始容量為什么是10?

1) 初始時:this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; size = 0;

2) 向數組中添加第一個元素時,add(E e)方法中調用了ensureCapacityInternal(size + 1)方法,即ensureCapacityInternal(1);

3) 在ensureCapacityInternal(int minCapacity)方法中,minCapacity=DEFAULT_CAPACITY=10,然后再調用ensureExplicitCapacity(minCapacity)方法,即ensureExplicitCapacity(10);

4) 在ensureExplicitCapacity(minCapacity)方法中調用grow(minCapacity)方法,即grow(10),此處為真正具體的數組擴容的算法,在此方法中,通過elementData = Arrays.copyOf(elementData, 10)具體實現了elementData數組初始容量為10的構造。

具體的擴容算法的實現請看這里

添加元素
// 在數組末尾加上一個元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 進行擴容檢查
    elementData[size++] = e;
    return true;
}

// 在數組的指定位置添加元素
public void add(int index, E element) {
    rangeCheckForAdd(index);   // 檢查index是否越界

    ensureCapacityInternal(size + 1);  // 進行擴容檢查
    
    // 對數據進行復制操作,空出index位置,并插入element,將源數組中從index位置開始后的size-index個元素統一后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;    // 元素個數加1
}

// 按照指定collection集合的迭代器所返回的元素順序,將該collection中的所有元素添加到列表的尾部
public boolean addAll(Collection c) {
    Object[] a = c.toArray();      // 將collection轉換為數組類型
    int numNew = a.length;         // collection中的元素個數
    ensureCapacityInternal(size + numNew);  // 進行擴容檢查
    System.arraycopy(a, 0, elementData, size, numNew);    // 將數組a[0,...,numNew-1]復制到數組elementData[size,...,size+numNew-1]
    size += numNew;
    return numNew != 0;
}

// 按照指定collection集合的迭代器所返回的元素順序,將該collection中的所有元素添加到列表的指定位置
public boolean addAll(int index, Collection c) {
    rangeCheckForAdd(index);    // 檢查index是否越界

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // 進行擴容檢查

    // 將數組elementData[index,...,index+numMoved-1]復制到elementData[index+numMoved,...,index+2*numMoved-1]
    //將源數組中從index位置開始的后numMoved個元素統一后移numNew位
    int numMoved = size - index;
    if (numMoved > 0)    
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    // 將數組a[0,...,numNew-1]復制到數組elementData[index,...,index+numNew-1]完成數據的插入                     
    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這個參數運用到了 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);
    // 對數組進行復制處理
    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);    //數組越界檢查
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;      //計算數組需要復制的數量
    if (numMoved > 0)   //將index后的數據都向前移一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);

    elementData[--size] = null;   //help  GC
    return oldValue;
}

// 刪除指定內容的元素(只刪除第一個匹配成功的)
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(區間--左閉右開)之間所有的元素
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;  //需向前移動的元素的個數
    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);
}

// 根據complement的值刪除元素
private boolean batchRemove(Collection c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;    //讀寫雙指針  w是重新存元素時的索引,r是原來的索引
    boolean modified = false;
    try {
        //遍歷數組,并檢查這個集合是否包含對應的值,移動要保留的值到數組前面,w最后值為要保留的元素的數量
        //簡單點:若保留,就將相同元素移動到前段;若刪除,就將不同元素移動到前段
        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:表示全部元素都保留了,所以也就沒有刪除操作發生,所以會返回false;反之,返回true,并更改數組
        //而w!=size的時候,即使try塊拋出異常,也能正確處理異常拋出前的操作,因為w始終為要保留的前段部分的長度,數組也不會因此亂序
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;//改變的次數
            size = w;   //新的大小為保留的元素的個數
            modified = true;
        }
    }
    return modified;
}

removeAll和retainAll方法:實現刪除或保留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中存在的所有元素。)

執行finally

finally是不管try中結果如何都會執行的。if(r!=size),則將elementData未參加比較的元素arraycopyelementData后面;新索引w加上剛arraycopy的數目;if (w != size),此時w還不等于size,則將w后的元素移除.只有執行了if (w != size)(事實上只要c中含有elementData的元素,w肯定不等于size),才令modified = true,才說明remove成功,返回true,否則返回false。

ArrayList中還有一個用于節約數組內存空間,縮小容量的方法

// 因為容量常常會大于實際元素的數量。內存緊張時,可以調用該方法刪除預留的位置,調整容量為元素實際數量。
// 如果確定不會再有元素添加進來時也可以調用該方法來節約空間
public void trimToSize() {
    modCount++;
    // length是數組長度,size表示數組內元素個數  
    // size

去掉預留元素的位置。返回一個新數組,新數組不含null,數組的size和elementData.length相等,以節省空間。此函數可避免size很小但elementData.length很大的情況。

ArrayList會每次增長會預申請多一點空間,1.5倍,這樣就會出現當size() = 10的時候,ArrayList已經申請了15空間, trimToSize就是刪除多余的5,只留10。

或許有人會有疑問:
調用Arrays.copyOf復制size長度的元素到elementData,而且由源碼看應該是從0復制到size處,那么如果我之前調用過add(int index, E element)呢?比如,list={1,2,3,null,null,4,null,null},如果調用trimToSize返回的應該是list={1,2,3,null}(因為size=4)。其實上面這種情況不會發生的,因為調用add(int index, E element)時,會檢查index的合法性,所以list的元素肯定是相鄰的,而不會出現上述這種中間出現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;
}

//返回一個值在數組首次出現的位置,會根據是否為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;
}

//返回一個值在數組最后一次出現的位置,不存在就返回-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;
}

//返回指定位置的值,因為是數組,所以速度特別快
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

//返回指定位置的值,但是會檢查這個位置數否超出數組長度
public E get(int index) {
    rangeCheck(index);

    return elementData(index); //實質上return (E) elementData[index]
}
序列化
//保存數組實例的狀態到一個流(即它序列化)。寫入過程數組被更改會拋出異常
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;
    s.defaultWriteObject(); //執行默認的反序列化/序列化過程。將當前類的非靜態和非瞬態字段寫入此流
    // 寫入大小
    s.writeInt(size);
    // 按順序寫入所有元素
    for (int i=0; i 0) {
        ensureCapacityInternal(size);
        Object[] a = elementData;
        //讀入所有元素
        for (int i=0; i

為什么要自定義序列化、反序列化機制呢?

由于ArrayList實質上是一個動態數組,往往數組中會有空余的空間,如果采用默認的序列化機制,那些空余的空間會作為null寫入本地文件或者在網絡中傳輸,耗費了不必要的資源。所以,ArrayList使用自定義序列化機制,僅寫入索引為【0,size)的有效元素以節省資源

迭代器
//返回ListIterator,開始位置為指定參數
public ListIterator listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

//返回ListIterator,開始位置為0
public ListIterator listIterator() {
    return new ListItr(0);
}

//返回普通迭代器
public Iterator iterator() {
    return new Itr();
}

//通用的迭代器實現
private class Itr implements Iterator {
    int cursor;       //游標,下一個元素的索引,默認初始化為0
    int lastRet = -1; //上次訪問的元素的位置
    int expectedModCount = modCount;//迭代過程不允許修改數組,否則就拋出異常
    //是否還有下一個
    public boolean hasNext() {
        return cursor != size;
    }
    //下一個元素
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();//檢查數組是否被修改
        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();//檢查數組是否被修改
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer 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();
    }
    //檢查數組是否被修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

//ListIterator迭代器實現
private class ListItr extends Itr implements ListIterator {
    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的區別:

Iterator可以應用于所有的集合,Set、List和Map和這些集合的子類型。而ListIterator只能用于List及其子類型;

Iterator只能實現順序向后遍歷,ListIterator可實現順序向后遍歷和逆向(順序向前)遍歷;

Iterator只能實現remove操作,ListIterator可以實現remove操作,add操作,set操作。

其他方法
//返回ArrayList的大小(元素個數)
public int size() {
    return size;
}

//判斷ArrayList是否為空
public boolean isEmpty() {
    return size == 0;
}

//返回此 ArrayList實例的淺拷貝(元素本身沒有被復制,復制過程數組發生改變會拋出異常)
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,數組是新的,但是里面N個元素全是引用的舊的。
淺拷貝(影子克隆):只復制基本類型。

深拷貝(深度克隆):基本類+對象。
*/

//返回一個包含ArrayList中所有元素的數組
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

// 返回一個數組,使用運行時確定類型,該數組包含在這個列表中的所有元素(從第一到最后一個元素)
// 返回的數組容量由參數和本數組中較大值確定
@SuppressWarnings("unchecked")
public  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會在加入一些數據頭,當擴容后的容量大于MAX_ARRAY_SIZE,我們會去比較最小需要容量和MAX_ARRAY_SIZE做比較,如果比它大, 只能取Integer.MAX_VALUE,否則是Integer.MAX_VALUE -8。
這個是從jdk1.7開始才有的

jdk1.8的無參構造函數和之前版本的構造函數有什么區別?
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的底層數組elementData大小(容量)默認為10;從1.7開始,無參構造方法構造的ArrayList的底層數組elementData大小默認為0。

java集合類在jdk1.7版本基本上都有一種改動:懶初始化。懶初始化指的是默認構造方法構造的集合類,占據盡可能少的內存空間(對于ArrayList來說,使用空數組來占據盡量少的空間,不使用null是為了避免null判斷),在第一次進行包含有添加語義的操作時,才進行真正的初始化工作。

1.7開始的ArrayList,默認構造方法構造的實例,底層數組是空數組,容量為0,在進行第一次add/addAll等操作時才會真正給底層數組賦非empty的值。如果add/addAll添加的元素小于10,則把elementData數組擴容為10個元素大小,否則使用剛好合適的大小(例如,第一次addAll添加6個,那么擴容為10個,第一次添加大于10個的,比如24個,擴容為24個,剛好合適)

1.8版本,默認構造的實例這個行為沒有改變,只是用的數組名字變了。

jdk1.6中擴容算法的缺陷

(由于jdk1.7和jdk1.8在擴容算法方面差別不大,所以下面沒有嚴格區分)

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開始對這個進行了完善。

而且沒考慮入參minCapacity可能因為int溢出變為負數。這個方法可以外部手動調用,手動擴容傳入負數這個肯定是應該攔截掉的。但是自動擴容會因為int溢出產生負數,碰到這種情況時應該特殊處理,而不是什么都不做,等著后面拋出一個ArrayIndexOutOfBoundsException。

還有就是下面這句代碼會造成過早溢出

int newCapacity = (oldCapacity * 3)/2 + 1;

雖然上面這行代碼和1.7開始的oldCapacity + (oldCapacity >> 1) 差不多,都是相當于1.5倍,但實際上是有
區別的。

這里主要有兩個區別

第一個區別是jdk1.6的乘除運算的數學結果比后面一個大1比如oldCapacity=10,1.6的
算法得到16,1.7開始的算法得到15,這個影響不大;

第二個區別就是兩者在數字比較大時運算結果不一樣,比如
oldCapacity=10^9,這個數和Integer.MAX_VALUE位數一樣,用1.6的算法得到的會是錯誤的-647483647,用
1.7的則是正確的1500000000,這時候明明可以1.5倍擴容,但是jdk1.6卻用的是按需擴容。

ensureCapacity(稱之為手動,是因為此方法是public的,可以外部手動調用)。
在1.6版本是只有這個手動的方法,內部自動操作也是調用這個方法,1.7開始進行了區分,并且進一步改進了擴容操作。

從1.7開始將內部擴容和外部可以調用的擴容方法分開了,通過源碼可以看出:外部調用的手動擴容方法ensureCapacity要多一個判斷條件 minCapacity > minExpand,這個判斷條件攔截掉負數的minCapacity,這樣調用內部擴容ensureCapacityInternal方法時,minCapacity一定是正數;內部擴容方法直接就用minCapacity - elementData.length > 0判斷,此條件可以檢測出int型溢出,碰到溢出最后會拋出一個OOM錯誤。jdk1.7用OOM,這比jdk1.6用ArrayIndexOutOfBoundsException更好,因為此時數組大小超出了虛擬機對數組的限制,虛擬機無法處理這種情況了,拋出一個ERROR是合理的。

使用這行代碼

newCapacity = oldCapacity + (oldCapacity >> 1);

這行代碼不僅僅是使用位運算加快執行速度,上面說了,這種做法才是對的,是真正的1.5倍。不僅僅因為那一個大小的差別,更重要的是避免過早出現int溢出的情況,保證了內部自動擴容會盡量按規定的策略執行。同時整個擴容處理流程中多增加了幾處if判斷,對各種情況處理更加完善。

為什么ArrayList自動容量擴充選擇擴充1.5倍?

這種算法構造出來的新的數組長度的增量都會比上一次大( 而且是越來越大) ,避免頻繁newInstance 的情況。

為什么ArrayList 不適合頻繁插入和刪除操作?

由上面分析的增加刪除方法可以看出在ArrayList中經常會調用 System.arraycopy 這個效率很低的操作來復制數組,所以導致ArrayList在插入和刪除操作中效率不高。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/69582.html

相關文章

  • java源碼

    摘要:集合源碼解析回歸基礎,集合源碼解析系列,持續更新和源碼分析與是兩個常用的操作字符串的類。這里我們從源碼看下不同狀態都是怎么處理的。 Java 集合深入理解:ArrayList 回歸基礎,Java 集合深入理解系列,持續更新~ JVM 源碼分析之 System.currentTimeMillis 及 nanoTime 原理詳解 JVM 源碼分析之 System.currentTimeMi...

    Freeman 評論0 收藏0
  • ArrayList源碼解析fail-fast機制深入理解

    摘要:當多個線程對同一個集合的內容進行操作時,就可能會產生事件。當某一個線程遍歷的過程中,的內容被另外一個線程所改變了就會拋出異常,產生事件。在線程在遍歷過程中的某一時刻,線程執行了,并且線程刪除了中的節點。 概要 前面,我們已經學習了ArrayList。接下來,我們以ArrayList為例,對Iterator的fail-fast機制進行了解。 1 fail-fast簡介 fail-fast...

    NikoManiac 評論0 收藏0
  • 我的阿里路+Java面經考點

    摘要:我的是忙碌的一年,從年初備戰實習春招,年三十都在死磕源碼,三月份經歷了阿里五次面試,四月順利收到實習。因為我心理很清楚,我的目標是阿里。所以在收到阿里之后的那晚,我重新規劃了接下來的學習計劃,將我的短期目標更新成拿下阿里轉正。 我的2017是忙碌的一年,從年初備戰實習春招,年三十都在死磕JDK源碼,三月份經歷了阿里五次面試,四月順利收到實習offer。然后五月懷著忐忑的心情開始了螞蟻金...

    姘擱『 評論0 收藏0
  • Java編程基礎16——Colletion集合

    摘要:集合的長度的是可變的,可以根據元素的增加而增長。如果元素個數不是固定的推薦用集合。線程安全,效率低。相對查詢慢線程安全的相對增刪慢數組結構底層數據結構是鏈表,查詢慢,增刪快。線程不安全,效率高。 1_對象數組的概述和使用 A:案例演示 需求:我有5個學生,請把這個5個學生的信息存儲到數組中,并遍歷數組,獲取得到每一個學生信息。 import net.allidea.bean.Stu...

    TerryCai 評論0 收藏0
  • Java相關

    摘要:本文是作者自己對中線程的狀態線程間協作相關使用的理解與總結,不對之處,望指出,共勉。當中的的數目而不是已占用的位置數大于集合番一文通版集合番一文通版垃圾回收機制講得很透徹,深入淺出。 一小時搞明白自定義注解 Annotation(注解)就是 Java 提供了一種元程序中的元素關聯任何信息和著任何元數據(metadata)的途徑和方法。Annotion(注解) 是一個接口,程序可以通過...

    wangtdgoodluck 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<