我试图弄清楚使用 keySet().iterator().next() 方法获取 HashMap 和 LinkedHashMap java 集合类中第一个键的时间复杂度。 HashMap 中的顺序并不重要。我只想选择第一个可用的 key 。
我一直在挖掘这两个类的源代码，看起来像这样:
在 HashMap 中，它遍历所有条目，直到找到非 null 一。因此，最坏的情况是 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)。
关于java - HashMap 和 LinkedHashMap 类中 keySet().iterator().next() 的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27460279/