java - Java中集合vs数组vs链表的性能

Question

我正在尝试研究 Java 中集合、数组和链表在性能方面的区别，所以我正在研究的示例是
如果我们需要在数组中查看两个数组、两个集合和两个链表之间的公共对象我们应用 for 循环和比较，在 set 中我们使用 interscet 还是 union？但是时间上有很大的不同，有什么想法吗？

Answer 1

相交集和相交列表或数组是有区别的。当你与两个集合相交时，你需要遍历其中一个，看看另一个集合中是否有对应的成员。集合的检索时间是 O(1)，所以交集是 O(n)。与列表或数组相交时，交集为 O(n^2)，因为对于一个列表/数组中的每个成员，您需要遍历整个另一个列表/数组

Answer 2

我建议你为微基准测试准备一个测试平台，这样你就可以看到时间上的差异。确保至少重复 10 次，并在测量之外进行热身。然后计算均值和标准差。如果我没记错的话，有一个漂亮的谷歌项目可以提供这个。

您应该清楚的第一件事是渐近复杂性或大 O。例如，如果您想做一个集合相交，最好的方法是。

 SortedSet<String> set1 = new TreeSet<String>(); // and populate
 SortedSet<String> set2 = new TreeSet<String>(); // and populate
 // intersect of two sorted sets can be done in linear time

上面是 O(n) 而你提到的所有其他选择都是 O(n^2) 读取更复杂和更慢。