arraylist(ArrayList是什么)

目錄

• 一、ArrayList 了解過嗎?它是啥?有啥用?

• 二、ArrayList 如何指定底層數組大小的

• 三、數組的大小一旦被規定就無法改變

• 四、ArrayList 具體是怎么添加數據的

• 五、ArrayList 又是如何刪除數據的呢

• 六、ArrayList 是線程安全的嗎?不安全的表現

• 七、為什么線程不安全還要用它呢

一、ArrayList 了解過嗎?它是啥?有啥用?

眾所周知,Java 集合框架擁有兩大接口 Collection 和 Map,其中,Collection 麾下三生子 List、Set 和 Queue。ArrayList 就實現了 List 接口,其實就是一個數組列表,不過作為 Java 的集合框架,它只能存儲對象引用類型,也就是說當我們需要裝載的數據是諸如 int、float 等基本數據類型的時候,必須把它們轉換成對應的包裝類。

ArrayList 的底層實現是一個 Object 數組:

既然它是基于數組實現的,數組在內存空間中是連續分配的,那必然查詢速率非?？?不過當然也肯定逃不過增刪效率低的缺陷。

另外,和 ArrayList 一樣同樣實現了 List 接口的、我們比較常用的還有 LinkedList。LinkedList 比較特殊,它不僅實現了 List 接口,還實現了 Queue 接口,所以你可以看見 LinkedList 經常被當作隊列使用:

Queue<Integer>queue=newLinkedList<>();

LinkedList 人如其名,它的底層自然是基于鏈表的,而且還是個雙向鏈表。鏈表的特性和數組正好是反的,由于沒有索引,所以查詢效率低,但是增刪速度快。

二、ArrayList 如何指定底層數組大小的

OK,首先,既然咱真正存儲數據的地方是數組,那我們初始化 ArrayList 的時候自然要給數組分配一個大小,開辟一個內存空間。我們先來看看 ArrayList 的無參構造函數:

可以看到,它為底層的 Object 數組也就是 elementData 賦值了一個默認的空數組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。也就是說,使用無參構造函數初始化 ArrayList 后,它當時的數組容量為 0 。

這給咱初始化一個容量為 0 的數組有啥用?啥也存不了啊?別急,如果使用了無參構造函數來初始化 ArrayList, 只有當我們真正對數據進行添加操作 add 時,才會給數組分配一個默認的初始容量 DEFAULT_CAPACITY = 10?？聪聢D:

說完了無參構造,ArrayList 的有參構造函數就是中規中矩了,按照用戶傳入的大小開辟數組空間:

三、數組的大小一旦被規定就無法改變

ArrayList 是怎么對底層數組進行擴容的?

ArrayList 的底層實現是 Object 數組,我們知道,數組的大小一旦被規定就無法改變。那如果我們不斷的往里面添加數據的話,ArrayList 是如何進行擴容的呢?或者說 ArrayList 是如何實現存放任意數量對象的呢?

OK,擴容發生在啥時候?那肯定是我們往數組中新加入一個元素但是發現數組滿了的時候。沒錯,我們去 add 方法中看看 ArrayList 是怎么做擴容的:

ensureExplicitCapacity 判斷是否需要進行擴容,很顯然,grow 方法是擴容的關鍵:

說實話,別的都不用看了,看上面圖中的黃色框框就知道 ArrayList 是怎么擴容的了:擴容后的數組長度 = 當前數組長度 + 當前數組長度 / 2。最后使用 Arrays.copyOf 方法直接把原數組中的數組 copy 過來,需要注意的是,Arrays.copyOf 方法會創建一個新數組然后再進行拷貝。

舉個例子畫個圖來演示一下:

四、ArrayList 具體是怎么添加數據的

OK,add 方法我們剛剛講了一半,添加數據前會先判斷一下是否需要擴容,真正的添加數據的操作在下半部分:

先講下 add(int index, E element) 這個方法的含義,就是在指定索引 index 處插入元素 element。比如說 ArrayList.add(0, 3),意思就是在頭部插入元素 3。

