性能：遍历ArrayList数百次，而不是将Arraylist转换为HashMap并返回？

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

(pseudocode)
ArrayList A
ArrayList B

对于A中的每个实体，我都可以遍历B中的每个单个项目，寻找与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 C
for (each object in A){look up the value in C}
convert C back to an ArrayList

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

（背景：数据从服务中以ArrayList的形式从我那里得到-前端需要一个ArrayList用于视图层。我试图使中间层的处理效率更高-但是入口和出口对象必须是ArrayList（或某些对象）其他清单））

是的，对于大量而言，a HashMap是有益的。

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

假设您的对象具有良好的哈希码算法，则从a中查找值HashMap是O（1）访问。您仍然会花费O（n）的时间来构造它，但是与O（n ²）相比，如果您有大量的项目，那没什么。

HashMap只要B的信息未更改，就使用“ B”中的数据构造一次“ C”并多次使用。如果您“需要经常执行此操作”，则性能会更好，因为HashMap已经构建了，只需重用即可。

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

您不需要“将临时哈希图转换回arraylist”，因为创建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 ²）性能时间将足够短，以至于HashMap不值得这样做。这是您需要做出的决定-您需要确定列表何时足够大，以至于建造HashMap和使用它值得HashMap建造成本。