高效地找到多个字符串集合的交集

Question

我有多个变长ArrayList，需要找到它们的交集。字符串集合数量的实际上限可能在35左右但也可能更多。我不需要任何代码，只是想听听其他高效解决思路。

目前来看，我的解决方案看起来具有渐进运行时间为Θ(n²)的特点。

感谢任何帮助！

tshred

编辑：为了澄清，我真正想知道的是是否有更快的方法。比Θ(n²)更快的方法。

- tshred

---

谢谢大家的帮助！字符串实际上是在已经存在的数组列表中的对象内部，这就是为什么我一直将它们留在数组中的原因。我从未使用过提到的Java集合类，但肯定会使用它们。感谢您的建议。问题已解决。 - tshred

参见：如何计算两个集合的交集？ - Basil Bourque

Answer 1

Set.retainAll()是查找两个集合的交集的方法，如果你使用HashSet，那么将你的ArrayList转换为Set并在循环中使用retainAll()实际上是O(n)的。

- Michael Borgwardt

---

你只需要将其中一个列表放入集合中即可。 - Hans

它只预计为O(n)。这不是最坏的情况！ - Till Schäfer

Answer 2

接受的答案已经很好了；更新一下：自从Java 8之后，有一种稍微更有效的方法来查找两个Set的交集。

Set<String> intersection = set1.stream()
    .filter(set2::contains)
    .collect(Collectors.toSet());

稍微更高效的原因是，原始方法必须将set1的元素添加到结果集中，如果它们不在set2中，则必须再次将其删除。这种做法仅向结果集中添加需要在其中的内容。

严格来说，在Java 8之前也可以这样做，但是没有Stream，代码会更加费力。

如果两个集合大小差别很大，则应优先选择较小的集合进行流处理。

- bowmore

---

请注意，小型集合上不支持流式操作。这是因为流式操作需要迭代元素，而另一个（更大的）集合可以通过哈希搜索进行查找（对于HashSet来说是O(1)）。 - Ondra Žižka

@bowmore 如果我错了，请纠正我，但我认为将 .collect(Collectors.toSet()) 更改为 .forEach(e -> ...) 将是找到两个集合交集的理想方式，而不会创建任何一个集合的副本或对交集的引用。换句话说，如果 a = { 1, 2, 3 } 和 b = { 4, 5, 6 } 并且调用了 forEach(e -> ...)，那么在任何时候只会存在七个元素引用。三个来自集合 a，三个来自集合 b，一个来自回调变量 e。 - Hatefiend

@bowmore 另外补充一下 @Ondra Žižka 提到的，你肯定会先检查 set1 或 set2 中哪个元素数量最少，然后将该集合作为流式处理的集合。剩余的集合将被引用为 contains。 - Hatefiend

@Hatefiend 如果在上下文中你知道集合将相对较小，或者始终大小可比较，那么不需要进行这样的检查。我在我的答案中也这样说了。 - bowmore

@Hatefiend 一个小例子：我们有一个包含所有打折商品的集合，以及一个包含客户购物篮中商品的集合。我不会费心去写if语句。从上下文来看，我知道大多数情况下购物篮集合会更小。我总是会遍历购物篮，即使有时它可能比打折商品集合还要大。 如果我有一组提到一个主题的推文，以及另一组提到另一个主题的推文，两者都可能达到数百万条，但也可能非常少，那么我会进行检查。 - bowmore

Answer 3

此外，Google Guava 中还有一个静态方法 Sets.intersection(set1, set2)，它返回两个集合交集的不可修改视图。

- Sonson123

---

因为这是一个视图，我记得它有重复交叉点的不幸副作用，所以需要小心使用。if (intersetionSet.size() < 1000) { doSomethingWith(intersetionSet); } - Annan Yearian

Answer 4

还有一个想法——如果你的数组/集合大小不同，那么从最小的开始是有意义的。

- a1ex07

Answer 5

最好的选择是使用HashSet来存储这些列表的内容，而不是使用ArrayList。如果你能这样做，你可以创建一个临时的HashSet，将要交集的元素添加到其中（使用putAll(..)方法）。然后执行tempSet.retainAll(storedSet)，tempSet将包含交集。

- Chris Dennett

Answer 6

将它们排序（n lg n），然后进行二分查找（lg n）。

- corsiKa

Answer 7

你可以使用单个 HashSet。当对象已经在集合中时，它的 add() 方法返回 false。从列表中添加对象并标记 false 返回值的次数将为您提供集合的并集和直方图数据（并且计数+1等于列表计数的对象是您的交集）。如果您将计数抛到 TreeSet 中，您可以尽早检测到空交集。

- Rostislav Matl

Answer 8

在编程中如果需要判断两个集合是否有交集，我使用下面这段Java 8+版本的代码片段：

set1.stream().anyMatch(set2::contains)

- kikea