比较两个列表并获取差异

Question

我有两个列表。它们包含不同类型的对象，但是两种类型都包含id和name，而id是我要比较的内容。 列表一是从数据库中获取的，而列表二是从前端发送的。

我需要做的是循环遍历它们，并找出哪个列表项是新添加的，哪个是被删除的。

我已经能够做到了，但问题在于它看起来很丑陋。

假设我有一个名为NameDTO的对象，它可以具有id和name。列表二填充了这种类型的对象。

这就是我所做的：

final ArrayList<NamedDTO> added = new ArrayList<>();
final ArrayList<NamedDTO> removed = new ArrayList<>();

for(NamedDTO listTwoObject : listTwo) {
   boolean contained = false;
   for(SomeObject listOneObject : listOne) {
       if(listTwoObject.getId().equals(listOneObject.getId()) {
           contained = true;
       }
   }
   if(!contained) {
      added.add(listTwoObject);
   }
}

for(SomeObject listOneObject : listOne) {
   boolean contained = false;
   for(NamedDTO listTwoObject : listTwo) {
       if(listTwoObject.getId().equals(listOneObject.getId()) {
           contained = true;
       }
   }
   if(!contained) {
      removed.add(new NamedDTO(listOneObject.getId(), listOneObject.getName()));
  }
}

这个方法可行，我已经测试过了。 有更好的解决方案吗？ 我在考虑使用Set以便进行比较，这样做有什么缺点吗？

- mirzak

---

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem - Nándor Előd Fekete

但问题是它看起来很丑。你的意思是太多代码了还是你在谈论性能？你的主要目标是什么？ - Chetan Kinger

为什么不创建另一个仅包含第二个列表ID的列表，并检查它是否包含该ID？ - Darshit

代码太多了。我正在尝试一些不同的东西，稍后会发布它。我也需要名字。 - mirzak

你一直在将对象与其自身进行比较。在考虑丑陋之前，您应该先考虑正确性。 - Holger

使用基于哈希的连接，例如Set或Map，以避免O(N^2)。 - Steve Kuo

Answer 1

如果我理解正确，这是示例场景：

• listOne [datab] 项目：[A, B, C, D]
• listTwo [front] 项目：[B, C, D, E, F]

你需要的效果是：

• 添加：[E, F]
• 删除：[A]

---

首先，我会使用某种类型的适配器或从一个公共类扩展不同类型，并overrideequals方法，这样你可以通过id和name匹配它们。

其次，在集合上进行此操作非常容易（你可以使用集合，但列表也可以）。我建议使用一个库：https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

现在基本上是：

• 添加的是listTwo - listOne
• 删除的是listOne - listTwo

并使用Java代码：

• 添加： CollectionUtils.removeAll(listTwo, listOne)
• 删除： CollectionUtils.removeAll(listOne, listTwo)

---

否则，所有实现Collection（Java Docs）的集合也具有removeAll方法，您可以使用它。

- Atais

---

如果提问者可以接受使用第三方库，那么这个答案就有意义。除非我们询问，否则我们无法确定。 - Chetan Kinger

@CKing 好的，我们也可以不用它。 - Atais

我已经研究了这个，发现它非常简单易读，在我的情况下很重要，因为我不是唯一在这个项目中工作的开发者。我会使用它。 - mirzak

Answer 2

我提出使用Java 8流的解决方案:

    ArrayList<ObjOne> list = new ArrayList<>(Arrays.asList(new ObjOne("1","1"),new ObjOne("3","3"),new ObjOne("2","2")));
    ArrayList<ObjTwo> list2 = new ArrayList<>(Arrays.asList(new ObjTwo("1","1"),new ObjTwo("3","3"),new ObjTwo("4","4")));

    List<ObjOne> removed = list.stream().filter(o1 -> list2.stream().noneMatch(o2 -> o2.getId().equals(o1.getId())))
            .collect(Collectors.toList());
    System.out.print("added ");
    removed.forEach(System.out::println);

    List<ObjTwo> added = list2.stream().filter(o1 -> list.stream().noneMatch(o2 -> o2.getId().equals(o1.getId())))
             .collect(Collectors.toList());

    System.out.print("removed ");
    added.forEach(System.out::println);

这基本上就是您的解决方案，但使用流实现，这将使您的代码更短更易于阅读。

- Kamil Banaszczyk

---

这基本上只是以不同的方式编写OP的方法 - 它具有相同的复杂度（list.size() * list2.size()）。尽管如此，因为它更紧凑一些，所以+1。 - Hulk

谢谢，正如您所看到的，我在下面的代码中进行了注释，这是他的解决方案，但它更短，更易于阅读 :) - Kamil Banaszczyk

重要的是要知道，使用Stream需要API级别24或更高版本。因此，并非所有人都可以使用它。 - Izoman

Answer 3

这种嵌套列表处理方法不仅难看，而且效率低下。你最好将一个列表的 ID 存储在 Set 中以实现高效查找，然后使用 Set 处理另一个列表。这样，你不需要执行 list1.size() * list2.size() 次操作，而只需执行 list1.size() + list2.size() 次操作，对于较大的列表来说这是一个显著的差异。由于两个操作基本相同，因此将它们抽象成一个方法是值得的：

public static <A,B,R,ID> List<R> extract(
    List<A> l1, List<B> l2, Function<A,ID> aID, Function<B,ID> bID, Function<A,R> r) {

    Set<ID> b=l2.stream().map(bID).collect(Collectors.toSet());
    return l1.stream().filter(a -> !b.contains(aID.apply(a)))
             .map(r).collect(Collectors.toList());
}

这种方法可以被用作

List<NamedDTO> added   = extract(listTwo, listOne, NamedDTO::getId, SomeObject::getId,
                                 Function.identity());
List<NamedDTO> removed = extract(listOne, listTwo, SomeObject::getId, NamedDTO::getId,
                                 so -> new NamedDTO(so.getId(), so.getName()));

由于交换两个列表需要帮助方法独立于元素类型，因此它期望用于访问id属性的函数，可以通过方法引用指定。然后，需要一个描述结果元素的函数，在一种情况下是恒等函数（仅获取NamedDTO），在另一种情况下是使用lambda表达式从SomeObject构造NamedDTO。

操作本身与上述描述一样简单，遍历一个列表，映射到id并收集到一个Set中，然后遍历另一个列表，仅保留其id不在集合中的元素，映射到结果类型并收集到一个List中。

- Holger

Answer 4

如果这些id是唯一的，你可以把它们放入一个HashSet中，从而找到你感兴趣的id：

    Set<Integer> uiList = Stream.of(new FromUI(1, "db-one"), new FromUI(2, "db-two"), new FromUI(3, "db-three"))
            .map(FromUI::getId)
            .collect(Collectors.toCollection(HashSet::new));
    Set<Integer> dbList = Stream.of(new FromDB(3, "ui-one"), new FromDB(5, "ui-five"))
            .map(FromDB::getId)
            .collect(Collectors.toCollection(HashSet::new));

    uiList.removeIf(dbList::remove);

added/uiSet :   [1,2]
removed/dbSet : [5]

我创建了FromUI和FromDB类，并使用构造函数将id和名称作为输入参数。

我假设，如果一个元素包含在uiSet中但不包含在dbSet中，则表示该元素已添加，反之亦然。

- Eugene

---

现在，您已经简化了太多。虽然 Collectors.toSet() 目前返回一个 HashSet，但不能保证返回一个可变的 Set，因此，您必须使用 toCollection(HashSet::new)。顺便说一句，oneSet.removeIf(otherSet::remove) 的技巧很聪明，我肯定有时会用到它。这将即使在 map1.keySet().removeIf(map2.keySet()::remove) 的情况下也能工作，这允许将所有者放入 values() 中... - Holger

@Holger 哦，该死，这太可怕了！我已经阅读了文档（我应该早点阅读），但我不知道可变性。非常感谢您提供的信息。 - Eugene