我正在编写一个算法,其中我要查找两个值的组合,使它们相加后得到我想要的另一个值。
我发现使用Map
将会加快我的算法速度,从O(n²)降为更低。但后来我意识到实际上并不需要使用Map
中的值,因此只需使用List
。
我在谷歌上进行了强力搜索,但是没有找到有关本题目方法的渐进运行时间的任何信息。
请问您能指出我应该在哪里寻找这样的信息吗?
我正在编写一个算法,其中我要查找两个值的组合,使它们相加后得到我想要的另一个值。
我发现使用Map
将会加快我的算法速度,从O(n²)降为更低。但后来我意识到实际上并不需要使用Map
中的值,因此只需使用List
。
我在谷歌上进行了强力搜索,但是没有找到有关本题目方法的渐进运行时间的任何信息。
请问您能指出我应该在哪里寻找这样的信息吗?
Map
和List
是接口,因此没有关于它们的实现或性能的信息。但是如果您使用最新的实现(LinkedList
或ArrayList
用于List
,HashMap
用于Map
),contains()
方法必须在最坏情况下通过整个列表,并将您的元素与每个条目进行比较。这是一个O(n)操作。
如果您使用HashMap
,实现方式完全不同: HashMap
包含一个具有比其中元素更多的条目的数组(实际上,对于映射中的n个元素,您的数组大小在4n/3到3n/2之间)。它计算键的哈希值,这是一个int,并将其包装在0和数组大小之间(假设这个数字是i
)。然后它将元素放置在数组的索引i
(或i+1
,i+2
…如果先前的索引已经被占用)。因此,当您使用containsKey
检查键是否存在时,它将重新计算哈希和i
值,并检查i
,i+1
…索引,直到找到空的数组单元格。理论上,如果数组几乎满了,并且所有键具有几乎相同的i
值,则最坏情况下可以达到O(n),但是使用良好的哈希函数,您可以获得常数时间的contains
和get
函数。 (但是,如果不需要调整数组大小(这非常慢),添加元素很快-我认为您需要重新计算每个键的索引)。
因此,如果您需要检查集合中是否存在键,并且不需要保持顺序(有一个SortedHashMap
用于此,但我不知道它的性能),则映射速度更快,但会占用更多内存。
此外,如果您不需要键值对,请使用HashSet
(它在内部与HashMap
相同)。
HashSet似乎更快:
另外,请注意通常不需要在HashMap和HashSet上调用.contains(),但我在代码中保留了它,以更准确地回答您的问题:
long t = System.currentTimeMillis();
HashMap<String, Boolean> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
String s = (Math.random() * 100) + "";
if (!map.containsKey(s)) {
map.put(s, true);
}
}
System.out.println("HashMap: " + (System.currentTimeMillis() - t));
t = System.currentTimeMillis();
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
String s = (Math.random() * 100) + "";
if (!list.contains(s)) {
list.add(s);
}
}
System.out.println("ArrayList: " + (System.currentTimeMillis() - t));
t = System.currentTimeMillis();
HashSet<String> set = new HashSet<>();
for (int i = 0; i < 10000; i++) {
String s = (Math.random() * 100) + "";
if (!set.contains(s)) {
set.add(s);
}
}
System.out.println("HashSet: " + (System.currentTimeMillis() - t));
如果你使用的是HashMap,那么Map.containsKey()的搜索复杂度为O(1)。
List.contains()通常会采用顺序搜索或二分搜索,因此其复杂度至少为O(log n)。
Set.contains()
和Map.containsKey()
,它们基本上是相等的——对于每种类型的 Map,在其实现中都有相应的 Set 类型。 - Bohemian