从 Set 中删除列表中存在的项目 - Streams

Question

我正在尝试从集合 (HashSet) 中删除一些对象，但前提是它们也存在于列表 (LinkedList) 中。如何使用 Java 8+ 功能（流）实现此目的。

Set<MyObject> theSet -> want to remove items that are present in the list

List<MyObject> theList

我已经覆盖了 MyObject 的 equals 和 hashcode（仅使用几个字段来比较相等性）。

Answer 1

您可以从Collection界面中查看removeIf()方法。所以你可以这样说：

theSet.removeIf(theList::contains)

它还会 return 一个 boolean 指示是否删除了任何元素。

Answer 2

如果您的集合是可变的，您可以像这样从集合中删除列表中存在的所有条目：

theSet.removeAll(theList);

假设您的集合是不可变的，那么您可以使用流对其进行过滤，从而导致新集合缺少列表中存在的条目，如下所示：

var newSet = theSet.stream()
    .filter(n -> !theList.contains(n))
    .collect(Collectors.toSet());

对于 Java 11+，您可以通过组合使用过滤谓词的方法参考：

var newSet = theSet.stream()
    .filter(Predicate.not(theList::contains))
    .collect(Collectors.toSet());

性能小记

两种方法（removeAll 和通过流）运行 in O(N * M) 其中 N 是大小theSet 和 M 的大小 theList。它归结为两个嵌套的 for-loops.

一个简单的增强是将 theList 变成一个集合，并将线性包含检查的成本降低到 O(1)[的渐近运行时间.

var numsToExclude = new HashSet<>(theList);
var newSet = theSet.stream()
    .filter(Predicate.not(numsToExclude::contains))
    .collect(Collectors.toSet());

Answer 3

考虑到流开销，我怀疑流是否与简单循环一样快。您总是必须遍历整个列表，所以我会这样做。这假定原始集是不可变的。

List<Integer> list = List.of(1,2,5,8,9,10);
Set<Integer> set = Set.of(3,4,8,2,1);
Set<Integer> result = new HashSet<>(set);
        
for(int val : list) {
     result.remove(val);
}
System.out.println("Before: " + set);
System.out.println("After:  " + result);

打印

Before: [1, 8, 4, 3, 2]
After:  [3, 4]

由于 Sets 不能包含重复项，因此在删除列表中遇到重复项不会影响结果。因此，如果您可以将它们收集在 Set 而不是 List 中，它可能会提供一些改进。

最后，要删除的 Object 必须覆盖 equals 和 hashCode 才能使上述工作正常。

从 Set 中删除列表中存在的项目 - Streams

Remove items from a Set that are present in a List - Streams

java

algorithm

java-stream

性能小记