时间戳

首页 > 解决方案 > 性能：循环 ArrayList 数百次与将 Arraylist 转换为 HashMap 并返回？

java - 性能：循环 ArrayList 数百次与将 Arraylist 转换为 HashMap 并返回？

问题描述

我有两个需要比较和操作的大型（1000 多个对象）ArrayList。我基本上需要从 ArrayList A 中获取一个值，在 ArrayList B 中查找匹配的对象，然后从 B 中操作该对象。我需要在 A 的所有对象中执行此操作。我需要在应用程序中经常执行此操作。订单未知，尺寸会有所不同。

(pseudocode)
ArrayList<myObject> A
ArrayList<myObject> B

我可以遍历 B 中的每个项目，为 A 中的每个实体寻找与 A 中的实体匹配的项目。这似乎效率很低。

(pseudocode)
for (each object in A){loop through all of B and find it}

将 B 转换为 HashMap 是否值得（使用我要比较的特定值作为键，对象作为值），然后以这种方式搜索 B，然后在我完成处理后将该临时 HashMap 转换回 ArrayList ?

(pseudocode)
convert B to HashMap<myObject.myValue,myObject> C
for (each object in A){look up the value in C}
convert C back to an ArrayList

这是一个好主意吗？或者这是过早/不必要的优化？谢谢你。

（背景：数据作为 ArrayList 来自服务 - 前端需要一个 ArrayList 用于视图层。我试图让这个中间层处理更高效 - 但入口和出口对象必须是 ArrayList （或一些其他列表））

标签： javaperformancearraylisthashmap

解决方案

是的，对于大量数字，aHashMap是有益的。

您的初始算法将花费很长时间，在嵌套的 for 循环中遍历两个列表。这是一个 O(n 2 ) 算法。即使假设 和 中各有 1000 个项目A，B并假设比较两个单独项目的成本为 1，一个来自A和一个来自B，您正在查看 500k 比较（避免将每个项目比较两次）。经常这样做会导致性能下降。

假设您有一个很好的对象哈希码算法，从 a 中查找一个值HashMap是 O(1) 访问。你仍然会花费 O(n) 时间来构建它，但如果你有大量项目，这与 O(n 2 ) 相比没什么。

使用“B”中的数据构建HashMap一次“C”并多次使用它，只要B' 的信息没有改变。如果您“需要经常这样做”，那么性能会更好，因为HashMap它已经构建了——只需重用它。

如果需要维护顺序，请将B列表索引作为值存储在哈希图中。

您不需要“将该临时哈希映射转换回数组列表”，因为创建HashMap“C”不会破坏原始列表“B”。需要注意的一件事是，如果列表中的对象B发生更改，则会强制更新以HashMap保持一致。要注意的另一件事是您对非常大的列表的内存使用情况——您可以将对象、列表和哈希图保留在内存中吗？

你的伪代码：

for each index in B:
    get object b
    put in hash map C values (b, index)

for each a in A:
    if found in hash map C: do something with found object

对于较小的数字，O(n 2 ) 性能时间将足够小，以至于构建它是HashMap不值得的。这是您需要做出的决定——您需要确定列表何时足够大，以至于构建HashMap和使用它是值得的HashMap建设成本。

推荐阅读