本文介紹

1、ArrayList相關(guān)面試題。
2、ArrayList基本信息。
3、ArrayList屬性和方法。
4、ArrayList的總結(jié)。
5、ArrayList最佳實(shí)踐。

概述

ArrayList是一種變長的集合類，基于定長數(shù)組實(shí)現(xiàn)。因底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，它是占據(jù)一塊連續(xù)的內(nèi)存空間，所以它也有數(shù)組的缺點(diǎn)，空間效率不高。同樣底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，直接通過下標(biāo)查找元素時(shí)，時(shí)間復(fù)雜度為O(1)。根據(jù)元素內(nèi)容查找時(shí)，時(shí)間復(fù)雜度為O(n)。
ArrayList 允許空值和重復(fù)元素，當(dāng)往 ArrayList 中添加的元素?cái)?shù)量大于其底層數(shù)組容量時(shí)，其會(huì)通過擴(kuò)容機(jī)制重新生成一個(gè)更大的數(shù)組。
ArrayList 是非線程安全類，并發(fā)環(huán)境下，多個(gè)線程同時(shí)操作 ArrayList，會(huì)引發(fā)不可預(yù)知的錯(cuò)誤。

ArrayList類關(guān)系圖

ArrayList 繼承AbstractList，實(shí)現(xiàn)了List, RandomAccess, Cloneable, java.io.Serializable接口。
ArrayList 實(shí)現(xiàn)List接口，即提供相關(guān)的添加、刪除、修改、遍歷功能。
ArrayList 實(shí)現(xiàn)RandmoAccess接口，即提供隨機(jī)訪問功能。
ArrayList 實(shí)現(xiàn)Cloneable接口，即覆蓋了函數(shù)clone()，能被克隆。
ArrayList 實(shí)現(xiàn)Serializable接口，這意味著ArrayList支持序列化。

下面讓我們翻開ArrayList的源代碼，看看一些常用的方法屬性，以及一些需要注意的地方。

屬性

ArrayList屬性主要就是當(dāng)前數(shù)組長度size，以及存放數(shù)組的對(duì)象elementData數(shù)組，除此之外還有一個(gè)經(jīng)常用到的屬性就是從AbstractList繼承過來的modCount屬性，代表ArrayList集合的修改次數(shù)。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    // 序列化id
    private static final long serialVersionUID = 8683452581122892189L;
    // 默認(rèn)初始的容量
    private static final int DEFAULT_CAPACITY = 10;
    // 一個(gè)空對(duì)象
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 一個(gè)空對(duì)象，如果使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建，則默認(rèn)對(duì)象內(nèi)容默認(rèn)是該值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 當(dāng)前數(shù)據(jù)對(duì)象存放地方，當(dāng)前對(duì)象不參與序列化
    transient Object[] elementData;
    // 當(dāng)前數(shù)組長度
    private int size;
    // 數(shù)組最大長度
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

一些測(cè)試

最大容量測(cè)試

添加值測(cè)試

構(gòu)造函數(shù)

無參構(gòu)造函數(shù)

如果不傳入?yún)?shù)，則使用默認(rèn)無參構(gòu)建方法創(chuàng)建ArrayList對(duì)象，如下：

