Java List家族大解惑

-

前言

在學時還有工作初期，看了市面上的Java教科書發現都沒有深入探討這些List底層與關鍵要素，都只教如何使用。但這個坑常常會在面試或是追蹤效能上體現出自己的不足，所以寫一篇文章鞏固自己的觀念

目標

搞清楚List中ArrayList & LinkedList & Vector

List

我目前開發最常使用的資料結構，因為ArrayList的方便性可以儲存各種物件。而真的只能用ArrayList去做這些處理嗎?如果遇到瓶頸還有甚麼解決方法呢?
接下來會以下方兩個討論去做比較

  1. ArrayList & LinkedList
  2. ArrayList & Vector

List & LinkedList

差別

  1. 實作
    • List的底層結構是Object陣列
    • LinkedList是LinkedList資料結構，
      • 也就是在搜尋時是透過Node的連結做移動
  2. 快速隨機存取
    • ArrayList實作RandomAccess而LinkedList沒有
      • 透過物件導向的概念這代表的ArrayList支持隨機存取但LinkedList沒有
    • LinkedList的資料結構本身是不支援隨機存取的，需要遍歷的方式才能找到元素
      • 可以看到LinkedList原始碼繼承AbstractSequentialList就可知道它需要遍歷抓取元素
    • ，而ArrayList只需要給index並且直接去找出陣列中的記憶體位置就可以取得元素，可以透過下方的程式碼觀察出差別。
    • 所以在get(index)方法中 ArrayList在正常條件下會優於LinkedList

ArratList

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

LinkedList

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
        Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

  1. Add & Delete

    • ArrayList在一般add()的情況下複雜度是O(1)因為直接於陣列後方新增，但如果是要在第i個位置新增或刪除add(i, element)或是delete(i)那複雜度就會是O(n-i)，因為必須將新增或刪除後方的元素做位置上的調整。
    • LinkedList因為是Linked List資料結構，因此在位置上都不需做到位置的調整所以複雜度為O(1)

  2. 記憶體空間

    • ArrayList需要彈性的新增，所以都會在固有長度上預留一定的空間
    • LinkedList儲存元素為node需要額外儲存上下節點的資訊所以每個元素都會花費較多的記憶體

段落Memo

  1. 實作RandomAccess的資料結構，那可以優先考慮for迴圈的方式去搜尋資料，因為他是支援快速隨機存取的。
  2. 未實作RandomAccess介面的資料結構，則優先選擇iterator遍歷的方式也就是現在常用的foreach方法（foreach底層也是透過iterator去對資料做處理）

ArrayList & Vector

  1. Vector與ArrayList的操作大致上大同小異，不過最大的差別在於，Vector支持同步化操作(也就是若在多執行序處理資料時確保資料的一致性)，而ArrayList沒有支持同步化操作，
  2. 同步化操作雖然可以確保一致性，但若是在沒有必要的時候使用(單執行序時)則會降低資料處理速度
  3. 有興趣觀察Vector的朋友們可以到原始碼觀看Vector.class中的ListItr這個final class。

結論

其實還有許多的差異與使用場景可以去探討，但就等之後如果有遇到或使用到在來補充此文章搂!

參考

https://dotblogs.com.tw/jerryhuang0306/2016/01/30/020303
https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md

留言

張貼留言

這個網誌中的熱門文章

Java Lambda Map篇

