哪一个更快？ List.contains（）或Map.containsKey（）
我正在写一个算法，在那里我寻找成对的值，当它们加在一起时会产生另一个我正在寻找的值。
我发现使用Map会使我的算法从O（n²）加速。 我后来意识到我并没有真正使用我的Map包含的值，所以List就足够了。
我在Google上进行了powershell搜索，但是在我的问题标题中没有找到关于这些方法的渐近运行时间的任何信息。
你能指出我应该在哪里寻找这些信息吗？
list.contains是O（n）而map.containsKey对于map.containsKey是O（1），对于树图是O（logn）。 对于hashmaps，谷歌搜索哈希表。 对于树形图，谷歌搜索二叉树或类似树。 维基百科在这些主题上有很好的条目。
如果您不需要地图，则可以使用相应的集合。 在内部，它们是根据相应的映射实现的，其中值只是一些虚拟单例对象。
但是，要小心避免使用Hashtable类。 这是现代图书馆的考古文物。 对于你的情况， HashSet可能是最好的选择。
Map和List是接口，因此没有关于它们的实现和性能的信息。 但是如果你使用最新的实现（ List LinkedList或ArrayList ，以及Map HashMap contains() ，在最坏的情况下， contains()方法必须遍历整个列表，并将你的元素与每个条目进行比较。 这是O（n）操作。
如果使用HashMap ，则实现完全不同： HashMap包含的条目数多于其中的元素（实际上，对于地图中的n个元素，数组大小介于4n / 3和3n / 2之间）。 它计算键的哈希值，它是一个int，并将它包装在0和你的数组大小之间（假设这个数字是i ）。 然后它将元素放在数组的索引i （或i+1 ， i+2 ……如果已经采用了先前的索引）。 因此，当您使用containsKey检查密钥存在时，它将重新计算散列和i值，并检查i ， i+1 …索引，直到找到空数组单元格。 理论上，你可以有一个O（n）最坏的情况，如果数组几乎已满，所有的键都具有几乎相同的值，但是具有良好的散列函数，你有常量时间contains和get函数。 （但是，如果您不需要调整数组大小，添加元素很快，这非常慢 – 我认为您需要重新计算每个键的索引）。
因此，如果你需要检查集合中的键外观，并且不需要保持顺序（有一个SortedHashMap ，但我不知道它的性能），地图真的更快，但它需要更多的内存。
此外，如果您不需要键值，则可以使用HashSet （内部与HashMap相同）。
Map.containsKey（）考虑到你正在使用HashMap，因为在HashMap中搜索是在O（1）中完成的。
List.contains（）通常应该采用顺序搜索或二进制搜索，因此复杂性至少为O（log n）