public ArrayList() {
    // 將空串賦值給elementData
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

注意：此時(shí)我們創(chuàng)建的ArrayList對(duì)象中的elementData中的長度是0，size是0,當(dāng)進(jìn)行第一次add的時(shí)候，elementData將會(huì)修改成默認(rèn)的長度：10

帶int類型的構(gòu)造函數(shù)

如果傳入?yún)?shù)，則代表指定ArrayList的初始數(shù)組長度，傳入?yún)?shù)如果是大于等于0，則使用用戶的參數(shù)初始化，如果用戶傳入的參數(shù)小于0，則拋出異常，構(gòu)造方法如下：

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) { // 如果初始容量大于0，則新建一個(gè)長度為initialCapacity的Object數(shù)組.
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { // 如果容量為0，直接將EMPTY_ELEMENTDATA賦值給elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else { // 容量小于0，直接拋出異常，把所有情況都考慮周到
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

帶Collection對(duì)象的構(gòu)造函數(shù)

public ArrayList(Collection<? extends E> c) {
    // 將collection對(duì)象轉(zhuǎn)換成數(shù)組，然后將數(shù)組的地址的賦給elementData
    elementData = c.toArray();
    // 因size代表的是集合元素?cái)?shù)量，所以通過別的集合來構(gòu)造ArrayList時(shí)，要給size賦值
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class) // 當(dāng)c.toArray出錯(cuò)，沒有返回Object[]，將集合c中的元素到elementData數(shù)組中
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //如果集合c元素?cái)?shù)量為0，則將空數(shù)組EMPTY_ELEMENTDATA賦值給elementData 
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add方法

add的方法有兩個(gè)，一個(gè)是帶一個(gè)參數(shù)的，一個(gè)是帶兩個(gè)參數(shù)的，下面我們一個(gè)個(gè)講解。

add(E e) 方法

add主要的執(zhí)行邏輯如下：
1）確保數(shù)組已使用長度（size）加1之后足夠存下下一個(gè)數(shù)據(jù)
2）修改次數(shù)modCount 標(biāo)識(shí)自增1，如果當(dāng)前數(shù)組已使用長度（size）加1后的大于當(dāng)前的數(shù)組長度，則調(diào)用grow方法，增長數(shù)組，grow方法會(huì)將當(dāng)前數(shù)組的長度變?yōu)樵瓉砣萘康?.5倍。

添加元素方法入口：

public boolean add(E e) {
    // 確保數(shù)組已使用長度（size）加1之后足夠存下 下一個(gè)數(shù)據(jù)
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 在數(shù)組末尾存放新的元素，并修改size
    elementData[size++] = e;
    // 成功返回true
    return true;
}

確保添加的元素有地方存儲(chǔ)，當(dāng)?shù)谝淮翁砑釉氐臅r(shí)候this.size+1 的值是1，所以第一次添加的時(shí)候會(huì)將當(dāng)前elementData數(shù)組的長度變?yōu)?0：

private void ensureCapacityInternal(int minCapacity) {
    // 判斷數(shù)組是否是用默認(rèn)構(gòu)造函數(shù)初始化的
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

將修改次數(shù)（modCount）自增1，判斷是否需要擴(kuò)充數(shù)組長度,判斷條件就是用當(dāng)前所需的數(shù)組最小長度與數(shù)組的長度對(duì)比，如果大于0，則增長數(shù)組長度。

private void ensureExplicitCapacity(int minCapacity) {
    // 修改modCount
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

如果當(dāng)前的數(shù)組已使用空間（size）加1之后大于數(shù)組長度，則增大數(shù)組容量，擴(kuò)大為原來的1.5倍。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 默認(rèn)擴(kuò)容為原大小的1.5位
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

add(int index, E element)方法

這個(gè)方法其實(shí)和上面的add類似，該方法可以按照元素的位置，指定位置插入元素，具體的執(zhí)行邏輯如下：
1）確保數(shù)插入的位置小于等于當(dāng)前數(shù)組長度，并且不小于0，否則拋出異常
2）確保數(shù)組已使用長度（size）加1之后足夠存下下一個(gè)數(shù)據(jù)
3）修改次數(shù)（modCount）標(biāo)識(shí)自增1，如果當(dāng)前數(shù)組已使用長度（size）加1后的大于當(dāng)前的數(shù)組長度，則調(diào)用grow方法，增長數(shù)組
4）grow方法會(huì)將當(dāng)前數(shù)組的長度變?yōu)樵瓉砣萘康?.5倍。
5）確保有足夠的容量之后，使用System.arraycopy 將需要插入的位置（index）后面的元素統(tǒng)統(tǒng)往后移動(dòng)一位。
6）將新的數(shù)據(jù)內(nèi)容存放到數(shù)組的指定位置（index）上

public void add(int index, E element) {
    // 范圍檢查
    rangeCheckForAdd(index);

    // Increments modCount!!
    ensureCapacityInternal(size + 1); 

    // 將index位置開始的數(shù)據(jù) 向后移動(dòng)一位 
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

注意：使用該方法的話將導(dǎo)致指定位置后面的數(shù)組元素全部重新移動(dòng)，即往后移動(dòng)一位。

get方法

返回指定位置上的元素，數(shù)組下標(biāo)從0開始。

public E get(int index) {
    // 檢查范圍，判斷下標(biāo)是否越界
    rangeCheck(index);
    // 返回?cái)?shù)組下標(biāo)對(duì)應(yīng)內(nèi)容
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

set方法

確保set的位置小于當(dāng)前數(shù)組的長度（size）并且大于0，獲取指定位置（index）元素，然后放到oldValue存放，將需要設(shè)置的元素放到指定的位置（index）上，然后將原來位置上的元素oldValue返回給用戶。

public E set(int index, E element) {
    // 檢查范圍，判斷下標(biāo)是否越界
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

contains方法

調(diào)用indexOf方法，遍歷數(shù)組中的每一個(gè)元素作對(duì)比，如果找到對(duì)于的元素，則返回true，沒有找到則返回false。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

// for循環(huán)尋找值，null做為特殊值區(qū)別開來查找
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;
}

remove方法

根據(jù)索引remove

public E remove(int index) {
    // 檢查索引有沒有越界
    rangeCheck(index);
    // 自增修改次數(shù)
    modCount++;
    // 暫存舊值
    E oldValue = elementData(index);

    // 將指定位置（index）上的元素都往前移動(dòng)一位
    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
    // 返回舊值
    return oldValue;
}

注意：調(diào)用這個(gè)方法不會(huì)縮減數(shù)組的長度，只是將最后一個(gè)數(shù)組元素置空而已。

根據(jù)對(duì)象remove

循環(huán)遍歷所有對(duì)象，得到對(duì)象所在索引位置，然后調(diào)用fastRemove方法，執(zhí)行remove操作

// 循環(huán)查找元素，找到后移除該元素
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;
}

定位到需要remove的元素索引，先將index后面的元素往前面移動(dòng)一位（調(diào)用System.arraycooy實(shí)現(xiàn)），然后將最后一個(gè)元素置空。

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
}

clear方法

添加操作次數(shù)（modCount），將數(shù)組內(nèi)的元素都置空，等待垃圾收集器收集，不減小數(shù)組容量。

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null; //將所有元素置null

    size = 0;
}

