java - ArrayList 还是不同键的映射，更快？

Question

示例:-

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

列表 A 中的一个对象将仅与列表 B 中的一个对象匹配。匹配标准是我定义的，假设是项目编号、起始日期和区号。如果这些值匹配，那么我会将所有其他值从列表 B 的对象复制到列表 A 的对象。

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

Sol 1:- 只需执行一个 for 循环即可匹配列表 A 中列表 B 的对象。

Sol 2:-
第 1 步:- 从列表 B 创建 HashMap < String, Object >。
第 2 步:- 使用该映射获取列表 A 中的匹配记录并设置值。如果我创建一个 map ，那么每个对象的键都是不同的。假设如果列表 B 有 1000 个对象，那么如果我想创建 HashMap，就会有 1000 个不同的键。

Answer 1

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

解决方案 1 需要对 n 个对象(列表 A)进行循环，并在 m 对象(列表 B)上进行内部循环。因此，这是 O(n*m) 或更准确地说是 O(n^2)。

解决方案 2 需要设置时间(构建 Map)，即 O(m)，然后扫描一次列表 A(并且在列表 B 中查找成本为零，因为HashMap 查找的时间为 O(1)。因此，这是 O(m)+O(n)，相当于 O (n)。这是一个更好的解决方案。

存在一种边缘情况，其中m远大于n - 在这种情况下，设置时间和内存成本可能会很大。