哪个工会更有效率：List/HashSet

Question

我正在写一些算法，我需要使用一个集合，而且他们的主要（也是唯一的）动作就是union。

我将有大约百万对象，我需要知道哪些系列有着更高效的工会法 - 列表或HashSet的（OT也许别的东西吗？）。

在此先感谢。

Answer 1

我猜，当你说：“我将使用distinct与List”，你的意思是这样的：

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); 

列表API没有distinct()方法，没有union()方法。

---

如果你实际使用Collection.contains()执行工会，那么HashSet()会比任何标准的List实现快得多。正如@JBNizet所述：

HashSet.contains是O（1）。 List.contains是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. 

几乎相同的代码适用于列表。但它是太多较慢。

你问：

好吧，是的。但是工会呢？

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

那是什么？ O（？）

请参见下面的文章：

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

所以工会的都是相同的O（N）（N - 大小第二集合）？

号

• 使用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大小写的性能。如上所述。

---

最后，如果元素类型是Integer然后Bitset可以比任一List或HashSet更有效。它可以使用少两个数量级的内存！取决于范围的整数，和密度的集合。

---

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