最近我接受了一次面试，被问到一个问题。
我有两个集合，每个集合大约有100万条记录。我需要找到这两个集合中的共同元素。
我的回答：
我将创建一个新的空集合，并提供以下解决方案，但他并不满意。他说由于有100万条记录，所以这个解决方案不够好。
public Set<Integer> commonElements(Set<Integer> s1, Set<Integer> s2) {
Set<Integer> res = new HashSet<>();
for (Integer temp : s1) {
if(s2.contains(temp)) {
res.add(temp);
}
}
return res;
}
那么解决这个问题的更好方法是什么呢？
首先：为了确定两个集合的交集，您必须查看至少其中一个集合的所有条目（以确定它是否在另一个集合中）。没有任何神奇的方法可以告诉你在不到O(min(size(s1), size(s2))的时间内。完结撒花。
接下来要告诉面试官的事情是：“100万条目。你一定在开玩笑。现在是2023年，任何像样的硬件都可以在不到一秒钟内处理两个100万项设置”（当然：这仅适用于便宜比较的对象，例如此处的整数实例。如果oneRecord.equals(anotherRecord)是超级昂贵的操作，则100万个条目在2023年仍可能是个问题）。
然后简要提到了解决这个问题的各种内置方法以及各种第三方库。但是避免另外两个答案犯的错误：指向计算相交的库根本不是将其作为此问题的“解决方案”出售的内容。
您知道，在编码方面：Java Set接口对此有一个简单的解决方案：s1.retainAll(s2)计算两个集合的连接，因为它删除了s1中不在s2中的所有元素。
显然，您必须在面试中提到这将修改s1。
如果要求不修改s1或s2，则您的解决方案是可行的方式，除此之外，没有任何可以降低运行时成本的方法。如果有的话，您可以为两个集合调用size()并迭代具有较少条目的那一个。
或者，你可以这样做：
Set<String> result = new HashSet<>(s1);
return result.retain(s2);
但最终，您必须迭代一个集合，并对于每个元素确定它是否在第二个集合中。
当然，对于这样的问题，真正的答案始终是向面试官展示您能够将问题分解为其不同的方面。您概述基本约束条件，概述不同的解决方案并讨论它们的优缺点。例如我，我希望您坐下来，也许写一个像这样的程序：
public class Numbers {
private final static int numberOfEntries = 20_000_000;
private final static int maxRandom = numberOfEntries;
private Set<Integer> s1;
private Set<Integer> s2;
@Before
public void setUp() throws Exception {
Random random = new Random(42);
s1 = fillWithRandomEntries(random, numberOfEntries);
s2 = fillWithRandomEntries(random, numberOfEntries);
}
private static Set<Integer> fillWithRandomEntries(Random random, int entries) {
Set<Integer> rv = new HashSet<>();
for (int i = 0; i < entries; i++) {
rv.add(random.nextInt(maxRandom));
}
return rv;
}
@Test
public void classic() {
long start = System.currentTimeMillis();
HashSet<Integer> intersection = new HashSet<>();
s1.forEach((i) -> {
if (s2.contains(i))
intersection.add(i);
});
long end = System.currentTimeMillis();
System.out.println("foreach duration: " + (end-start) + " ms");
System.out.println("intersection.size() = " + intersection.size());
}
@Test
public void retainAll() {
long start = System.currentTimeMillis();
s1.retainAll(s2);
long end = System.currentTimeMillis();
System.out.println("Retain all duration: " + (end-start) + " ms");
System.out.println("intersection.size() = " + s1.size());
}
@Test
public void streams() {
long start = System.currentTimeMillis();
Set<Integer> intersection = s1.stream().filter(i -> s2.contains(i)).collect(Collectors.toSet());
long end = System.currentTimeMillis();
System.out.println("streaming: " + (end-start) + " ms");
System.out.println("intersection.size() = " + intersection.size());
}
@Test
public void parallelStreams() {
long start = System.currentTimeMillis();
Set<Integer> intersection = s1.parallelStream().filter(i -> s2.contains(i)).collect(Collectors.toSet());
long end = System.currentTimeMillis();
System.out.println("parallel streaming: " + (end-start) + " ms");
System.out.println("intersection.size() = " + intersection.size());
}
}
首先观察到的是：我决定使用2000万条目运行。我从200万开始，但是所有三个测试都在500毫秒以下良好运行。这是在我的Mac Book Pro上打印出来的20百万结果:
foreach duration: 9304 ms
intersection.size() = 7990888
streaming: 9356 ms
intersection.size() = 7990888
Retain all duration: 685 ms
intersection.size() = 7990888
parallel streaming: 6998 ms
intersection.size() = 7990888
正如预期的那样：所有相交部分的大小都相同（因为我用随机数生成器种子来获得可比较的结果）。
而令人惊奇的是：就地修改s1...是迄今为止最便宜的选项。它以10倍的速度击败了流处理。还要注意：并行流在这里更快。当运行1百万个条目时，顺序流速度更快。
因此，我最初提到“100万条目不是性能问题”。这是一个非常重要的声明，因为它告诉面试官，您不是那些浪费时间微调不存在的性能问题的人之一。
你可以使用
CollectionUtils
它来自于Apache。
CollectionUtils.intersection(Collection a,Collection b)
s1.retainAll(s2);
参考 https://www.w3resource.com/java-exercises/collection/java-collection-hash-set-exercise-11.php
s1的内容。希望面试官并不是在寻找一个答案，而是想看看候选人对任何选择所涉及问题的理解程度。 - Andy Turner
s1.retainAll(s2)? - user330315SortedSet，您可以迭代这两个集合，推进一个迭代器或另一个迭代器，直到迭代器指向相等的元素。 - Andy Turner