java - 为恒定时间 contains() 创建一个 HashMap 和一个 ArrayList 是一个有效的策略吗？

Question

我有一个 ArrayList，它的长度可以是 0 到 5000 个项目(也是相当大的对象)。

有一次我将它与另一个 ArrayList 进行比较，以找到它们的交集。我知道这是 O(n^2)。

在这个 ArrayList 旁边创建一个 HashMap 来实现恒定时间查找，这是一个有效的策略，以便将复杂性降低到 O(n)？还是另一种数据结构的开销根本不值得？我相信它不会占用额外的空间(除了引用文献)。

(我知道，我确定“这取决于我在做什么”，但我很想知道是否有任何缺点让它变得毫无意义，或者它是否真的是一种常见的使用策略。是的，我知道关于过早优化的引述。我只是从理论上的角度好奇)。

Answer 1

首先，一个简短的旁注:

And yes, I'm aware of the quote about prematurely optimizing.

你在这里问的是不是“过早的优化”!

您不是在谈论用一些奇怪的按位运算替换乘法，“因为它们更快(在 90 年代的 PC 上，在 C 程序中)”。您正在为您的应用程序模式考虑正确的数据结构。您正在考虑应用案例(尽管您没有告诉我们有关它们的很多细节)。您正在考虑选择某种数据结构对您算法的渐近 运行时间的影响。这是规划，或者可能是工程，但不是“过早的优化”。

---

话虽这么说，但要告诉您您已经知道的内容:这取决于情况。

详细说明一下:这取决于您对这些集合执行的实际操作(方法)、您执行的频率、它们的时间关键程度以及应用程序对内存的敏感程度。

_{(对于 5000 个元素，后者应该不是问题，因为仅存储引用 - 请参阅评论中的讨论)}

一般来说，如果它们总是应该包含相同的元素。这种措辞是有意为之的:您应该始终了解这两个集合之间的差异。主要是:Set 只能包含每个元素一次，而 List 可能多次包含相同的元素。

对于所有提示、建议和注意事项，应牢记这一点。

但是，即使在您的情况下列表总是只包含一次元素是理所当然的，那么您仍然必须确保两个集合都得到适当的维护。如果你真的只是存储它们，你很容易导致细微的错误:

private Set<T> set = new HashSet<T>();
private List<T> list = new ArrayList<T>();

// Fine
void add(T element)
{
    set.add(element);
    list.add(element);
}

// Fine
void remove(T element)
{
    set.remove(element);
    list.remove(element); // May be expensive, but ... well
}

// Added later, 100 lines below the other methods:
void removeAll(Collection<T> elements)
{
    set.removeAll(elements);
    // Ooops - something's missing here...
}

为了避免这种情况，人们甚至可以考虑创建一个专用的集合类——类似于 FastContainsList，它结合了 Set 和 List ，并将 contains 调用转发给 Set。但是您很快就会注意到，要不违反 Collection 和 List 接口(interface)的约定是很困难的(或者可能是不可能的)一个集合，除非“你不能添加元素两次”的条款成为契约(Contract)的一部分......

---

因此，所有这一切都取决于你想用这些方法做什么，以及你真正需要哪个接口(interface)。如果您不需要 List 的索引访问，那很简单。否则，引用你的例子:

At one point I compare it against another ArrayList, to find their intersection. I know this is O(n^2).

您可以通过本地创建集来避免这种情况:

static <T> List<T> computeIntersection(List<T> list0, List<T> list1)
{
    Set<T> set0 = new LinkedHashSet<T>(list0);
    Set<T> set1 = new LinkedHashSet<T>(list1);
    set0.retainAll(set1);
    return new ArrayList<T>(set0);
}

这将有 O(n) 的运行时间。当然，如果您经常这样做，但很少更改列表的内容，则可以选择避免复制，但由于上述原因，维护所需的数据结构可能会变得棘手。