比双重嵌套的ArrayList更高效？

Question

我正在构建一个Java后端组件，每天处理适量的数据。我们有一个POJO，叫做Widget，它有大约10个属性。我的软件必须处理Widget列表的组：实际上有其他进程（完全不同的系统）组合他们自己的List<Widget>，然后将它们发送到我的软件。我的软件实际上接收到一个外壳POJO，看起来像这样：

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，因此总共有约2.5百万个Widget在内部ArrayList中。

在最近的代码审查中，一些技术领导告诉我，我选择了错误的数据结构来处理这个批量小部件。他们告诉我，我应该使用HashMap<String,List<Widget>>，因为它更有效率和易于使用。哈希映射键是包含在我的软件中的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>添加到一个大的“批处理”数据结构中，然后在稍后检查所有这些数据并对每个Widget执行操作。 这个软件在一些性能强劲的服务器上运行，具有大量的内存和处理能力。

因此，我想问： ArrayList<ArrayList<Widget>>、HashMap<String,List<Widget>>还是其他什么东西是正确的选择，为什么？

- IAmYourFaja

---

我感觉你说了很多不必要的东西来回答核心问题。试着把它看作是列举事实而不是讲故事。 - Bernhard Barker

如果您要将所有内容一起处理，那么可以使用ArrayList<Widget>并随着widget的到来将它们添加到主列表中。此外，您是否需要在开始处理之前先获取全部的50万组数据，或者每次只处理一个小列表并存储结果即可。针对每个小列表生成一个线程以进行处理，并在完成后丢弃该列表，这种做法可能更节省内存。 - Windle

顺便说一句，你的用户名让我笑了 =) - Windle

处理顺序很重要吗？例如，您是否想先处理旧批次？如果是这样，使用GUID作为键的Map将破坏此顺序（除非您使用TreeMap并且可以保证GUID按顺序排列）。 - David Lavender

@Dukeling 我在某种程度上同意你的观点，然而，如果你直接跳到最后，问题的表述是相当清楚的。也许可以加个“简短概述”标题，但我个人发现额外的背景信息很有帮助。 - totallyNotLizards

我认为LinkedList比ArrayList更好，但除此之外，我认为基于List的实现是正确的。更准确地说，假设您在初始化时知道ArrayList内容的确切大小，则应使用LinkedList<ArrayList<Widget>>。 - Justin

Answer 1

我想问一下：是选择 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，请不要引入这个新类（保持简单）。

这让我想到了：谁是对的？！？

在你的解决方案和同事的代码审查中，我个人强烈推荐你的方案。

但是，你可以自己保留意见并遵循“技术领袖”的决定。如果这是他们的职责，那么提供这些选择就是他们的决定和责任。 （支付你工资的人永远是对的）

- Luigi R. Viggiano

Answer 2

你一直在使用的一个名词，在你的数据模型中丢失了：批次。 如果你真的关心将它们保留在它们的批次中，并保持你的代码易读性，那么请将它们封装在一个批次类中：

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

如果你不关心批次，那么你可以将它们全部压缩为单个List<Widget>吗？

- David Lavender

Answer 3

相比于数组列表，哈希映射并不更高效或更易于使用。如果您需要通过其GUID键查找批次，则可以进行更改。

哈希映射不如数组列表高效，因为调整大小意味着必须重新评估哈希码并将数据重新分配到相当随机的内存位置。另一方面，调整数组的大小会将内容线性地从旧数组复制到新数组中，这对于CPU缓存更加友好。

哈希映射也不更易于使用。要访问条目，您必须通过map的entry set，这违反了Demeter定律。

- Joni

Answer 4

也许一个嵌入式（in-core）数据库是你最终想要的。另一个可能性是像JavaSpaces/NoSQL这样的东西，将交付和处理解耦。这取决于具体情况。

- Joop Eggen

Answer 5

从你的问题中可以清楚地看出你正在做这些事情。

1. 从你的数据中读取。
2. 添加更多的小部件。

问题是，将数据结构从 ArrayList<ArrayList<Widget>> 更改为 HashMap<String,List<Widget>> 将如何影响上述两个活动。

1) 读取：你已经将它们分成了4组，因此使用 hashmap 存储你的组，使用哈希处理存储不适用于小数据集（在你的情况下是组），因此在这里不需要使用 hashmap。

2) 添加更多的小部件：你将访问要添加的 List，所以同样是读取。使用 ArrayListObj.get(index) 不会有任何问题。

现在使用 ArrayList 将始终按顺序读取 widgets。这将不会使用 Hashmap 完成，但无论如何，我认为这不是你关心的问题，对吧？:-)

- Amandeep Jiddewar

Answer 6

如果您需要随机访问内部列表并且使用哈希映射的代码看起来更加优雅，这时候哈希映射会更加有效。但是，如果您必须遍历和访问每个节点，那么您不会比On^2更好。您可以将它们塞入数据库中，但这只会增加复杂性而没有其他好处，就像哈希映射一样优雅。当然，所有这些都假定您有足够的内存来同时保存所有250万个小部件。如果您必须对其进行分页，则某种类型的DB SQL或NoSQL可能会更好。

- WPrecht