哪一个更快？ List.contains（）或Map.containsKey（） [英] Which one is faster? List.contains() or Map.containsKey()

问题描述

我在写一个算法，在那里我查找的值对，当添加在一起导致另一个值，我正在寻找。

我想出了a Map 会加快我的算法从O（n²）。我后来意识到，我不真的使用包含在 Map 中的值，因此 List 就足够了。 p>

我在Google上进行了大功率搜索，但我没有在我的问题标题中找到关于这些方法的渐近运行时间的任何信息。

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

解决方案

list.contains 是O（n），而 map.containsKey 是O（1）对于哈希表，O（logn）
对于hashmable，google为hashtable。对于treemaps，google为二叉树或类似。维基百科在这些主题上有很好的条目。

如果你不需要地图，你可以使用相应的集合。它们是在相应的映射中实现的，其中的值只是一些虚拟的单例对象。

但是，要避免类 Hashtable 。这是一个考古学的文物在现代图书馆。对于你的情况 HashSet 可能是最好的选择。

I'm writing an algorithm where I look for pairs of values which when added together results in another value I'm looking for.

I figured out that using a Map will speed up my algorithm from O(n²). I later realized that I don't really use the values contained in my Map so a List will suffice.

I did a power search on Google but I did not find any information on the asymptotic running time of those methods in the title of my question.

Can you point out where should I look for such information?

解决方案

list.contains is O(n) whereas map.containsKey is O(1) for hashmaps, O(logn) for treemaps. For hashmaps, google for hashtable. For treemaps, google for binary tree or similar. Wikipedia has good entries on these subjects.

If you don't need a map, you can use the corresponding set. Inside they are implemented in terms of corresponding maps, where the value is just some dummy singleton object.

Be careful, however, to avoid the class Hashtable. It's an archaeological artefact in the modern library. For your case HashSet is probably the best choice.

这篇关于哪一个更快？ List.contains（）或Map.containsKey（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！