以下環(huán)境是 JDK 1.8

ArrayList 的初始容量

面試官：你看過(guò) ArrayList 的源碼？

Python 小星：看過(guò)

面試官：那你說(shuō)下ArrayList 的初始容量是多少？

Python 小星：10

面試官：你確定!？

......

1、ArrayList源碼 -- 構(gòu)造器

從源碼里我們可以看到，無(wú)參構(gòu)造函數(shù)，容量初始化為 0，有參構(gòu)造函數(shù)的初始容量自定義。

我們也可以做個(gè)測(cè)試驗(yàn)證，我們通過(guò)反射獲取 elementData 的長(zhǎng)度，即是 ArrayList 的容量

輸出結(jié)果：

思考哈：為什么默認(rèn)長(zhǎng)度是 10 ？

hashmap 里默認(rèn) 16，是為了 hash 算法。@Python大星 認(rèn)為固定長(zhǎng)度的數(shù)組初始容量不需要考慮 hashmap 里的hash沖突，取 10 可能是不大不小的值，然后一直引用下來(lái)。就像你說(shuō)為什么數(shù)組的下標(biāo)都是從 0 開(kāi)始，而不是從 1 開(kāi)始，a [0] 就是偏移為 0 的位置。a [k] 就表示偏移 k 個(gè)元素類型大小的位置，少做一步減法，就一直被繼承下來(lái)，無(wú)論是 C語(yǔ)言、Java語(yǔ)言 或者 Python 語(yǔ)言。

知道的小伙伴歡迎在評(píng)論下留言，也許無(wú)形中幫助了很多迷茫的人。

ArrayList 是“動(dòng)態(tài)數(shù)組”-- 擴(kuò)容

1、“動(dòng)態(tài)”體現(xiàn)在 ArrayList的自動(dòng)擴(kuò)容上

ArrayList 如何完成一次擴(kuò)容？

場(chǎng)景：ArrayList 初始容量是 10 ，如果再 add 一個(gè)元素，會(huì)怎樣？

我們可以看到 JDK8 相比之前做了一點(diǎn)優(yōu)化，使用了 >> 位運(yùn)算

數(shù)組會(huì)按照 10 + 10 * 0.5 = 15 擴(kuò)容(把原來(lái)的數(shù)組復(fù)制到另一個(gè)內(nèi)存空間更大的數(shù)組中)，擴(kuò)容后再把指向原數(shù)的地址換到新數(shù)組。

ArrayList、LinkedList、Vector 的區(qū)別？

① Arraylist 和 Vector 是采用數(shù)組方式存儲(chǔ)數(shù)據(jù)，所以插入數(shù)據(jù)慢，查找有下標(biāo)，所以查詢數(shù)據(jù)快

此數(shù)組元素?cái)?shù)大于實(shí)際存儲(chǔ)的數(shù)據(jù)以便增加插入元素，都允許直接序號(hào)索引元素，但是插入數(shù)據(jù)要涉及到數(shù)組元素移動(dòng)等內(nèi)存操作，

② Vector 本身所有方法都是用 synchronized 修飾的，線程安全，所以性能上比 ArrayList 要差

③ LinkedList 使用雙向鏈表實(shí)現(xiàn)存儲(chǔ)

按序號(hào)索引數(shù)據(jù)需要進(jìn)行向前或向后遍歷，查找較慢，但是插入數(shù)據(jù)時(shí)只需要記錄本項(xiàng)前后項(xiàng)即可，插入數(shù)據(jù)較快。

為什么說(shuō) ArrayList 不是線程安全？

1、測(cè)試

輸出結(jié)果：999

可以看出和我們預(yù)期的不一致。

在 add 操作分 2 步 ：

① 判斷 elementData 數(shù)組容量是否滿足需求

② 在 elementData 對(duì)應(yīng)位置上設(shè)置值

在多個(gè)線程進(jìn)行 add 操作時(shí)可能會(huì)導(dǎo)致 elementData 數(shù)組越界。

elementData [size++] = e 設(shè)置值的操作同樣會(huì)導(dǎo)致線程不安全。從這兒可以看出，這步操作也不是一個(gè)原子操作，線程不安全。

LinkedList

LinkedList 內(nèi)部是雙向鏈表結(jié)構(gòu)

面試官：LinkedList 為什么說(shuō)查找慢？它是怎么查找的？

Python 小星：因?yàn)樗擎湵斫Y(jié)構(gòu)，從表頭開(kāi)始遍歷，所以當(dāng)查找元素在鏈表后面，會(huì)比較慢

面試官：好的。回去等通知！

廢話不多說(shuō)，我們看下源碼

從第二張圖中我們可以看出：

