哪一个更快？List.contains()或Map.containsKey()

Question

我正在写一个算法,我在那里寻找成对的值,这些值在加在一起时会产生另一个我正在寻找的值.

我发现使用一个Map会从O(n²)加速我的算法.我后来才意识到我并没有真正使用我所包含的值,Map所以List就足够了.

我在Google上进行了强力搜索,但是在我的问题标题中没有找到关于这些方法的渐近运行时间的任何信息.

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

Answer 1

list.contains是O(n),而map.containsKey对于散列图是O(1),对于树图是O(logn).对于hashmaps,谷歌搜索哈希表.对于树形图,谷歌搜索二叉树或类似的.维基百科在这些主题上有很好的条目.

如果您不需要地图,则可以使用相应的集合.在内部,它们是根据相应的映射实现的,其中值只是一些虚拟单例对象.

但要小心避免上课Hashtable.这是现代图书馆的考古文物.对于你的情况HashSet可能是最好的选择.

Answer 2

Map并且List是接口,因此没有关于它们的实现和它们的性能的信息.但是,如果您使用最新的实现(LinkedList或ArrayListfor for List和HashMapfor Map),则contains()在最坏的情况下,该方法必须遍历整个列表,并将您的元素与每个条目进行比较.这是O(n)操作.

如果使用a HashMap,则实现完全不同:HashMap包含一个数组,其中的条目数多于其中的元素(实际上,对于地图中的n个元素,数组大小介于4n/3和3n/2之间).它计算键的哈希值,它是一个int,并将它包装在0和你的数组大小之间(假设这个数字是i).然后它会把元素的索引,在i数组(或i+1,i+2...如果以前的索引已经采取了).因此,当您检查密钥存在时containsKey,它将重新计算散列和i值,并检查i,i+1...索引,直到找到一个空的数组单元格.理论上,你可以有一个O(n)最坏情况,如果数组几乎已满,所有键都具有几乎相同的i值,但是具有良好的散列函数,你有恒定时间contains和get函数.(然而,添加元素是快,如果你没有需要调整的数组,这是真的慢-我认为你需要重新计算每个键的索引).

因此,如果你需要检查集合中的键外观,并且不需要保持顺序(有一个SortedHashMap,但我不知道它的性能),地图真的更快,但它将需要更多的内存.

此外,如果您不需要键值,则可以使用a HashSet(内部与a相同HashMap).