arraylist擴容(Java中ArrayList底層擴容原理以及擴容操作的示例分析)

ArrayList是Java集合框架中比較常用的一個數據結構,它的底層是是基于數組實現的。

第一章 前言概述

第01節 概述

底層說明

ArrayList是List的實現類,它的底層是用Object數組存儲,線程不安全

后期應用

適合用于頻繁的查詢工作,因為底層是數組,可以快速通過數組下標進行查找

第02節 區別

小結

ArrayList 集合的特點:

1. 線程不安全

2. 底層數據結構是數組(查詢快,增刪慢,支持快速隨機訪問)

3. 內存占用會存在部分浪費,末尾會預留一部分容量空間

第二章 核心代碼

第01節 成員變量

代碼

publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{/***默認初始容量大小,默認初始化容量為10*/privatestaticfinalintDEFAULT_CAPACITY=10;/***空數組。當集合內容置空的時候,底層使用空數組標記*/privatestaticfinalObject[]EMPTY_ELEMENTDATA={};/***用于無參數構造方法,創建對象的時候,使用這個數組定義。*相比上面的數組EMPTY_ELEMENTDATA可以進行區分,知道在添加元素的過程當中,容量增加多少*/privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};/***保存ArrayList數據的數組,這個數組會不斷的改變,前面沒有被final修飾表示地址值會發生的變化*/transientObject[]elementData;//non-privatetosimplifynestedclassaccess/***ArrayList所包含的元素個數,也就是在ArrayList集合底層,通過size()方法,獲取到的元素個數*/privateintsize;}

補充

1.ArrayList集合底層存在6個成員變量還有一個privatestaticfinallongserialversionuid=8683452581122892189L;序列化使用,目前針對于當前的操作過程當中,暫時不會使用得到。2.ArrayList集合當中核心的兩個成員變量A.底層維護數組transientObject[]elementData;B.存儲的元素個數privateintsize;

第02節 構造方法

代碼

publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{/***構造一個初始長度為0的空數組。*/publicArrayList(){this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/***在構造方法當中,傳遞一個參數集合c,將集合c轉換成為新的列表*elementData當中的數據,就是新集合存放的數據*c.toArray就是將原始集合的數據取出*如果取出的集合長度不為零的情況下,則復制參數集合c到elementData當中*如果取出的集合長度為零的情況下,則賦值為空數組EMPTY_ELEMENTDATA*/publicArrayList(Collection<?extendsE>c){elementData=c.toArray();if((size=elementData.length)!=0){if(elementData.getClass()!=Object[].class)elementData=Arrays.copyOf(elementData,size,Object[].class);}else{this.elementData=EMPTY_ELEMENTDATA;}}/***指定參數的長度大小*如果初始化的長度大于0,則返回新的數組*如果初始化的長度等于0,則返回默認的空數組作為集合this.elementData=EMPTY_ELEMENTDATA;*如果初始化的長度小于0,則出現非法參數異常*/publicArrayList(intinitialCapacity){if(initialCapacity>0){this.elementData=newObject[initialCapacity];}elseif(initialCapacity==0){this.elementData=EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("IllegalCapacity:"+initialCapacity);}}}

補充(一) 無參構造創建對象

補充(二)帶參構造創建對象,帶有int類型參數

補充(三)帶參構造創建對象,帶有 集合類型參數

第三章 擴容操作

第01節 擴容代碼

核心方法介紹

來自于ArrayList集合當中的方法:1.publicbooleanadd(Ee){...}2.privatevoidadd(Ee,Object[]elementData,ints){....}3.privateObject[]grow()4.privateObject[]grow(intminCapacity)來自于其他類當中的功能1.Arrays.copyOf(elementData,newCapacity);表示來自于數組工具類Arrays當中的copyOf()底層使用的是System.arraycopy()方法2.Math.max(DEFAULT_CAPACITY,minCapacity)表示來自于數學工具類Math當中的max()方法,比較兩個數據最大值,取較大者,返回

核心代碼解釋

publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{/***將指定的元素添加到此集合的末尾位置**modCount是來自于父類的AbstractList當中的成員變量*add(e,elementData,size)調用自己下面的重載方法*returntrue表示當前的方法,一定可以添加成功,因為List系列的集合添加數據都是允許成功的true如果是Set此方法返回false*/publicbooleanadd(Ee){modCount++;add(e,elementData,size);returntrue;}/***這個方法是私有方法,僅僅自己可以使用。不允許外界訪問得到。便于上面的add()方法重載調用的*參數1:表示需要添加的元素數據Ee*參數2:表示成員變量當中,需要維護管理的底層數組Object[]elementData*參數3:表示成員變量當中,size容器elementData當中存放的真實有效的數據個數*方法里面的邏輯:當size已經等于了內部容器elementData的最大長度,則準備進行擴容的操作,擴容使用grow()方法*無論上面是否進行了擴容的操作,這里都需要將添加的元素賦值到數組當中,也就是elementData[s]=e;*并且將當前成員變量的size在原始數據的基礎上面,增加1,表示添加了新的元素之后,長度變化了,增加了1*/privatevoidadd(Ee,Object[]elementData,ints){if(s==elementData.length)elementData=grow();elementData[s]=e;size=s+1;}/***這個方法是私有方法,僅僅自己可以使用。不允許外界訪問得到。便于上面的add()方法調用的*方法的內部調用了ArrayList當中自己重載的方法grow(size+1)同時傳入了參數。*這里參數的含義,表示的是集合當中總長度size+1表示在原始size基礎上增加1*方法的返回值是一個新的數組,也就是擴容之后的數組*/privateObject[]grow(){returngrow(size+1);}/***這個方法是私有方法,僅僅自己可以使用。不允許外界訪問得到。便于上面的grow()方法調用的*這里的參數minCapacity,就是上面傳入的參數size+1,也就是說最小容量minCapacity=size+1*方法體當中的執行邏輯:*1.獲取到了底層維護數組的長度intoldCapacity=elementData.length;這里就是舊容量oldCapacity*2.判斷舊容量oldCapacity是否小于0,也就是else的邏輯,*如果滿足if當中的邏輯,則表示舊數組當中存在數據,并且舊數組并不是默認容量的空數組地址值*說明:擴容過的就不會是之前默認DEFAULTCAPACITY_EMPTY_ELEMENTDATA的地址值*在這種情況下,就會得到1.5被的數組長度整數,傳遞給Arrays.copyOf()方法進行擴容,得到新數組返回*如果滿足else當中的邏輯,則返回DEFAULT_CAPACITY和minCapacity較大值。*說明:DEFAULT_CAPACITY值表示的是成員變量,默認為10*說明:minCapacity在低于10的時候,表示的會是擴容添加的長度1,2,3..9.10.11..*/privateObject[]grow(intminCapacity){intoldCapacity=elementData.length;if(oldCapacity>0||elementData!=DEFAULTCAPACITY_EMPTY_ELEMENTDATA){intnewCapacity=ArraysSupport.newLength(oldCapacity,minCapacity-oldCapacity,/*minimumgrowth*/oldCapacity>>1/*preferredgrowth*/);returnelementData=Arrays.copyOf(elementData,newCapacity);}else{returnelementData=newObject[Math.max(DEFAULT_CAPACITY,minCapacity)];}}}