为恒定时间 contains() 创建一个 HashMap 和一个 ArrayList 是一个有效的策略吗？
Is creating a HashMap alongside an ArrayList just for constant-time contains() a valid strategy?
我有一个 ArrayList，它的长度可以从 0 到 5000 个项目（也是相当大的对象）。
有一次我将它与另一个 ArrayList 进行比较，以找到它们的交集。我知道这是 O(n^2).
在这个 ArrayList 旁边创建一个 HashMap 来实现恒定时间查找，这是一种有效的策略，以便将复杂度降低到 O(n)？还是另一种数据结构的开销根本不值得？我相信它不会占用额外的 space（除了引用）。
（我知道，我确定'这取决于我在做什么'，但我很想知道是否有任何缺点使它毫无意义，或者它是否实际上是一种常见的使用策略。并且是的，我知道关于过早优化的引述。我只是从理论上的角度好奇）。
首先，简短的旁注：
And yes, I'm aware of the quote about prematurely optimizing.
你在这里问的是不是 "premature optimization"!
您不是在谈论用一些奇数位运算替换乘法 "because they are faster (on a 90's PC, in a C-program)"。您正在为您的应用程序模式考虑正确的数据结构。您正在考虑应用案例（尽管您没有告诉我们有关它们的很多细节）。您正在考虑选择某种数据结构对算法的 asymptotic 运行 时间的影响。这是规划，或者可能是工程，但不是"premature optimization"。
话虽这么说，但要告诉你你已经知道的事情：这取决于。
详细说明一下：这取决于您对这些集合执行的实际操作（方法）、您执行的频率、它们的时间关键程度以及应用程序对内存的敏感程度。
（对于 5000 个元素，后者应该不是问题，因为只存储引用 - 请参阅评论中的讨论）
一般来说，如果它们总是应该包含相同的内容，我也会犹豫是否真的 将 Set 与 List 一起存储元素。这种措辞是有意为之的：您应该始终了解这两个集合之间的差异。主要是：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...
}
为了避免这种情况，人们甚至可以考虑创建一个专用集合 class - 类似于 FastContainsList，它结合了 Set 和 List，然后转发contains 调用 Set。但是您很快就会注意到，要不 违反此类集合的Collection 和List 接口的约定是很难的（或者可能是不可能的），除非 "You may not add elements twice" 成为合同一部分的条款...
同样，所有这一切都取决于你想用这些方法做什么，以及你真正需要哪个接口。如果你不需要 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) 时间。当然，如果你经常这样做，但很少更改列表的内容，则可以选择避免复制，但由于上述原因，维护所需的数据结构可能会变得棘手。
我有一个 ArrayList，它的长度可以从 0 到 5000 个项目（也是相当大的对象）。
有一次我将它与另一个 ArrayList 进行比较，以找到它们的交集。我知道这是 O(n^2).
在这个 ArrayList 旁边创建一个 HashMap 来实现恒定时间查找，这是一种有效的策略，以便将复杂度降低到 O(n)？还是另一种数据结构的开销根本不值得？我相信它不会占用额外的 space（除了引用）。
（我知道，我确定'这取决于我在做什么'，但我很想知道是否有任何缺点使它毫无意义，或者它是否实际上是一种常见的使用策略。并且是的，我知道关于过早优化的引述。我只是从理论上的角度好奇）。
首先，简短的旁注：
And yes, I'm aware of the quote about prematurely optimizing.
你在这里问的是不是 "premature optimization"!
您不是在谈论用一些奇数位运算替换乘法 "because they are faster (on a 90's PC, in a C-program)"。您正在为您的应用程序模式考虑正确的数据结构。您正在考虑应用案例（尽管您没有告诉我们有关它们的很多细节）。您正在考虑选择某种数据结构对算法的 asymptotic 运行 时间的影响。这是规划，或者可能是工程，但不是"premature optimization"。
话虽这么说，但要告诉你你已经知道的事情：这取决于。
详细说明一下：这取决于您对这些集合执行的实际操作（方法）、您执行的频率、它们的时间关键程度以及应用程序对内存的敏感程度。
（对于 5000 个元素，后者应该不是问题，因为只存储引用 - 请参阅评论中的讨论）
一般来说，如果它们总是应该包含相同的内容，我也会犹豫是否真的 将 Set 与 List 一起存储元素。这种措辞是有意为之的：您应该始终了解这两个集合之间的差异。主要是：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...
}
为了避免这种情况，人们甚至可以考虑创建一个专用集合 class - 类似于 FastContainsList，它结合了 Set 和 List，然后转发contains 调用 Set。但是您很快就会注意到，要不 违反此类集合的Collection 和List 接口的约定是很难的（或者可能是不可能的），除非 "You may not add elements twice" 成为合同一部分的条款...
同样，所有这一切都取决于你想用这些方法做什么，以及你真正需要哪个接口。如果你不需要 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) 时间。当然，如果你经常这样做，但很少更改列表的内容，则可以选择避免复制，但由于上述原因，维护所需的数据结构可能会变得棘手。