年少往事
記得剛學資料連結清單的時候,老師是不是說,讀多寫少用數組,寫多讀少用連結清單,但你有沒有想過多少才算多?我也有這個疑問,剛好今天有時間,借這個話題一起探讨,ArrayList和LinkedList選擇之寫操作。
磁盤IO
我們都知道,磁盤IO以塊為機關讀取資料,如果你所需要的資料都存儲在一個塊呢,一次IO即可傳回。如果跨越多個塊,隻要你的塊是連續的,類似MYSQl,基于預讀機制,一次讀取多個塊的資料。這明顯利好數組,因為數組申請記憶體的時候,大小是固定且連續的。如果是連結清單,它的資料随機散落在不同的塊,意味着磁盤IO很快。
小結
- 數組讀性能好是因為資料順序存儲,一次IO即可傳回
- 連結清單讀性能差是因為資料随機存儲,多次IO才能傳回
擴容
我們都知道,ArrayList存在擴容問題,在頻繁寫入的時候,會因為容量不足需要重寫開辟新的數組空間,然後複制原數組資料到新的數組,這個過程消耗大量記憶體,這也是提出寫多用連結清單的原因。
那麼,是不是隻要寫多就用連結清單?這個回答顯然是否定的,不然沒有探讨的意義。下面我們看看大資料量下兩者寫入差異。
小試牛刀,500萬資料看看
ArrayList初始容量1萬,循環插入500萬資料,擴容9次,用時138ms,LinkedList隻需要不停建立節點,将節點next綁定即可,但用時724ms,差距5倍多。
小結
500萬資料寫入,用ArrayList是上策。不過能接觸到這麼多資料量的情況并不多,實際使用以實際情況為準,多測測你的業務和機器選擇比較好,不過對于我來說,優先考慮ArrayList,因為從GC的角度來說,順序存儲利于GC,不管是CMS還是G1。
加量-1千萬
可以看到,一千萬資料量依然有接近3倍的差異,看到這你還猶豫什麼,無腦ArrayList
2千萬
沒想到2千萬就被反超了,但是你以為這樣會說服我使用LinkedList嗎,我隻能說Naive
3千萬
已持平!
4千萬
重新反超,這麼大的資料量下,linkedList建立大量node,比需要開辟新數組記憶體的arrayList消耗的時間更多,記憶體也更多,不信Jmap看看?而arrayList可是擴容了12次
結論
沒得出什麼牛逼結論,反而看出兩個list在大資料量情況下,性能不是一定誰更好,可能是兩條有多個交點的曲線。在選擇上,無腦arrayList,如果是重要場景,最好根據業務和機器配置選擇合适的。但業務會增長,摸着良心問自己,業務增長到另一個交點的時候,你會改過來嗎!