再來看看 add 方法的核心 System.arraycopy,這個方法有 5 個參數:

• elementData:源數組

• index:從源數組中的哪個位置開始復制

• elementData:目標數組

• index + 1:復制到目標數組中的哪個位置

• size - index:要復制的源數組中數組元素的數量

解釋一下上面代碼中 arraycopy 的意思,舉個例子,我們想要在 index = 5 的位置插入元素,首先,我們會復制一遍源數組 elementData(這里我們稱復制的數組為新數組吧),然后把源數組中從 index = 5 的位置開始到數組末尾的元素,放到新數組的 index + 1 = 6 的位置上:

于是,這就給我們要新增的元素騰出了位置,然后在新數組 index = 5 的位置放入元素 element 就完成了添加的操作:

顯然,不用多說,ArrayList 的將數據插入到指定位置的操作性能非常低下,因為要開辟新數組復制元素啊,要是涉及到擴容那就更慢了。

另外,ArrayList 還內置了一個直接在末尾添加元素的 add 方法,不用復制數組,直接 size ++ 就好,這個方法應該是我們最常使用的:

五、ArrayList 又是如何刪除數據的呢

Ctrl + F 找到 remove 方法,就這?和添加一個道理,也是復制數組

舉個例子,假設我們要刪除數組的 index = 5 的元素,首先,我們會復制一遍源數組,然后把源數組中從 index + 1 = 6 的位置開始到數組末尾的元素,放到新數組的 index = 5 的位置上:

也就是說 index = 5 的元素直接被覆蓋掉了,給了你被刪除的感覺。同樣的,它的效率自然也是十分低下的

六、ArrayList 是線程安全的嗎?不安全的表現

ArrayList 和 LinkedList 都不是線程安全的,我們以在末尾添加元素的 add 方法為例,來看看 ArrayList 線程不安全的表現是啥:

黃色框里的并不是一個原子操作,它由兩步操作構成:

elementData[size]=e;size=size+1;

在單線程執行這兩條代碼時,那當然沒有任何問題,但是當多線程環境下執行時,可能就會發生一個線程添加的值覆蓋另一個線程添加的值。舉個例子:

• 假設 size = 0,我們要往這個數組的末尾添加元素

• 線程 A 開始添加一個元素,值為 A。此時它執行第一條操作,將 A 放在了數組 elementData 下標為 0 的位置上

• 接著線程 B 剛好也要開始添加一個值為 B 的元素,且走到了第一步操作。此時線程 B 獲取到的 size 值依然為 0,于是它將 B 也放在了 elementData 下標為 0 的位置上

• 線程 A 開始增加 size 的值,size = 1

• 線程 B 開始增加 size 的值,size = 2

這樣,線程 A、B 都執行完畢后,理想的情況應該是 size = 2,elementData[0] = A,elementData[1] = B。而實際情況變成了 size = 2,elementData[0] = B(線程 B 覆蓋了線程 A 的操作),下標 1 的位置上什么都沒有。并且后續除非我們使用 set 方法修改下標為 1 的值,否則這個位置上將一直為 null,因為在末尾添加元素時將會從 size = 2 的位置上開始。

上段代碼驗證下:

結果和我們分析的一樣:

ArrayList 的線程安全版本是 Vector,它的實現很簡單,就是把所有的方法統統加上 synchronized :

既然它需要額外的開銷來維持同步鎖,所以理論上來說它要比 ArrayList 要慢。

七、為什么線程不安全還要用它呢

因為在大多數場景中,查詢的情況居多,不會涉及太頻繁的增刪。那如果真的涉及頻繁的增刪,可以使用LinkedList,底層鏈表實現,為增刪而生。而如果你非得保證線程安全那就使用 Vector。當然實際開發中使用最多的還是 ArrayList,雖然線程不安全、增刪效率低,但是查詢效率高啊。

“ArrayList是什么”的內容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業相關的知識可以關注本站網站,小編將為大家輸出更多高質量的實用文章!