比雙重嵌套的ArrayList更高效嗎？

我正在構建一個每天處理中等數據量的Java後端組件。我們有一個POJO，我們稱之爲Widget，它有大約10個屬性。我的軟件必須處理Widget列表組：本質上還有其他進程（完全不同的系統）將它們自己的List<Widget>放在一起，然後將它們發送到我的軟件。我的軟件實際收到的包裝POJO，看起來像這樣：比雙重嵌套的ArrayList更高效嗎？

public class Payload { 
    private List<Widget> widgets; // <-- what I want 
    private String guid; // GUID; my software doesn't need this 
    private boolean fizz; // again, my software doesn't need this 
    ... many other properties that I don't care about 
}

我的軟件彙集了所有這些List<Widget>，各由不同的系統上創建的，然後在一個大批量一起對其進行處理。

我暫時選擇了ArrayList<ArrayList<Widget>>作爲保存這批Widget列表的數據結構。將會有大約500,000個組List<Widget>（外部ArrayList），並且每個List<Widget>將各自具有大約5個Widget;在內部ArrayList的總共約250萬Widget s。

在最近的代碼審查中，一些技術負責人告訴我，我爲這個批處理小部件選擇了錯誤的數據結構。他們告訴我，我應該使用HashMap<String,List<Widget>>，因爲它更高效，更容易使用。 hashmap密鑰是我的軟件給出的Payload中包含的GUID。不是因爲任何原因我需要GUID，它只是保持〜500,000 List<Widget>獨立的關鍵 - 我確實需要這樣做。

這讓我想到：誰是對的？！？我們在這個數據結構上做的唯一操作是「增加」（在ArrayList的情況下，只需通過add(...)添加Widget或List<Widget>）然後「讀取」（在我的軟件中，我必須遍歷每個Widget並檢查。它的東西與我的嵌套ArrayList它的要點是：

for(List<Widget> widgetList : myDoublyNestedArrayOfWidgets) { 
    for(Widget widget : widgetList) { 
     ... 
    } 
}

這些都是我們所需要的只是操作：添加不同List<Widget> s到一些大「批量」數據結構，然後在以後的時間，檢查所有這些軟件，並與每個Widget一起做這個軟件。這個軟件運行在一些內存和處理能力都很強大的服務器上。

所以我問：**是ArrayList<ArrayList<Widget>>正確的選擇，HashMap<String,List<Widget>>，還是別的......爲什麼？

來源

2013-02-14 IAmYourFaja

我覺得你說的很多東西不是回答核心問題所必需的。試着把它看作是列舉事實而不是講故事。 – Dukeling 2013-02-14 13:10:15

如果你一起處理所有東西，你可以使用'ArrayList '，並在進入主列表時添加Widget？另外，在開始處理之前是否需要全部500k套，或者是否可以處理每個小列表，並將結果存儲起來。產生一個處理每個小列表的線程，然後在完成後拋出列表可能會提高內存效率 – Windle 2013-02-14 13:12:10

在附註中，您的用戶名讓我大笑=） – Windle 2013-02-14 13:14:18

所以我問：是ArrayList<ArrayList<Widget>>正確的選擇，HashMap<String,List<Widget>>，或其他什麼......爲什麼？

最後，重要的是你的軟件解決了它應該解決的問題。

HashMap比ArrayList更昂貴，如果您不需要通過鍵訪問數據，ArrayList更可能是最佳選擇。此外，使用ArrayList時，需要編寫的代碼執行處理似乎更簡單高效。

順便說一句，有ArrayList<ArrayList<Widget>>或HashMap<String,List<Widget>>聞起來有點。也許你正在建模的是ArrayList<WidgetGroup>和WidgetGroup包含一個List<Widget>（與所有其他屬性，目前，你可能不需要）。但是，如果你的WidgetGroup只包含一個ArrayList，那麼不要引入這個新類（保持簡單）。

這讓我想到：誰是對的？！？

在您的解決方案和您的同行評審者之間，我個人非常喜歡你的解決方案。

但是，您可以保留這一點，並遵循「技術線索」。如果這是他們的角色，那麼他們的決定是重要的，他們有責任提供這些選擇。（支付支票的人永遠是對的）

來源

2013-02-14 13:12:04

哈希映射不比數組列表更有效或更容易使用。如果某些時候您需要通過GUID鍵查找批處理，則更改可能是合理的。

哈希映射不如數組列表有效，因爲調整它的大小意味着必須重新評估哈希代碼並將數據重新分配到相當隨機的內存位置。另一方面調整數組的大小會將舊數組中的內容線性複製到新的數組中，這對CPU高速緩存非常友好。

哈希映射也不容易處理。要訪問條目，您必須通過地圖的條目集，這會打破law of Demeter。

來源

2013-02-14 13:09:30 Joni

也許你最終想要的是一個嵌入式（核心）數據庫。另一種可能性是JavaSpaces/NoSQL，解耦交付和處理。依靠。

來源

2013-02-14 13:13:09

有一個名詞，您繼續使用，但從您的數據模型中缺失：批次。如果你真的關心他們留在他們的批次，並保持你的代碼的可讀性，然後封裝進行批量類：

 
class Batch { 
    String guid; 
    List&ltWidget> widgets; 
}

而且，如果你不關心批次，則可能你只是它們壓平全部變成單個List<Widget>？

來源

2013-02-14 13:14:35

從你的問題很明顯，你正在做這些事情。

從您的數據中讀取數據。
添加更多小部件。

問題是如何改變您的數據結構ArrayList<ArrayList<Widget>> to HashMap<String,List<Widget>>如何影響以上兩項活動。

1）閱讀：你將這些措施分成4組，所以使用hashmap你將存儲使用散列您的組這確實是沒有意義的小數據集（在你的情況下，組），所以沒有必要在這裏使用hashmap。

2）添加更多小部件：您將訪問您要添加到的列表，所以再次同樣你的閱讀。它不會傷害使用ArrayListObj.get(index)。

現在使用ArrayList將始終按順序讀取widgets。這不會使用Hashmap完成，但無論如何，我不認爲這是你的關注還是它？如果你有隨機訪問內部列表，並使用一個HashMap 代碼看起來更優雅到誰蕁麻疹爆發時，他們看到的嵌套循環評審:-)

來源

2013-02-14 13:14:44

的Hashmap會更有效。但是，如果您必須迭代並訪問每個節點，則不會比On^2做得更好。你可以將它們填入數據庫中，但除了複雜性之外，這不會帶來任何好處。它更加優雅，就像hashmap。當然，所有這一切都假定你有記憶一次容納250萬個Widget。如果您必須對其進行分頁，那麼某種類型的DB SQL或NoSQL可能會更好。

來源

2013-02-14 13:18:26 WPrecht

比雙重嵌套的ArrayList更高效嗎？

回答

相關問題