• 一篇文章帶您讀懂List集合(源碼分析)

    今天要分享的Java集合是List,主要是針對它的常見實現類ArrayList進行講解

    內容目錄

    什么是List核心方法源碼剖析1.文檔注釋2.構造方法3.add()3.remove()如何提升ArrayList的性能ArrayList可以代替數組嗎?

    什么是List

      List集合是線性數據結構的主要實現,用來存放一組數據。我們稱之為:列表。


      ArrayList是List的一個常見實現類,它的面試頻率和使用頻率都非常高,所以我們今天通過學習ArrayList來對Java中的List集合有一個深入的理解。
      ArrayList最大的優勢是可以將數組的操作細節封裝起來,比如數組在插入和刪除時要搬移其他數據。另外,它的另一大優勢,就是支持動態擴容,這也是我們使用ArrayList的主要場景之一,在某些情況下我們沒有辦法在程序編譯之前就確定存儲數據
    容器的大小。

     

    核心方法源碼剖析

      這一部分,選取了ArrayList的一些核心方法進行講解。分別是:構造方法,add()、和remove()。這里有一個小竅門,我們在讀jdk源碼的時候,一定要先看類上的doc注釋,比較核心的知識點都會寫在上面。有一個初步的概念再去看源碼,就會容易很多。

    1.文檔注釋

      This class is roughly equivalent to Vector, except that it is unsynchronized.
      大致相當于Vector,不同之處是不同步(線程不安全)

      Implements all optional list operations, and permits all elements, including null
      實現所有可選列表操作,并允許所有元素,包括null

      in the face of concurrent modification, the iterator fails quickly and cleanly
      面對并發修改,迭代器將快速而干凈地失敗

    2.構造方法

      ArrayList()提供了三種構造方法。
      ArrayList():構造一個初始容量為10的空列表。
      ArrayList(int initialCapacity):構造具有指定初始容量的空列表。
      ArrayList(Collection c):構造一個包含指定集合的元素的列表,按照它們由集合的迭代器返回的順序。

    1/**
    2 * Constructs an empty list with an initial capacity of ten.
    3 */

    4public ArrayList() {
    5   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    6}

      這里的DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個空的部數組,不設定初始值時,只是引用這個內部數組。

     1/**
    2 * Constructs an empty list with the specified initial capacity.
    3 *
    4 * @param  initialCapacity  the initial capacity of the list
    5 * @throws IllegalArgumentException if the specified initial capacity
    6 *         is negative
    7 */

    8public ArrayList(int initialCapacity) {
    9    if (initialCapacity > 0) {
    10        this.elementData = new Object[initialCapacity];
    11    } else if (initialCapacity == 0) {
    12        this.elementData = EMPTY_ELEMENTDATA;
    13    } else {
    14        throw new IllegalArgumentException("Illegal Capacity: "+
    15                                               initialCapacity);
    16    }
    17}

      這里的EMPTY_ELEMENTDATA同樣是一個空內部數組,為了和DEFAULTCAPACITY_EMPTY_ELEMENTDATA做區分,所以沒有使用一個對象。

    3.add()

      add方法是ArrayList中的一個核心方法,涉及到內部數組的擴容。

     1 /**
    2  * Appends the specified element to the end of this list.
    3  *
    4  * @param e element to be appended to this list
    5  * @return <tt>true</tt> (as specified by {@link Collection#add})
    6  */

    7public boolean add(E e) {
    8  ensureCapacityInternal(size + 1);  // Increments modCount!!
    9  elementData[size++] = e;
    10  return true;
    11}

      該方法是在集合中追加元素。其中核心方法是ensureCapacityInternal,意思是確定集合內部容量。

     1private void ensureCapacityInternal(int minCapacity) {
    2      ensureExplicitCapacity(
    3  calculateCapacity(elementData,minCapacity));
    4}
    5
    6private static int calculateCapacity(Object[] elementData, int 
    7      minCapacity)
     
    {
    8  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    9    return Math.max(DEFAULT_CAPACITY, minCapacity);
    10  }
    11  return minCapacity;
    12}

      這里首先計算了集合的容量,如果這個ArrayList是通過無參構造創建的,那么比較默認值10,以及傳入的minCapacity,取最大值,這里可能有的同學會有疑問,為什么要比較默認值和minCapacity,默認值不是一定大于minCapacity嗎?,這里是因為ensureCapacityInternal這個方法不僅僅是add()會調用,allAll()也會調用。

    1public boolean addAll(int index, Collection<? extends E> c) {
    2        rangeCheckForAdd(index);
    3
    4        Object[] a = c.toArray();
    5        int numNew = a.length;
    6        ensureCapacityInternal(size + numNew);  // Increments modCount
    7       //省略部分代碼..
    8    }

      這里如果numNew大于10,那么默認值就會不夠用。所以才會在calculateCapacity方法中引入一個求最大值的步驟。
      算出集合存儲數據所需的最小空間后,就要考慮,集合原有存儲空間是否夠用,是否需要擴容。

     1private void ensureExplicitCapacity(int minCapacity) {
    2    modCount++;
    3    // overflow-conscious code
    4    if (minCapacity - elementData.length > 0)
    5    grow(minCapacity);
    6}
    7
    8/**
    9 * Increases the capacity to ensure that it can hold at least the
    10 * number of elements specified by the minimum capacity argument.
    11 *
    12 * @param minCapacity the desired minimum capacity
    13 */

    14 private void grow(int minCapacity) {
    15    // overflow-conscious code
    16    int oldCapacity = elementData.length;
    17    int newCapacity = oldCapacity + (oldCapacity >> 1);
    18    if (newCapacity - minCapacity < 0)
    19    newCapacity = minCapacity;
    20    if (newCapacity - MAX_ARRAY_SIZE > 0)
    21    newCapacity = hugeCapacity(minCapacity);
    22    // minCapacity is usually close to size, so this is a win:
    23    elementData = Arrays.copyOf(elementData, newCapacity);
    24}

    這里我們主要關注4個點:
      1.int newCapacity = oldCapacity + (oldCapacity >> 1);每次擴容是原數組的1.5倍
      2.擴容也是有限的,存在最大值:MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
      3.集合擴容底層調用的是:Arrays.copyOf()方法,需要把數組中的數據復制一份,到新數組中,而這個方法底層是System.arrayCopy是一個native方法,效率不高。
      4.最重要的一個點:如果我們可以事先估計出數據量,那么最好給ArrayList一個初始值,這樣可以減少其擴容次數,從而省掉很多次內存申請和數據搬移操作。(不指定初始值,至少會執行一次grow方法,用于初始化內部數組)。

    3.remove()

     1/**
    2 * Removes the element at the specified position in this list.
    3 * Shifts any subsequent elements to the left (subtracts one from their
    4 * indices).
    5 *
    6 * @param index the index of the element to be removed
    7 * @return the element that was removed from the list
    8 * @throws IndexOutOfBoundsException {@inheritDoc}
    9 */

    10public E remove(int index) {
    11    rangeCheck(index);
    12    modCount++;
    13    E oldValue = elementData(index);
    14
    15    int numMoved = size - index - 1;
    16    if (numMoved > 0)
    17       System.arraycopy(elementData, index+1, elementData, index,
    18                             numMoved);
    19    elementData[--size] = null// clear to let GC do its work
    20    return oldValue;
    21}

      刪除的代碼因為不涉及到縮容,所以比起add較為簡單,首先會檢查數組是否下標越界,然后會獲取指定位置的元素,接著進行數據的搬移,將--size位置的元素置成null,讓GC進行回收。最后將目標元素返回即可。
      另外最后我想提出一個比較容易犯的錯誤,集合在遍歷的時候,對其結構進行修改(刪除、新增元素)。舉一個例子:

     1public class Test {
    2    public static void main(String[] args) {
    3        List<Integer> list = new ArrayList<>();
    4        list.add(1);
    5        list.add(2);
    6        list.add(3);
    7        for (Integer i : list) {
    8            if(i.equals(1)){
    9                list.remove(i);
    10            }
    11        }
    12    }
    13}

    結果:

    1Exception in thread "main" java.util.ConcurrentModificationException
    2    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    3    at java.util.ArrayList$Itr.next(ArrayList.java:859)
    4    at jialin.li.Test.main(Test.java:12)

      產生問題的原因,其實文檔注釋已經給出了明確的結果,即:
      if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own {@link ListIterator#remove() remove} or {@link ListIterator#add(Object) add} methods, the iterator will throw a {@link ConcurrentModificationException}
      如果列表在任何時間從結構上修改創建迭代器之后,以任何方式除非通過迭代器自身remove種或add方法,迭代器都將拋出一個ConcurrentModificationException。這里我建議是遍歷的時候,不要對其結構進行修改,而是采用其他方法(打標,或者復制列表)的方式進行。

    如何提升ArrayList的性能

      1 給定初值,省掉很多次內存申請和數據搬移操作。
      2 對于讀多寫少的場景,可以使用ArrayList替代LinkedList,可以省內存,同時CPU緩存的利用率也會更高。(數組存儲的時候,是內存是連續的,CPU讀取內存數據、內存讀取磁盤數據的時候,都不是一條一條讀取,而是一次讀取臨近的一批數據,所以連續的存儲可以讓CPU更有機會一次讀取較多的有效數據)

    ArrayList可以代替數組嗎?

      不可以,任何數據結構都有它存在的場景和意義,集合沒有辦法存儲基本數據類型,只能存儲包裝類型,包裝類型就意味著需要拆箱和裝箱,會有一定的性能消耗,如果對性能要求非常高的系統,或者只需要使用基本類型,那么就應該去使用數組而不是集合。同時數組在表示多維數據的時候,也更加直觀,比如二維 int[][] 、ArrayList<arraylist>。我們使用集合更多的情況是想利用它的擴容特性,以及增刪數據時不會造成空洞。

      最后,期待您的訂閱和點贊,專欄每周都會更新,希望可以和您一起進步,同時也期待您的批評與指正!

    posted @ 2020-03-01 16:04  進擊的李同學  閱讀(...)  評論(...編輯  收藏
    贵州快三平台贵州快三主页贵州快三网站贵州快三官网贵州快三娱乐贵州快三开户贵州快三注册贵州快三是真的吗贵州快三登入贵州快三快三贵州快三时时彩贵州快三手机app下载贵州快三开奖 克山县 | 区。 | 华容县 | 卢氏县 | 东乌珠穆沁旗 | 砀山县 | 宁城县 | 元阳县 | 高安市 | 阿克苏市 | 托克托县 | 元阳县 | 凭祥市 | 宁远县 | 凉山 | 明溪县 | 荣昌县 | 乌什县 | 邮箱 | 康保县 | 珲春市 | 淮南市 | 金门县 | 宁阳县 | 齐齐哈尔市 | 安阳县 | 临邑县 | 肃宁县 | 布尔津县 | 勃利县 | 右玉县 | 贡觉县 | 安庆市 | 海淀区 | 南雄市 | 阿拉善盟 | 承德县 | 江北区 | 藁城市 | 偃师市 | 遵义县 | 观塘区 | 清徐县 | 三门县 | 周宁县 | 台州市 | 赣州市 | 庐江县 | 泰州市 | 冀州市 | 阿合奇县 | 黄山市 | 营口市 | 玉屏 | 永川市 | 平顶山市 | 芦山县 | 惠来县 | 枞阳县 | 赤水市 | 兰溪市 | 扎囊县 | 海伦市 | 三亚市 | 武安市 | 福鼎市 | 茶陵县 | 弥勒县 | 奇台县 | 克什克腾旗 | 永平县 | 榆中县 | 馆陶县 | 长子县 | 土默特右旗 | 鄄城县 | 长丰县 | 徐汇区 | 中阳县 | 曲麻莱县 | 上犹县 | 吉安县 | 邢台县 | 梁平县 | 盱眙县 | 平罗县 | 寻乌县 | 西安市 | 东宁县 | 新丰县 | 崇信县 | 交城县 | 莲花县 | 北海市 | 定结县 | 江华 | 涿州市 | 高阳县 | 盐山县 | 体育 | 图木舒克市 | 新平 | 甘肃省 | 甘孜县 | 新丰县 | 永济市 | 女性 | 小金县 | 高州市 | 阿荣旗 | 岑溪市 | 铜山县 | 美姑县 | 肃宁县 | 红安县 | 都兰县 | 勃利县 | 安阳市 | 得荣县 | 司法 | 兰溪市 | 五莲县 | 张家界市 | 锦州市 | 遂昌县 | 峡江县 | 阳谷县 | 阳新县 | 宁远县 | 石城县 | 长泰县 | 额尔古纳市 | 台安县 | 沙湾县 | 松滋市 | 托克托县 | 新泰市 | 虹口区 | 禄劝 | 莱西市 | 隆德县 | 祁门县 | 略阳县 | 建德市 | 永登县 | 庆元县 | 周口市 | 庄浪县 | 阳曲县 | 开原市 | 嘉兴市 | 富锦市 | 公主岭市 | 永仁县 | 乡城县 | 威远县 | 韶关市 | 宿州市 | 安泽县 | 都兰县 | 雅安市 | 奉贤区 | 乌鲁木齐市 | 宜宾市 | 龙江县 | 腾冲县 | 乾安县 | 威远县 | 教育 | 石首市 | 定西市 | 阿巴嘎旗 | 城步 | 伊金霍洛旗 | 邵阳县 | 荥经县 | 纳雍县 | 布拖县 | 白水县 | 牟定县 | 资兴市 | 凤凰县 | 荆州市 | 郓城县 | 扬州市 | 莫力 | 梓潼县 | 郎溪县 | 邢台市 | 中山市 | 吉林市 | 理塘县 | 保德县 | 上饶市 | 米泉市 | 望奎县 | 康定县 | 特克斯县 | 阳信县 | 康马县 | 定兴县 | 林口县 | 焦作市 | 德州市 | 江西省 | 诸暨市 | 沧源 |