两个 List的高效交集在Java中？

Question

问题很简单：

我有两个列表

List<String> columnsOld = DBUtils.GetColumns(db, TableName);
List<String> columnsNew = DBUtils.GetColumns(db, TableName);

，我需要获得它们的交集。有没有一种快速的方法可以实现这一目标？

Answer 1

您可以使用 retainAll 方法：

columnsOld.retainAll (columnsNew);

Answer 2

使用 Google 的 Guava 库：

Sets.intersection(Sets.newHashSet(setA), Sets.newHashSet(setB))

注意： 这就是很多比天真地与两个列表进行交集更有效：它是 O(n+m)，而 列表版本的 O(n×m) 。对于两百万个项目的列表，这就是数百万次操作和数万亿次操作之间的区别。

Answer 3

由于 keepAll 不会触及参数集合，因此速度会更快：

List<String> columnsOld = DBUtils.GetColumns(db, TableName); 
List<String> columnsNew = DBUtils.GetColumns(db, TableName); 

for(int i = columnsNew.size() - 1; i > -1; --i){
    String str = columnsNew.get(i);
    if(!columnsOld.remove(str))
        columnsNew.remove(str);
}

交集将是 columnsNew 中留下的值。从旧列中删除已比较的值将减少所需的比较次数。

Answer 4

怎么样

private List<String> intersect(List<String> A, List<String> B) {
    List<String> rtnList = new LinkedList<>();
    for(String dto : A) {
        if(B.contains(dto)) {
            rtnList.add(dto);
        }
    }
    return rtnList;
}

Answer 5

如果不关心出现的情况，则使用retainAll，否则使用N.intersection

a = N.asList(12, 16, 16, 17, 19);
b = N.asList(16, 19, 107);
a.retainAll(b); // [16, 16, 19]
N.println(a);

a = N.asList(12, 16, 16, 17, 19);
b = N.asList(16, 19, 107);
a = N.intersect(a, b);
N.println(a); // [16, 19]

N 是 abacus-common< 中的一个实用程序类< /a>

Answer 6

对于流，有一种很好的方法，它可以在一行代码中完成此操作，并且您可以使用两个不同类型的列表，这对于 containsAll 方法来说是不可能的，据我所知：

columnsOld.stream().filter(c -> columnsNew.contains(c)).collect(Collectors.toList());

不同类型列表的示例。如果 foo 和 bar 之间存在关系，并且可以从 foo 获取 bar 对象，那么您可以修改流：

List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));

fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());

Answer 7

如果将第二个列表放入一个集合中，例如 HashSet。只需迭代第一个列表，检查集合中是否存在，如果不存在则删除，您的第一个列表最终将具有您需要的交集。
它比列表中的retainAll或contains要快得多。
这里强调的是使用集合而不是列表。查找的时间复杂度为 O(1)。
firstList.retainAll(new HashSet(secondList))也将起作用。

Answer 8

使用 org.apache.commons.collections4.ListUtils#intersection

Answer 9

使用 Java 8 Stream API（和 Java 9 List.of()）您可以执行以下操作：

List<Integer> list1 = List.of(1, 1, 2, 2);
List<Integer> list2 = List.of(2, 2, 3, 3);

List<Integer> intersection = list1.stream()
    .filter(list2::contains)
    .distinct()
    .collect(Collectors.toList());