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

Question

我有两个大型（1000 多个对象）ArrayList，我需要比较和操作它们。我基本上需要从 ArrayList A 中获取一个值，在 ArrayList B 中寻找一个匹配的对象，然后操作 B 中的对象。我需要在 A 的所有对象中执行此操作。我需要在应用程序中经常执行此操作。订单未知，尺寸会有所不同。(pseudocode)ArrayList<myObject> AArrayList<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> Cfor (each object in A){look up the value in C}convert C back to an ArrayList这是一个好主意吗？或者这是过早/不必要的优化？谢谢你。（背景：数据作为 ArrayList 从服务传给我——前端需要一个 ArrayList 用于视图层。我试图使这个中间层处理更有效率——但入口和出口对象必须是 ArrayList（或一些其他列表））

Answer 1

是的，对于大量的人来说，aHashMap是有益的。

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

假设你有一个很好的对象哈希码算法，从 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构建成本。