鏈表中的 index 只是標(biāo)記元素的相對(duì)于鏈表頭部(first 指向的)node 的個(gè)數(shù) ，這樣在根據(jù) index 查詢時(shí)，可以根據(jù) index 和 size 的關(guān)系，提高查詢性能。當(dāng) index 大致在鏈表的前半部分時(shí)(index > 1))，從鏈表的首部開(kāi)始遍歷顯然更快，而當(dāng) index 大致在鏈表的后半部分時(shí)(index > (size >> 1))，從鏈表的尾部開(kāi)始遍歷顯然更快，這樣就使得查找次數(shù)從 n 次將為了 n/2 次，雖然查找算法的時(shí)間復(fù)雜度還是 O (n)。

我們都知道 LinkedList 是鏈表結(jié)構(gòu)，那到底是單向鏈表還是雙向鏈表？

由上圖可以看出Linkedlist是雙向鏈表

為什么說(shuō) Vector 過(guò)時(shí)了，棄用了？

摘選 stackoverflow 的回答

https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated#comment12234699_1386288

首先需要說(shuō)明，在 Java 8 中 ，官方并沒(méi)有棄用。

① Vector 對(duì)每個(gè)單獨(dú)的方法進(jìn)行同步；

② 通常 我們想要同步整個(gè)操作序列。

參考 https://javaconceptoftheday.com/not-use-vector-class-code/

① 無(wú)需 vector 也能實(shí)現(xiàn)線程安全

可以使用 Collections 類中 synchronizedList 來(lái)實(shí)現(xiàn)線程安全的 ArrayList

② 線程安全的 Vector 非常耗時(shí)

Vector 類的所有方法均已同步。這使 Vector 對(duì)象線程上的每個(gè)操作都安全。但是,這很耗時(shí)。因?yàn)?#xff0c;您需要為Vecto r在對(duì)象上執(zhí)行的每個(gè)操作獲取對(duì)象鎖。通常，我們需要一組操作而不是每個(gè)操作都同步。一次鎖定對(duì)象，為什么每次操作都要一次又一次次地獲得鎖？這是耗時(shí)的，降低性能。

③ Vector 設(shè)計(jì)不好

Vector 結(jié)合 2 個(gè)功能，“可調(diào)整大小的數(shù)組” 和 “同步”。這使設(shè)計(jì)不佳，而應(yīng)始終使用ArrayList類。您將擁有可調(diào)整大小的數(shù)組，每當(dāng)您要使其同步時(shí)，可以使用 Collections 中 synchronizedList 來(lái)實(shí)現(xiàn)線程安全的 ArrayList。

除了 Vector ，還有哪些線程安全的 ArrayList ？

synchronizedList 和 CopyOnWriteArrayList

1、synchronizedList

① synchronizedList 的用法(適合對(duì)數(shù)據(jù)要求較高的情況)

SynchronizedList 的 add 方法

add 方法

我們可以看出，SynchronizedList 用 synchronized 同步的是代碼塊，而 vector 用synchronized 同步的是方法。

【1】SynchronizedList 有很好的擴(kuò)展和兼容功能。他可以將所有的 List 的子類轉(zhuǎn)成線程安全的類；

【2】使用 SynchronizedList 的時(shí)候，進(jìn)行遍歷時(shí)要手動(dòng)進(jìn)行同步處理。

② CopyOnWriteArrayList (適合讀多寫(xiě)少的場(chǎng)景)

1、add方法

CopyOnWriteArrayList 中 add 方法的實(shí)現(xiàn)(向 CopyOnWriteArrayList 里添加元素)，可以發(fā)現(xiàn)在添加的時(shí)候是需要加鎖的，寫(xiě)入時(shí)復(fù)制(CopyOnWrite)，copy 一份新的數(shù)組進(jìn)行相關(guān)的操作，在執(zhí)行完修改操作后將原來(lái)集合指向新的集合來(lái)完成修改操作

add方法

2、get方法

讀的時(shí)候不需要加鎖，如果讀的時(shí)候有多個(gè)線程正在向 CopyOnWriteArrayList 添加數(shù)據(jù)，讀還是會(huì)讀到舊的數(shù)據(jù)，因?yàn)閷?xiě)的時(shí)候不會(huì)鎖住舊的 CopyOnWriteArrayList。

get方法

CopyOnWriteArrayList 缺點(diǎn):

【1】 內(nèi)存占有問(wèn)題：很明顯，兩個(gè)數(shù)組同時(shí)駐扎在內(nèi)存中，如果實(shí)際應(yīng)用中，數(shù)據(jù)比較多，而且比較大的情況下，占用內(nèi)存會(huì)比較大，針對(duì)這個(gè)其實(shí)可以用 ConcurrentHashMap 來(lái)代替。

【2】 數(shù)據(jù)一致性：CopyOnWrite 容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。所以如果你希望寫(xiě)入的的數(shù)據(jù)，馬上能讀到，請(qǐng)不要使用 CopyOnWrite 容器

@Python大星 | 文

總結(jié)

以上是生活随笔為你收集整理的arraylist 后往前遍历_面试官：请说出线程安全的 ArrayList 有哪些，除了Vector的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。