ArrayList 源碼分析
      
    
      
        網友投稿
        812
        2022-05-30
		    
      
    
                    
      公眾號原文：ArrayList 源碼分析
      博客原文：ArrayList 源碼分析
      以下源碼分析使用的 Java 版本為 1.8
      1. 概覽
      ArrayList 是基于數組實現的，繼承 AbstractList， 實現了 List、RandomAccess、Cloneable、Serializable 接口，支持隨機訪問。
      java.util?public?class?ArrayList?extends?AbstractList
      implements?List,?RandomAccess,?Cloneable,?java.io.Serializable
      2. Java Doc 關鍵點：
      實現List接口的動態數組，容量大小為 capacity，默認的容量大小 10，會自動擴容
      公眾號原文：ArrayList 源碼分析
      博客原文：ArrayList 源碼分析
      以下源碼分析使用的 Java 版本為 1.8
      ArrayList 是基于數組實現的，繼承 AbstractList， 實現了 List、RandomAccess、Cloneable、Serializable 接口，支持隨機訪問。
      java.util?public?class?ArrayList?extends?AbstractList
      implements?List,?RandomAccess,?Cloneable,?java.io.Serializable
      實現List接口的動態數組，容量大小為 capacity，默認的容量大小 10，會自動擴容
      可包含空元素 null
      size, isEmpty, get, set, iterator, and listIterator 等操作的復雜度為 O(1)，The add operation runs in amortized constant time, that is, adding n elements requires O(n) time，其它操作為線性時間
      非線程安全，多線程環境下必須在外部增加同步限制，或者使用包裝對象 List list = Collections.synchronizedList(new ArrayList(…));
      快速失敗：在使用迭代器時，調用迭代器的添加、修改、刪除方法，將拋出 ConcurrentModificationException 異常，但是快速失敗行為不是硬保證的，只是盡最大努力
      當添加第一個元素時，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的任何空ArrayList都將擴展為默認的capacity
      private?static?final?int?DEFAULT_CAPACITY?=?10;?//?默認容量大小
      private?static?final?Object[]?EMPTY_ELEMENTDATA?=?{};?//?ArrayList空實例共享的一個空數組
      private?static?final?Object[]?DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};?//?ArrayList空實例共享的一個空數組，用于默認大小的空實例。與?EMPTY_ELEMENTDATA?分開，這樣就可以了解當添加第一個元素時需要創建多大的空間
      transient?Object[]?elementData;?//?真正存儲ArrayList中的元素的數組
      private?int?size;???//?存儲ArrayList的大小，注意不是elementData的長度
      private?static?final?int?MAX_ARRAY_SIZE?=?Integer.MAX_VALUE?-?8;?//?數組的最大長度
      protected?transient?int?modCount?=?0;?//AbstractList類的，表示?elementData在結構上被修改的次數,每次add或者remove它的值都會加1
      //?無參構造方法，默認初始容量10
      public?ArrayList()?{
      this.elementData?=?DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
      }
      //?提供初始容量的構造方法
      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);
      }
      }
      //?通過一個容器來初始化
      public?ArrayList(Collection?c)?{
      elementData?=?c.toArray();
      if?((size?=?elementData.length)?!=?0)?{?//?c.toArray?返回的可能不是??Object[]
      if?(elementData.getClass()?!=?Object[].class)
      elementData?=?Arrays.copyOf(elementData,?size,?Object[].class);
      }?else?{
      this.elementData?=?EMPTY_ELEMENTDATA;?//?replace?with?empty?array.
      }
      }
      添加元素時使用 ensureCapacityInternal() 方法來保證容量足夠，size + 1 為最少需要的空間大小，如果elementData的長度不夠時，需要使用 grow() 方法進行擴容
      //?添加一個元素
      public?boolean?add(E?e)?{
      ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
      elementData[size++]?=?e;
      return?true;
      }
      //?計算最少需要的容量
      private?static?int?calculateCapacity(Object[]?elementData,?int?minCapacity)?{
      if?(elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{
      //?默認的空實例第一次添加元素時，使用默認的容量大小與minCapacity的最大值
      return?Math.max(DEFAULT_CAPACITY,?minCapacity);
      }
      return?minCapacity;
      }
      private?void?ensureCapacityInternal(int?minCapacity)?{
      ensureExplicitCapacity(calculateCapacity(elementData,?minCapacity));
      }
      private?void?ensureExplicitCapacity(int?minCapacity)?{
      modCount++;
      if?(minCapacity?-?elementData.length?>?0)?//?需要的容量大于elementData的長度
      grow(minCapacity);??//?進行擴容
      }
      擴容：當新容量小于等于 MAX_ARRAY_SIZE 時，新容量的大小為 oldCapacity + (oldCapacity >> 1) 與 minCapacity 之間的較大值 ，也就是舊容量的 1.5 倍與 minCapacity 之間的較大值
      private?void?grow(int?minCapacity)?{
      int?oldCapacity?=?elementData.length;?//?原本的容量
      int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);?//?新的容量
      if?(newCapacity?-?minCapacity?
      newCapacity?=?minCapacity;
      if?(newCapacity?-?MAX_ARRAY_SIZE?>?0)
      newCapacity?=?hugeCapacity(minCapacity);
      elementData?=?Arrays.copyOf(elementData,?newCapacity);
      }
      private?static?int?hugeCapacity(int?minCapacity)?{
      if?(minCapacity?
      throw?new?OutOfMemoryError();
      return?(minCapacity?>?MAX_ARRAY_SIZE)???Integer.MAX_VALUE?:?MAX_ARRAY_SIZE;
      }
      最后調用 Arrays.copyOf 復制原數組，將 elementData 賦值為得到的新數組。由于數組復制代價較高，所以建議在創建 ArrayList 對象時就指定大概的容量大小，減少擴容操作的次數
      public?class?Arrays?{
      public?static??T[]?copyOf(T[]?original,?int?newLength)?{
      return?(T[])?copyOf(original,?newLength,?original.getClass());
      }
      public?static??T[]?copyOf(U[]?original,?int?newLength,?Class?newType)?{
      @SuppressWarnings("unchecked")
      T[]?copy?=?((Object)newType?==?(Object)Object[].class)
      ??(T[])?new?Object[newLength]?:?(T[])?Array.newInstance(newType.getComponentType(),?newLength);
      System.arraycopy(original,?0,?copy,?0,?Math.min(original.length,?newLength));
      return?copy;
      }
      //...
      }
      通過 addAll 添加一個集合中所有元素時的擴容：至少需要的容量為兩個集合的長度之和，同樣是通過 ensureCapacityInternal() 來保證容量是足夠的，然后調用 System.arraycopy 將要添加的集合中的元素復制到原集合已有元素的后面
      public?boolean?addAll(Collection?c)?{
      Object[]?a?=?c.toArray();
      int?numNew?=?a.length;
      ensureCapacityInternal(size?+?numNew);??//?Increments?modCount
      System.arraycopy(a,?0,?elementData,?size,?numNew);?//?復制元素到原數組尾部
      size?+=?numNew;
      return?numNew?!=?0;
      }
      刪除指定下標的元素時，如果下標沒有越界，則取出下標對應的值，然后將數組中該下標后面的元素都往前挪1位，需要挪的元素數量是 size - index - 1，時間復雜度為 O(n)，所以刪除元素的代價挺高
      public?E?remove(int?index)?{
      rangeCheck(index);?//?檢查下標是否在數組的長度范圍內
      modCount++;
      E?oldValue?=?elementData(index);?//?下標為index的值
      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;
      }
      private?void?rangeCheck(int?index)?{
      if?(index?>=?size)
      throw?new?IndexOutOfBoundsException(outOfBoundsMsg(index));
      }
      刪除在指定集合中的所有元素 removeAll，刪除不在指定集合中的所有元素 retainAll
      這兩者都是通過 batchRemove 來批量刪除
      //?刪除在指定集合中的所有元素
      public?boolean?removeAll(Collection?c)?{
      Objects.requireNonNull(c);??//?c?不能為null
      return?batchRemove(c,?false);
      }
      //?刪除不在指定集合中的所有元素，也就是只保留指定集合中的元素，其它的都刪除掉
      public?boolean?retainAll(Collection?c)?{
      Objects.requireNonNull(c);
      return?batchRemove(c,?true);
      }
      //?批量刪除
      private?boolean?batchRemove(Collection?c,?boolean?complement)?{
      final?Object[]?elementData?=?this.elementData;
      int?r?=?0,?w?=?0;???//?r為當前下標，w為當前需要保留的元素的數量（或者說是下一個需保留元素的下標）
      boolean?modified?=?false;
      try?{
      for?(;?r?
      if?(c.contains(elementData[r])?==?complement)???//?判斷元素?elementData[r]?是否需要刪除
      elementData[w++]?=?elementData[r];
      }?finally?{
      //?r?!=?size?的情況可能是?c.contains()?拋出了異常，將?r?之后的元素復制到?w?之后
      if?(r?!=?size)?{
      System.arraycopy(elementData,?r,?elementData,?w,?size?-?r);
      w?+=?size?-?r;
      }
      if?(w?!=?size)?{
      //?w?之后的元素設置為?null?以讓?GC?回收
      for?(int?i?=?w;?i?
      elementData[i]?=?null;
      modCount?+=?size?-?w;
      size?=?w;
      modified?=?true;
      }
      }
      return?modified;
      }
      刪除第一個值為指定值的元素 remove(Object o)，參數 o 可以為 null
      fastRemove(int index) 與 remove(int index) 幾乎一樣，只不過不返回被刪除的元素
      public?boolean?remove(Object?o)?{
      if?(o?==?null)?{
      for?(int?index?=?0;?index?
      if?(elementData[index]?==?null)?{
      fastRemove(index);
      return?true;
      }
      }?else?{
      for?(int?index?=?0;?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)
      System.arraycopy(elementData,?index+1,?elementData,?index,
      numMoved);
      elementData[--size]?=?null;?//?clear?to?let?GC?do?its?work
      }
      ArrayList 支持三種方式：
      for循環下標遍歷
      迭代器(Iterator和ListIterator)
      foreach 語句
      迭代器 Iterator 和 ListIterator 的主要區別：：
      ArrayList 的迭代器 Iterator 和 ListIterator 在《設計模式 | 迭代器模式及典型應用》這篇文章中有過詳細介紹，這里只做一個小結
      ListIterator 有 add() 方法，可以向List中添加對象，而 Iterator 不能
      ListIterator 和 Iterator 都有 hasNext() 和 next() 方法，可以實現順序向后遍歷，但是 ListIterator 有 hasPrevious() 和 previous() 方法，可以實現逆向（順序向前）遍歷。Iterator 就不可以。
      ListIterator 可以定位當前的索引位置，nextIndex() 和 previousIndex() 可以實現。Iterator 沒有此功能。
      都可實現刪除對象，但是 ListIterator 可以實現對象的修改，set() 方法可以實現。Iierator 僅能遍歷，不能修改
      foreach 循環：
      foreach 循環涉及到一個 Consumer 接口，接收一個泛型的參數T，當調用 accept 方法時，Stream流中將對 accept 的參數做一系列的操作
      public?void?forEach(Consumer?action)?{
      Objects.requireNonNull(action);
      final?int?expectedModCount?=?modCount;??//?記錄當前的?modCount
      @SuppressWarnings("unchecked")
      final?E[]?elementData?=?(E[])?this.elementData;
      final?int?size?=?this.size;
      for?(int?i=0;?modCount?==?expectedModCount?&&?i?
      action.accept(elementData[i]);
      }
      if?(modCount?!=?expectedModCount)?{
      throw?new?ConcurrentModificationException();
      }
      }
      ArrayList 有兩個屬性被 transient 關鍵字 修飾，transient 關鍵字 的作用：讓某些被修飾的成員屬性變量不被序列化
      transient?Object[]?elementData;
      protected?transient?int?modCount?=?0;
      為什么最為重要的數組元素要用 transient 修飾呢？
      跟Java的序列化機制有關，這里列出Java序列化機制的幾個要點：
      需要序列化的類必須實現java.io.Serializable接口，否則會拋出NotSerializableException異常
      若沒有顯示地聲明一個serialVersionUID變量，Java序列化機制會根據編譯時的class自動生成一個serialVersionUID作為序列化版本比較（驗證一致性），如果檢測到反序列化后的類的serialVersionUID和對象二進制流的serialVersionUID不同，則會拋出異常
      Java的序列化會將一個類包含的引用中所有的成員變量保存下來（深度復制），所以里面的引用類型必須也要實現java.io.Serializable接口
      當某個字段被聲明為transient后，默認序列化機制就會忽略該字段，反序列化后自動獲得0或者null值
      靜態成員不參與序列化
      每個類可以實現readObject、writeObject方法實現自己的序列化策略，即使是transient修飾的成員變量也可以手動調用ObjectOutputStream的writeInt等方法將這個成員變量序列化。
      任何一個readObject方法，不管是顯式的還是默認的，它都會返回一個新建的實例，這個新建的實例不同于該類初始化時創建的實例
      每個類可以實現private Object readResolve()方法，在調用readObject方法之后，如果存在readResolve方法則自動調用該方法，readResolve將對readObject的結果進行處理，而最終readResolve的處理結果將作為readObject的結果返回。readResolve的目的是保護性恢復對象，其最重要的應用就是保護性恢復單例、枚舉類型的對象
      所以問題的答案是：ArrayList 不想用Java序列化機制的默認處理來序列化 elementData 數組，而是通過 readObject、writeObject 方法自定義序列化和反序列化策略。
      問題又來了，為什么不用Java序列化機制的默認處理來序列化 elementData 數組呢？
      答案是因為效率問題，如果用默認處理來序列化的話，如果 elementData 的長度有100，但是實際只用了50，其實剩余的50是可以不用序列化的，這樣可以提高序列化和反序列化的效率，節省空間。
      現在來看 ArrayList 中自定義的序列化和反序列化策略
      private?static?final?long?serialVersionUID?=?8683452581122892189L;
      private?void?writeObject(java.io.ObjectOutputStream?s)?throws?java.io.IOException{
      int?expectedModCount?=?modCount;
      s.defaultWriteObject();?//?默認的序列化策略，序列化其它的字段
      s.writeInt(size);???//?實際用的長度，而不是容量
      for?(int?i=0;?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;
      //?Read?in?size,?and?any?hidden?stuff
      s.defaultReadObject();
      s.readInt();?//?ignored
      if?(size?>?0)?{
      ArrayList 源碼分析
      int?capacity?=?calculateCapacity(elementData,?size);
      SharedSecrets.getJavaOISAccess().checkArray(s,?Object[].class,?capacity);
      ensureCapacityInternal(size);
      Object[]?a?=?elementData;
      for?(int?i=0;?i
      a[i]?=?s.readObject();
      }
      }
      }
      modCount 用來記錄 ArrayList 結構發生變化的次數，如果一個動作前后 modCount 的值不相等，說明 ArrayList 被其它線程修改了
      如果在創建迭代器之后的任何時候以任何方式修改了列表（增加、刪除、修改），除了通過迭代器自己的remove 或 add方法，迭代器將拋出 ConcurrentModificationException 異常
      需要注意的是：這里異常的拋出條件是檢測到 modCount != expectedmodCount，如果并發場景下一個線程修改了modCount值時另一個線程又 "及時地" 修改了expectedmodCount值，則異常不會拋出。所以不能依賴于這個異常來檢測程序的正確性。
      private?void?writeObject(java.io.ObjectOutputStream?s)?throws?java.io.IOException{
      int?expectedModCount?=?modCount;????//?記錄下當前的?modCount
      //?一些操作之后....
      if?(modCount?!=?expectedModCount)?{?//?比較現在與之前的?modCount，不相等表示在中間過程中被修改了
      throw?new?ConcurrentModificationException();
      }
      }
      private?void?writeObject(java.io.ObjectOutputStream?s)?throws?java.io.IOException{
      int?expectedModCount?=?modCount;
      //?一些操作之后....
      if?(modCount?!=?expectedModCount)?{
      throw?new?ConcurrentModificationException();
      }
      }
      public?void?forEach(Consumer?action)?{
      final?int?expectedModCount?=?modCount;
      //?一些操作之后....
      if?(modCount?!=?expectedModCount)?{
      throw?new?ConcurrentModificationException();
      }
      }
      public?boolean?removeIf(Predicate?filter)?{
      final?int?expectedModCount?=?modCount;
      //?一些操作之后....
      if?(modCount?!=?expectedModCount)?{
      throw?new?ConcurrentModificationException();
      }
      }
      public?void?replaceAll(UnaryOperator?operator)?{
      final?int?expectedModCount?=?modCount;
      //?一些操作之后....
      if?(modCount?!=?expectedModCount)?{
      throw?new?ConcurrentModificationException();
      }
      modCount++;?//?修改了要加一
      }
      public?void?sort(Comparator?c)?{
      final?int?expectedModCount?=?modCount;
      //?一些操作之后....
      if?(modCount?!=?expectedModCount)?{
      throw?new?ConcurrentModificationException();
      }
      modCount++;
      }
      //?內部迭代器
      private?class?Itr?implements?Iterator?{
      public?void?forEachRemaining(Consumer?consumer)?{
      checkForComodification();
      }
      final?void?checkForComodification()?{
      if?(modCount?!=?expectedModCount)
      throw?new?ConcurrentModificationException();
      }
      }
      后記
      歡迎評論、轉發、分享，您的支持是我最大的動力
      更多內容可訪問我的個人博客：http://laijianfeng.org
      關注【小旋鋒】微信公眾號，及時接收博文推送
      
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

      
    
      
         
        

    
       
    
                    
      
        
      
                        上一篇:《Spark數據分析：基于Python語言 》
                    
      
        
      
                        下一篇:關于errno的后事妥善處理
                    
      
    
      

      

      
    
      
        相關文章
    
      
    

      
    
                            
      
          
      
               
      
      
    
      
  
      

  

      
       
  
      
    
  
      
  
      










亚洲AV无码专区在线厂|
亚洲色中文字幕无码AV|
亚洲欧美一区二区三区日产|
亚洲色图.com|
久久亚洲私人国产精品|
亚洲视频.com|
亚洲视频国产精品|
亚洲福利电影一区二区?|
亚洲综合在线观看视频|
亚洲AV无码成人专区片在线观看
|
亚洲精品老司机在线观看|
国产午夜亚洲精品不卡免下载
|
亚洲成AV人片在WWW|
亚洲av无码专区在线观看下载|
亚洲成av人在线观看网站|
亚洲成av人在线观看网站|
五月婷婷亚洲综合|
亚洲无码精品浪潮|
中文字幕亚洲乱码熟女一区二区|
永久亚洲成a人片777777|
国产亚洲综合色就色|
无码久久精品国产亚洲Av影片|
亚洲电影中文字幕|
久久精品国产亚洲77777|
亚洲国产精品综合久久网各|
亚洲一区二区三区播放在线|
亚洲一区二区三区写真|
亚洲av无码兔费综合|
亚洲AⅤ视频一区二区三区
|
亚洲妇女水蜜桃av网网站|
亚洲一区二区三区四区视频|
亚洲一区二区无码偷拍|
午夜亚洲WWW湿好爽|
亚洲日韩中文字幕日韩在线|
亚洲日韩精品A∨片无码|
亚洲2022国产成人精品无码区
|
国产91成人精品亚洲精品|
国产精品亚洲综合一区|
亚洲AV永久青草无码精品|
亚洲综合久久1区2区3区|
国产精品亚洲综合久久|