-
目的 主要介紹Map中的新方法，包含如下 forEach() getOrDefault() putIfAbsent() remove() replace() replaceAll() merge() 有些是Lambda有些則是我覺得比以前使用Map更方便而介紹 forEach Map的forEach方法與List不大依樣，因為Map主要的迭代方法是以Entry為主，所以需要Key-Value Pair去迭代 原始碼解說 可以看到forEach的傳入參數BiConsumer介面，必須傳入Key與Val，裡面的實作就如同我們使用Java8版本以前的寫法，需要使用for迴圈去迭代抓出每個Value 原始碼 default void forEach(BiConsumer<? super K, ? super V> action) { Objects.requireNonNull(action); for (Map.Entry<K, V> entry : entrySet()) { K k; V v; try { k = entry.getKey(); v = entry.getValue(); } catch(IllegalStateException ise) { // this usually means the entry is no longer in the map. throw new ConcurrentModificationException(ise); } action.accept(k, v); } } 範例 private void forEachExample() { Map<Integer, String> map = new HashMap<>(); map.put(1, "test1"); map.put(2, "test2"); m...
閱讀完整內容

設計模式 - 工廠模式 (Creational Patterns - Factory Pattern)

-
圖片
前言 這篇文章會介紹三個最常使用的工廠模式方法，分別是 Simple Factory (簡單工廠) Abstract Factory (抽象工廠) Factory Method (工廠方法) 其中最容易讓人搞混的是，Abstract Factory和Factory Method，不過對我來說何必太過糾結於這兩個的概念，工廠模式最主要的核心原理就是將你創造物件的邏輯隱藏起來，不向客戶端顯示，我覺得只要知道這個概念就夠了，接下來會介紹這三個種類的工廠模式。 Factory Pattern 工廠模式 Simple Factory 簡單工廠 簡單工廠是工廠模式的第一步，也是工廠模式最基本的核心概念實踐，主要解決的問題是 將創建物件邏輯抽離 解偶Class的複雜度 Class Diagram 將封裝物件邏輯抽出寫成Simple Factory 產出父類別物件的物件 範例 在這個範例我們希望將戰士與魔法師遊戲創造英雄的邏輯抽出並且寫成靜態工廠，戰士與魔法師都是英雄並且’目前’只能進行攻擊，程式碼如下 Interface Hero public interface Hero { void attack(); } Magician.class public class Magician implements Hero { @Override public void attack() { System.out.println("Use magic to attack"); } } Warrior.class public class Warrior implements Hero { @Override public void attack() { System.out.println("Use sword to attack"); } } HeroFactory.class public class HeroFactory { public Hero makeHero(HeroType heroType) { if (heroType.equals(HeroType.MA...
閱讀完整內容

(InterviewBit) System Design - Design Cache System

-
圖片
前言 這是InterviewBit中Storage Scalabiliy第一題，設計一個快取系統。 我希望可以透過InterviewBit中的文章與題目，打開自己系統設計的視野，並且重裡面中得到關鍵詞彙，透過這些關鍵詞彙補足自己知識的不足。 其中會參考許多 jyt0532神 的許多文章 題目 替Twitter或是google設計快取系統，概念圖如下: 分析步驟 列出需求情境 估算 立定設計目標 深入探討設計方法 需求情境 需要多大的快取 我們的快取清除策略要如何 因為快取大小所以必須將舊資料刪掉 快取的寫入策略 Write through cache 當資料寫入時，同時寫入DB和Cache中 寫入因為需要寫入兩個系統(DB/Cache)所以有較高的延遲 Write around cache 當資料寫入時先寫入DB，當快取被讀取發現遺失資料時，再將資料從DB同步到快取中 因為讀取是從快取中讀取，但是在讀取時判斷到有新增資料沒進入快取，會有較高的讀延遲。 但寫和重複讀不會有特別的延遲 Write back cache 直接將資料寫入到快取中，在同步到資料庫裡 風險 - 畢竟快取是in-memory會有遺失風險 優點 - 高寫入效率(寫得快可附合的流量大) 可以透過replica快取降低memory消失的風險 評估 預先知識 QPS - Queries Per Second TPS - Transactions Per Second UV - Unique Visitor RPS - Requests Per Secornd 獲取設計前條件 目前得知的條件 快取大小會是30TB QPS會是10M(每秒一千萬) 估算機器數量 假設我們每台機器都有72G的記憶體，則要存入30TB的資料則需要 30TB / 72G = 420(大約)，而這是剛剛好的數目，有可能需要增加，因為我們每秒要附和10M的搜尋流量。 設計目標 設計目標三巨頭 Latency(延遲) Consistency(一致性) Availability(可使用性) 快取系統的設計目標 快取的用意就在於降低延遲，DB的寫入是依靠硬碟的而快取是依靠記憶體，有基本計算機常識的話就可以知道...
閱讀完整內容