ps:一不小心又寫萬把字了,沒辦法,怕你們看不下去,分成了上下兩部分!
關於ArrayList的學習
ArrayList屬於Java基礎知識,面試中會經常問到,所以作為一個Java從業者,它是你不得不掌握的一個知識點。
可能很多人也不知道自己學過多少遍ArrayList,以及看過多少相關的文章了,但是大部分人都是當時覺得自己會了,過不了多久又忘了,真的到了面試的時候,自己回答的支支吾吾,自己都不滿意
為什麼會這樣?對於ArrayList這樣的知識點的學習,不要靠死記硬背,你要做的是真的理解它!
我這裡建議,如果你真的想清楚的理解ArrayList的話,可以從它的構造函數開始,一步步的讀源碼,最起碼你要搞清楚add這個操作,記住,是源碼
一個問題看看你對ArrayList掌握多少
很多人已經學習過ArrayList了,讀過源碼的也不少,這裡給出一個問題,大家可以看看,以便測試下自己對ArrayLIst是否真的掌握:
請問在ArrayList源碼中DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA是什麼?它們有什麼區別?
怎麼樣?如果你能很輕鬆的回答上來,那麼你掌握的不錯,不想再看本篇文章可以直接出門右拐(我也不知道到哪),如果你覺得不是很清楚,那就跟著我繼續往下,咱們再來把ArrayList中那些重點過一遍!
你覺得ArrayList的重點是啥?
在我看來,ArrayList的一個相當重要的點就是數組擴容技術,我們之前學習過數組,想一下數組是個什麼玩意以及它有啥特點。
隨機訪問,連續內存分佈等等,這些學過的都知道,這裡說一個似乎很容易被忽略的點,那就是數組的刪除,想一下,數組怎麼做刪除?
關於數組刪除的一些思考
關於數組的刪除,我之前也是有疑惑,後來也花時間思考了一番,算是比較通透了,這裡就提一點,數組並沒有提供刪除元素的方法,我們都是怎麼做刪除的?
比如我們要刪除中間的一個元素,怎麼操作,首先我們可以把這個元素置為null,也就把這個元素刪除掉了,此時數組上就空出了一個位置,這樣行嗎?
當我們再次遍歷這個數組的時候是不是還是會遍歷到這個位置,那麼就會報空指針異常,怎麼辦?是的我們可以先判斷,但是這樣的做法不好,怎麼辦呢?
那就是我們可以把這個元素後面的所有元素統一的向前複製,有的地方這裡會說移動,我覺得不夠合理,為啥?
複製是把一個元素拷貝一份放到其他位置,原來位置元素還存在,而移動呢?區別就是移動了,原本的元素就不存在了,而數組這裡是複製,把元素統一的各自向前複製,最終結果就是倒數第一和第二位置上的元素是相同的。
此時的刪除的本質實際上是要刪除的這個元素的後一個元素把要刪除的這個元素給覆蓋了,後面依次都是這樣的操作,可能有點繞,自己想一下。
所以就引出了數組的刪除操作是要進行數組元素的複製操作,也就導致數組刪除操作最壞的時間複雜度是0(n)。
為什麼說這個?因為對理解數組擴容技術很有幫助!
數組擴容技術
上面我們談到了關於數組的刪除操作,我們只是分析了該如何去刪除,但是數組並未提供這樣的方法,如果我們要搞個數組,這個刪除操作還是要我們自己寫代碼去實現的。
不過好在已經有實現了,誰嘞,就是我們今天的主角ArrayList,其實ArrayList就可以看作是數組的一個升級版,ArrayList底層也是使用數組來實現,然後加上了很多操作數組的方法,比如我們上面分析的刪除操作,當然除此之外,還實現了一些其他的方法,然後這就形成了一個新的物種,這就是ArrayList。
本質上ArrayList就是一個普通的類,對數組進行的封裝,擴展其功能
對於數組,我們還了解一點那就是數組一旦確定就不能再被改變,而這個ArrayList卻可以實現自動擴容,有木有覺得很高級,其實也沒啥,因為數組本身特性決定,ArrayList所謂的自動擴容其實也是新創建一個數組而已,因為ArrayList底層就是使用的數組。
我們的重點需要關注的是這個自動擴容的過程,就是怎麼創建一個新的數組,創建完成之後又是怎麼做的,這才是我們關注的重點。
接下來我們看兩種數組擴容方式。
Arrays.copyof
不知道你使用過沒,我們直接看代碼:
<code>public static void main(String[] args) {
int[] a1 = new int[]{1, 2};
for (int a : a1) {
System.out.println(a);
}
System.out.println("-------------拷貝------------");
int[] b1 = Arrays.copyOf(a1, 10);
for (int b : b1) {
System.out.println(b);
}
}/<code>
代碼不多,很簡單,看看輸出結果你就明白了
ok,是不是很簡單,知道這個簡單用法就ok了,接下來看另外一種
System.arraycopy()
這個方法我們看看是個啥:
<code>public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);/<code>
看見沒,native修飾的,一般是使用c/c++寫的,性能很高,我們看看這裡面的這幾個參數都是啥意思:
src:要拷貝的數組 srcPos:要拷貝的數組的起始位置 dest:目標數組 destPos:目標數組的起始位置 length:你要拷貝多少個數據
怎麼樣,知道這幾個參數什麼意思了,那使用就簡單了,我這裡就不顯示了。
ps:以後複製數組別再傻傻的遍歷了,用這個多香
以上兩個方法都是進行數組拷貝的,這個對理解數組擴容技術很重要,而且在ArrayList中也有應用,我們等會會詳細說。
下面咱們開始看看ArrayList的一些源碼,加深我們對ArrayList的理解!
源碼中的ArrayList
一般我們是怎麼用ArrayList的呢?看下面這些代碼:
<code>ArrayList arrayList = new ArrayList();
arrayList.add("hello");
arrayList.add(1);
ArrayList<string> stringArrayList = new ArrayList<>();
stringArrayList.add("hello");/<string>/<code>
簡單,都會吧,就是new一個出來,不過上面的代碼我還想說明一個問題,當你不指定具體類型的時候是可以存儲任意類型的數據的,指定的話就只能存儲特定類型,為啥不指定可以存儲任意類型?
這個問題不做解釋,等會看源碼你就明白了。
看看ArrayList的無參構造函數
一般我們看ArrayList的源碼,都是從它的無參構造函數開始看起的,也就是這個:
<code>new ArrayList();/<code>
好啦,走進去看看這個new ArrayList();構造函數長啥樣吧。
<code>/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}/<code>
咋一看,代碼不多,簡單,裡面就是個賦值操作啊,有兩個新東西elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA,這是啥?
不著急,我們點進去看看
<code>private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access/<code>
這不就是Object數組嘛,好像還真是的,那transient啥意思?它啊,你就記住被它修飾序列化的時候會被忽略掉。
好了,除此之外,就是個數組,對Object類型的。
不好像有點區別啊,DEFAULTCAPACITY_EMPTY_ELEMENTDATA已經指定是個空數組了,而elementData只是聲明,在new一個ArrayList的時候進行了賦值,也就是這樣:
<code>this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;/<code>
咋樣?明白了吧,之前不就說了嘛,ArrayList底層就是一個數組的,這裡你看,new之後不就給你弄個空數組出來嘛,也就是說啊,你要使用ArrayList,一開始先new一下,然後給你搞個空數組出來。
啥?空數組?空數組怎麼行呢?畢竟我們還需要用它存數據嘞,所以啊,重點來了,我們看它的add,也就是添加數據的操作。
看看ArrayList的add
<code>public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}/<code>
就是這個啦,ArrayList不就是使用add來添加數據嘛,我們看看是怎麼操作的,咋一看這段代碼,讓我們感到比較陌生的就是這個方法了
<code>ensureCapacityInternal(size + 1);/<code>
這是啥玩意,翻譯一下
確保內部容量?什麼鬼,這裡還有個size,我們看看是啥?
<code>private int size;/<code>
就是一個變量啊,我們再看看這段代碼
<code>public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}/<code>
尤其是
<code>elementData[size++] = e;/<code>
知道了嘛?我們之前不是已經創建了一個空數組,不就是elementData嘛,這好像是在往數組裡面放數據啊,不過不對啊,不是空數組嘛?咋能放數據,這不是前面還有這一步嘛
<code>ensureCapacityInternal(size + 1);/<code>
是不是有想法了,這一步應該就是把數組的容量給確定下來的,趕緊進去看看
<code>private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}/<code>
就是這個了,這一步很重要:
<code>if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}/<code>
也好理解吧,就是先判斷下現在這個ArrayList的底層數組elementData 是不是剛創建的的空數組,這裡肯定是啊,然後開始執行
<code>minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);/<code>
留一個疑問,你們知道minCapacity 到底是個啥嘛?這可是很重要的,我們下回再說!
未完待續!
我是一名從事多年開發的java老程序猿員,目前辭職在做自己的java私人訂製課程,今年年初我花了一個月整理了一份最適合2019年學習的java學習乾貨資料,從最基礎的javase到spring各種框架都有整理,送給每一位java小夥伴,想要獲取的可以關注我的頭條號並在後臺私信我:02,即可免費獲取。
鏈接:https://url.cn/5zdUIwm
閱讀更多 程序猿168 的文章