sublist方法

我們看到代碼中是創(chuàng)建了一個(gè)ArrayList 類里面的一個(gè)內(nèi)部類SubList對(duì)象，傳入的值中第一個(gè)參數(shù)時(shí)this參數(shù)，其實(shí)可以理解為返回當(dāng)前l(fā)ist的部分視圖，真實(shí)指向的存放數(shù)據(jù)內(nèi)容的地方還是同一個(gè)地方，如果修改了sublist返回的內(nèi)容的話，那么原來的list也會(huì)變動(dòng)。

public List<E> subList(int fromIndex, int toIndex) {
    // 范圍檢查
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

trimToSize方法

將elementData中空余的空間（包括null值）去除，例如：數(shù)組長度為10，其中只有前三個(gè)元素有值，其他為空，那么調(diào)用該方法之后，數(shù)組的長度變?yōu)?.

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

iterator方法

interator方法返回的是一個(gè)內(nèi)部類，由于內(nèi)部類的創(chuàng)建默認(rèn)含有外部的this指針，所以這個(gè)內(nèi)部類可以調(diào)用到外部類的屬性。

public Iterator<E> iterator() {
    return new Itr();
}

一般的話，調(diào)用完iterator之后，我們會(huì)使用iterator做遍歷，這里使用next做遍歷的時(shí)候有個(gè)需要注意的地方，就是調(diào)用next的時(shí)候，可能會(huì)引發(fā)ConcurrentModificationException，當(dāng)修改次數(shù)，與期望的修改次數(shù)（調(diào)用iterator方法時(shí)候的修改次數(shù)）不一致的時(shí)候，會(huì)發(fā)生該異常，詳細(xì)我們看一下代碼實(shí)現(xiàn)：

@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];
}

expectedModCount這個(gè)值是在用戶調(diào)用ArrayList的iterator方法時(shí)候確定的，但是在這之后用戶add，或者remove了ArrayList的元素，那么modCount就會(huì)改變，那么這個(gè)值就會(huì)不相等，將會(huì)引發(fā)ConcurrentModificationException異常，這個(gè)是在多線程使用情況下，比較常見的一個(gè)異常。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

System.arraycopy 方法

參數(shù) 說明
src 原數(shù)組
srcPos 原數(shù)組
dest 目標(biāo)數(shù)組
destPos 目標(biāo)數(shù)組的起始位置
length 要復(fù)制的數(shù)組元素的數(shù)目

Arrays.copyOf方法

