我试图弄清楚使用方法keySet().iterator().next()获取HashMap和LinkedHashMap java集合类中的第一个密钥的时间复杂度是多少。HashMap 中的顺序并不重要。我只想选择第一个可用的密钥。
我一直在挖掘这两个类的源代码，看起来像这样：
-
在 HashMap 中，它会遍历所有条目，直到找到非空值一。因此，最坏的情况是O(N(。
-
在 LinkedHashMap 中，它看起来像是 O(1(。
有人可以确认或纠正这些陈述吗？
我知道Apache Commons Collections中的LinkedMap类有方法firstKey()和lasKey()。这些方法的时间复杂度是多少？
更新：
根据我所做的测试，HashMap 和 LinkedHashMap 似乎都在 O(1( 中执行，因为当元素数量以 2 的幂增加时，执行时间不会增加：
import org.junit.Test;
import java.util.*;
import static org.junit.Assert.*;
public class LinkedHashMapTest {
private static final Random rnd = new Random();
@Test
public void testHashMapFirstKeyTime() throws Exception {
System.out.println("**testHashMapFirstKeyTime:**");
firstKeyTime(new HashMap<Key, Integer>(), 22);
}
@Test
public void testLinkedHashMapFirstKeyTime() throws Exception {
System.out.println("**testLinkedHashMapFirstKeyTime:**");
firstKeyTime(new LinkedHashMap<Key, Integer>(), 22);
}
private void firstKeyTime(Map<Key, Integer> map, int bits) {
int m = 0;
map.clear();
for (int i = 1; i <= bits; i++) {
int n = 1 << i;
for (int j = m; j < n; j++) {
Key key = new Key();
key.s = String.valueOf(rnd.nextInt());
key.d = new Date(System.currentTimeMillis());
key.i = rnd.nextInt();
map.put(key, j);
}
m = n;
long startTime = System.currentTimeMillis();
Key firstKey = map.keySet().iterator().next();
long duration = System.currentTimeMillis() - startTime;
System.out.printf("Retrieving first key %s in a map of size %10d took %d ms%n", firstKey, map.size(), duration);
assertTrue(duration < 5); // less than 5ms
}
}
private static class Key {
String s;
Date d;
int i;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Key key = (Key) o;
if (i != key.i) return false;
if (!d.equals(key.d)) return false;
if (!s.equals(key.s)) return false;
return true;
}
@Override
public int hashCode() {
int result = s.hashCode();
result = 31 * result + d.hashCode();
result = 31 * result + i;
return result;
}
@Override
public String toString() {
return String.format("Key{s='%1$11s', d=%2$tDT%2$tT.%2$tL%2$tz, i=%3$11d}", s, d, i);
}
}
}
testHashMapFirstKeyTime：
Retrieving first key Key{s=' 1985523727', d=12/14/14T02:00:24.335+0100, i= 643333406} in a map of size 2 took 0 ms
Retrieving first key Key{s=' 1985523727', d=12/14/14T02:00:24.335+0100, i= 643333406} in a map of size 4 took 0 ms
Retrieving first key Key{s=' 767922762', d=12/14/14T02:00:24.346+0100, i= 431427041} in a map of size 8 took 0 ms
Retrieving first key Key{s=' -256241316', d=12/14/14T02:00:24.347+0100, i=-1263480851} in a map of size 16 took 0 ms
Retrieving first key Key{s=' -256241316', d=12/14/14T02:00:24.347+0100, i=-1263480851} in a map of size 32 took 0 ms
Retrieving first key Key{s=' -935843053', d=12/14/14T02:00:24.349+0100, i= 438592480} in a map of size 64 took 0 ms
Retrieving first key Key{s='-1067014413', d=12/14/14T02:00:24.352+0100, i= -621892808} in a map of size 128 took 0 ms
Retrieving first key Key{s='-1067014413', d=12/14/14T02:00:24.352+0100, i= -621892808} in a map of size 256 took 0 ms
Retrieving first key Key{s='-1988805714', d=12/14/14T02:00:24.353+0100, i= -61029749} in a map of size 512 took 0 ms
Retrieving first key Key{s='-1926538837', d=12/14/14T02:00:24.353+0100, i=-1072972113} in a map of size 1024 took 0 ms
Retrieving first key Key{s=' -406648261', d=12/14/14T02:00:24.362+0100, i= 201747454} in a map of size 2048 took 0 ms
Retrieving first key Key{s=' 913423510', d=12/14/14T02:00:24.373+0100, i= 532927328} in a map of size 4096 took 0 ms
Retrieving first key Key{s='-1514850500', d=12/14/14T02:00:24.390+0100, i=-1849450899} in a map of size 8192 took 0 ms
Retrieving first key Key{s=' 913423510', d=12/14/14T02:00:24.373+0100, i= 532927328} in a map of size 16384 took 0 ms
Retrieving first key Key{s=' 418571021', d=12/14/14T02:00:24.419+0100, i= 913773732} in a map of size 32768 took 0 ms
Retrieving first key Key{s=' -807723833', d=12/14/14T02:00:24.450+0100, i= 1204270612} in a map of size 65536 took 0 ms
Retrieving first key Key{s=' 239598471', d=12/14/14T02:00:24.483+0100, i= 271236296} in a map of size 131072 took 0 ms
Retrieving first key Key{s=' 1332893667', d=12/14/14T02:00:24.607+0100, i= -494154632} in a map of size 262144 took 0 ms
Retrieving first key Key{s=' 857896380', d=12/14/14T02:00:25.779+0100, i= 771055858} in a map of size 524288 took 0 ms
Retrieving first key Key{s=' 422311855', d=12/14/14T02:00:25.828+0100, i= 1193799319} in a map of size 1048576 took 0 ms
Retrieving first key Key{s=' 422311855', d=12/14/14T02:00:25.828+0100, i= 1193799319} in a map of size 2097152 took 1 ms
Retrieving first key Key{s=' 222881497', d=12/14/14T02:00:34.934+0100, i= 1772777984} in a map of size 4194304 took 0 ms
testLinkedHashMapFirstKeyTime：
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 2 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 4 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 8 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 16 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 32 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 64 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 128 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 256 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 512 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 1024 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 2048 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 4096 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 8192 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 16384 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 32768 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 65536 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 131072 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 262144 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 524288 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 1048576 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 2097152 took 0 ms
Retrieving first key Key{s=' 7710621', d=12/14/14T02:00:35.474+0100, i= -239716357} in a map of size 4194304 took 0 ms
查看代码，对于 HashMap，您找到(在 HashIterator 类中(：
final Entry<K,V> [More ...] nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
}
对于 LinkedHashMap，您可以找到(在 LinkedHashIterator 类中(：
Entry<K,V> [More ...] nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
这似乎证实了你的说法。
关于Apache的LinkedMap：
public Object [More ...] firstKey() {
if (size == 0) {
throw new NoSuchElementException("Map is empty");
}
return header.after.getKey();
}
public Object [More ...] lastKey() {
if (size == 0) {
throw new NoSuchElementException("Map is empty");
}
return header.before.getKey();
}
似乎是 O(1(。