ArrayList或独特密钥的Map，更快？

Question

示例： -

列表A包含N个对象。
列表B包含M个对象。

列表A中的一个对象将仅匹配列表B中的一个对象。 匹配条件由我定义，假设它是项目编号，从日期和区域代码。如果这些值匹配，那么我会将列表B的对象中的所有其他值复制到列表A的对象中。

解决方案： -有两种解决方案，哪一种更好或更快？

溶胶1： -只需执行一个循环，以匹配列表B的名单A.对象

溶胶2： -
步骤1： -要创建一个HashMap <字符串，对象>从列表B中删除。
第2步： -使用该映射来获取匹配记录并设置列表A中的值。 如果我创建映射，那么每个对象的键将不同。 假设列表B有1000个对象，那么如果我想创建HashMap，将会有1000个不同的键。

Answer 1

您的第二个解决方案更高效。

解决方案1需要通过n对象（列表B）带有内部循环的对象（列表B）的循环。因此这是O(n*m)或更准确地说是O(n^2)。

溶液2需要建立时间（构建Map），其是O(m)接着列表A的一次扫描（和名单B查找的成本为零，因为HashMap查找是O(1)。因此，这是O(m)+O(n)这相当于O(n)。这是一个更好解决

有一种情况m比n大多的边缘情况。 - 设置时间和存储成本可能显著在这种情况下

Answer 2

第一个解决方案的复杂度为O（N * M）。

第二个O（N）+ O（M），但消耗更多的内存。

第二种算法速度更快。

Answer 3

让我回顾一下：（？短）

• 列表的
• 长名单B
• 列表A有一个项目可能符合某些条件的条目B中
• 当该找到B条目，将B中的所有其他条目复制到A中。
• 问题：B上的Map（索引的标准键）可以帮助吗？

您可以从A制作标准的HashSet，然后通过B直到第一个匹配。

也应该好，也快。

但是，一定要使用Map/Set。也许取决于N < < M.