original - 要復(fù)制的數(shù)組
newLength - 要返回的副本的長度
newType - 要返回的副本的類型

其實(shí)Arrays.copyOf底層也是調(diào)用System.arraycopy實(shí)現(xiàn)的源碼如下：

//基本數(shù)據(jù)類型（其他類似byte，short···）
public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

總結(jié)

ArrayList總體來說比較簡單，不過ArrayList還有以下一些特點(diǎn)：
ArrayList自己實(shí)現(xiàn)了序列化和反序列化的方法，因?yàn)樗约簩?shí)現(xiàn)了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
ArrayList基于數(shù)組方式實(shí)現(xiàn)，無容量的限制（會(huì)擴(kuò)容）
添加元素時(shí)可能要擴(kuò)容（所以最好預(yù)判一下），刪除元素時(shí)不會(huì)減少容量（若希望減少容量，trimToSize()），刪除元素時(shí)，將刪除掉的位置元素置為null，下次gc就會(huì)回收這些元素所占的內(nèi)存空間。
add(int index, E element)：添加元素到數(shù)組中指定位置的時(shí)候，需要將該位置及其后邊所有的元素都整塊向后復(fù)制一位
get(int index)：獲取指定位置上的元素時(shí)，可以通過索引直接獲取（O(1)）
remove(Object o)：需要遍歷數(shù)組
remove(int index)：不需要遍歷數(shù)組，只需判斷index是否符合條件即可，效率比remove(Object o)高
contains(E)：需要遍歷數(shù)組
使用iterator遍歷可能會(huì)引發(fā)多線程異常

最佳實(shí)踐

1、適合用于查詢修改多，增加刪除少的業(yè)務(wù)中。如：后臺(tái)管理系統(tǒng)數(shù)據(jù)分頁展示頁面、商城商品分頁展示頁面，從數(shù)據(jù)庫中查詢一批數(shù)據(jù)后需由容器裝載傳輸?shù)角岸?。此時(shí)用ArrayList來裝載商品數(shù)據(jù)最適合不過。
2、創(chuàng)建容器時(shí)指定初始容器大小，如：后臺(tái)管理系統(tǒng)數(shù)據(jù)分頁展示頁面，一頁展示15條數(shù)據(jù)，如果不指定容器大小，默認(rèn)10，查詢15條數(shù)據(jù)還需要擴(kuò)一次容，累不累？
3、new ArrayList時(shí)增加泛型，目的是為了安全。如以下代碼

// 添加泛型的list
List<String> list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add(1);// 此處會(huì)報(bào)編譯錯(cuò)誤

// 未添加范型的list
List list1 = new ArrayList();
list1.add("a"); // 編譯通過
list1.add(1); // 編譯通過
list1.add(0.5f); // 編譯通過

image.png

引文

ArrayList源碼分析（基于JDK8）
https://blog.csdn.net/fighterandknight/article/details/61240861

面試必備：ArrayList源碼解析（JDK8）
https://blog.csdn.net/zxt0601/article/details/77281231

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

ArrayList源碼分析（基于JDK8）

ArrayList源碼分析（基于JDK8）

本文介紹

相關(guān)面試題

概述

屬性

一些測(cè)試

構(gòu)造函數(shù)

無參構(gòu)造函數(shù)

帶int類型的構(gòu)造函數(shù)

帶Collection對(duì)象的構(gòu)造函數(shù)

add方法

add(E e) 方法

add(int index, E element)方法

get方法

set方法

contains方法

remove方法

根據(jù)索引remove

根據(jù)對(duì)象remove

clear方法

sublist方法

trimToSize方法

iterator方法

System.arraycopy 方法

Arrays.copyOf方法

總結(jié)

最佳實(shí)踐

引文

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

ArrayList源碼分析（基于JDK8）

本文介紹

相關(guān)面試題

概述

屬性

一些測(cè)試

構(gòu)造函數(shù)

無參構(gòu)造函數(shù)

帶int類型的構(gòu)造函數(shù)

帶Collection對(duì)象的構(gòu)造函數(shù)

add方法

add(E e) 方法

add(int index, E element)方法

get方法

set方法

contains方法

remove方法

根據(jù)索引remove

根據(jù)對(duì)象remove

clear方法

sublist方法

trimToSize方法

iterator方法

System.arraycopy 方法

Arrays.copyOf方法

總結(jié)

最佳實(shí)踐

引文

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av