• 一篇文章帶您讀懂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下载贵州快三开奖 海门市 | 延川县 | 开鲁县 | 岚皋县 | 浦城县 | 瓮安县 | 报价 | 洮南市 | 古浪县 | 神池县 | 邵武市 | 海丰县 | 从江县 | 宜川县 | 和硕县 | 乌鲁木齐市 | 西藏 | 石棉县 | 涪陵区 | 仙桃市 | 罗田县 | 宿迁市 | 马公市 | 琼海市 | 大连市 | 独山县 | 福清市 | 平安县 | 盘山县 | 耒阳市 | 定结县 | 视频 | 积石山 | 襄汾县 | 东明县 | 雷山县 | 静宁县 | 浪卡子县 | 蒙自县 | 靖州 | 自贡市 | 南召县 | 亳州市 | 北票市 | 通道 | 广东省 | 武夷山市 | 南投县 | 鹤峰县 | 固阳县 | 黔西县 | 奉化市 | 攀枝花市 | 临漳县 | 孝昌县 | 莫力 | 游戏 | 达拉特旗 | 进贤县 | 巫溪县 | 亚东县 | 黄大仙区 | 司法 | 印江 | 铜川市 | 吉隆县 | 福泉市 | 汕尾市 | 古丈县 | 绍兴县 | 北宁市 | 通渭县 | 彭州市 | 哈尔滨市 | 泊头市 | 宣汉县 | 松江区 | 晋宁县 | 乐清市 | 松潘县 | 长海县 | 宁乡县 | 麻阳 | 无极县 | 宁德市 | 连州市 | 玛多县 | 永靖县 | 山东 | 贺兰县 | 南涧 | 洛川县 | 固原市 | 马关县 | 贵港市 | 安丘市 | 平度市 | 文水县 | 石棉县 | 涟水县 | 永德县 | 怀远县 | 读书 | 惠安县 | 马公市 | 泰宁县 | 开远市 | 客服 | 林口县 | 桑植县 | 云林县 | 卓资县 | 大连市 | 辉南县 | 于都县 | 高安市 | 微山县 | 濮阳市 | 崇仁县 | 湖州市 | 方正县 | 定州市 | 尉犁县 | 海丰县 | 大安市 | 元朗区 | 新野县 | 饶阳县 | 信宜市 | 公主岭市 | 炉霍县 | 平定县 | 湖南省 | 景谷 | 沁水县 | 开封县 | 大足县 | 轮台县 | 建昌县 | 太仓市 | 东平县 | 安义县 | 建始县 | 新野县 | 文登市 | 威海市 | 滁州市 | 阿荣旗 | 安平县 | 佛坪县 | 隆昌县 | 武平县 | 甘孜 | 钟祥市 | 民和 | 中宁县 | 黄石市 | 吐鲁番市 | 嵊泗县 | 长顺县 | 吕梁市 | 日照市 | 嘉黎县 | 高阳县 | 苏尼特右旗 | 峡江县 | 石台县 | 泉州市 | 海伦市 | 鄂尔多斯市 | 克什克腾旗 | 东山县 | 通化市 | 武川县 | 乌鲁木齐县 | 贡嘎县 | 辰溪县 | 龙江县 | 临夏市 | 东乡县 | 乌拉特后旗 | 普兰县 | 梅河口市 | 岳池县 | 孝义市 | 高唐县 | 清水县 | 吴桥县 | 金山区 | 鄢陵县 | 南丹县 | 芦山县 | 泾阳县 | 两当县 | 汽车 | 会宁县 | 英超 | 丽江市 | 井研县 | 临沭县 | 伊春市 | 游戏 | 阆中市 | 望奎县 | 怀化市 | 博湖县 | 翁牛特旗 |