java - 哪个联合效率更高: List/HashSet

Question

我正在编写一些需要使用集合的算法，并且它们的主要(也是唯一)操作是并集。

我将拥有大约100万个对象，并且我需要知道哪个集合具有更有效的联合方法 - 列表或 HashSet(也许还有别的吗？)。

提前致谢。

Answer 1

我猜当你说“我将使用 distinct 与列表”时，你的意思是这样的:

  List l = ...
  Set result = Collectors.toSet(l.stream().distinct()).union(someOtherSet);

与此相比:

  HashSet h = ...
  Set result = h.union(someOtherSet);

显然第二个版本更有效。第一个必须从列表中生成一个中间集。每次运行它时。

第一个节省的唯一东西是一些内存(从长远来看)，因为中间集在使用后变得无法访问。

第一个版本可以更简单、更有效地编写为:

  List l = ...
  Set result = new HashSet(l).union(someOtherSet);

List API 没有 distinct() 方法，也没有 union() 方法。

---

如果您实际上使用Collection.contains()来执行联合，那么HashSet()将比任何标准List快得多> 实现。正如 @JBNizet 所说:

HashSet.contains is O(1). List.contains is O(n).

例如:

  Set result = new HashSet();
  for (Integer element: set1) {
      if (set2.contains(element)) {
          result.add(element);
      }
  }
  // result now contains the union of set1 and set2.

几乎相同的代码适用于列表。但速度慢得多。

你问:

Ok, yeah. But how about union?

见上文。这是关于使用 contains 调用实现 union 。

Whats that? O(?)

请参阅以下文章:

• https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
• https://en.wikipedia.org/wiki/Big_O_notation

So the both of the unions are the same O(N) (n - size of the second collection)?

没有。

• 使用 HashSet:N x O(1) 为 O(N)
• 使用列表:N x O(N) 为 O(N^2)

或更准确地说:

• 使用 HashSet:min(M, N) x O(1) 为 O(min(M, N))
• 使用列表:N x O(M) 为 O(NM)

其中 N 和 M 是两个集合/列表的大小。您可以通过迭代两个集合中较小的一个来调整 HashSet 情况的性能。正如上面所反射(reflect)的。

---

最后，如果元素类型为 Integer，则 Bitset 可能比 List 或 HashSet 更高效。而且它可以使用少几个数量级的内存!取决于整数的范围以及集合的密度。

---

这就是Java分析。我不熟悉 Scala，但底层计算和复杂性是相同的。