哪一个更快？List.contains（）或Map.containsKey（）

我正在编写一种算法，在其中寻找一对值，这些值加在一起会导致我正在寻找另一个值。

我发现使用a Map可以从O（n²）加速我的算法。后来我意识到我并没有真正使用我包含的值，Map因此List就足够了。

我在Google上进行了幂搜索，但是在我的问题的标题中找不到这些方法的渐近运行时间的任何信息。

您能指出我应该在哪里寻找这些信息吗？

后来我意识到我并没有真正使用我包含的值，Map因此List就足够了。

Map不仅是键值对的列表，而且是从键到值的唯一映射。所以，当你从改变Map到List，您允许重复，你以前没有。另一方面，a

Set恰好是Map没有值的a。因此，请考虑使用HashSet。

至于搜索的复杂性：

list.contains是O（n），hashSet.containsO（1）和treeSet.containsO（log n）。

有关现在HashMap有效的一般信息，请使用Google的“哈希表”。对于TreeMap，Google表示“二叉树”或类似名称。维基百科在这些主题上有很好的条目。

但是要小心，避免上课Hashtable。这是现代图书馆中的考古文物。对于您的情况HashSet可能是最佳选择。