HashMap遍历函数和LinkedHashMap遍历函数之间有什么性能差异values()吗？
问问题
34047 次
7 回答
46
我认为LinkedHashMap由于其出色的nextEntry实现，它的遍历速度必须更快Iterator
这就是为什么：
让我们一步一步从values实现开始。
的HashMap实现values是这样的：
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
LinkedHashMap 扩展自HashMap并继承相同的实现。
不同Iterator之处在于两者的实现Values。
因为HashMap它从 java.util.HashMap.HashIterator
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
但因为LinkedHashMap它从java.util.LinkedHashMap.LinkedHashIterator
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
所以差异基本上归结为nextEntry实施。
因为LinkedHashMap它只是调用 e.after ，其中 e 是Entry，但是在遍历数组以找到下一个下一个时HashMap涉及到一些工作。Entry[]
更新nextEntry()：代码HashMap
final Entry<K,V> 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;
return e;
}
Entry[] 不是连续存储。（两者之间可能有空值）。如果你看一下上面的代码，它的作用是指向当前的 next 并通过遍历 Entry[] 找到下一个 next。
但我认为这种性能提升将以插入为代价。在这两个类中检查该addEntry方法作为练习。
于 2012-10-21T14:43:53.420 回答
45
我编写了一个小分析程序，创建 100 万个键（整数）与 Boolean.TRUE，重复 100 次。发现以下内容：
HashMap:-
Create: 3.7sec
Iterate: 1.1sec
Access: 1.5sec
Total: 6.2sec
LinkedHashMap:-
Create: 4.7sec (30% slower)
Iterate: 0.5sec (50% faster)
Access: 0.8sec (50% faster)
Total : 6.0sec
垃圾收集没有这样做会在一定程度上污染数字，但是我认为 LinkedHashMap 比 HashMap 更有优势，我将在未来的代码中使用它。
于 2014-04-03T13:20:24.947 回答
5
几乎没有关系。问题是：你需要什么。如果元素的顺序相关，则必须使用LinkedHashMap. 否则你只是不需要它，所以使用HashMap.
于 2012-10-21T14:25:22.767 回答
3
最好的建议是“不要害怕尝试”，但我很确定它们非常相似。值集的 getter 是 O(1)，每个迭代器步骤也是如此。遍历链表与遍历哈希桶一样微不足道，可能有一个小优势有利于链表。
于 2012-10-21T14:21:11.640 回答
3
我在 UnitTest 中尝试过，迭代 values() 10000 次，毫秒：806 vs 902。几乎相同。
于 2012-10-21T14:29:54.197 回答
3
是的，在所有迭代中都会有相同的性能差异： 将花费HashMap与条目数加上哈希表大小成正比的时间，并且只花费与条目数成正比的时间。LinkedHashMapHashMapLinkedHashMap
于 2012-10-21T18:53:08.127 回答
2
代码...
import java.lang.management.GarbageCollectorMXBean;
import java.lang.management.ManagementFactory;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;
public class MapTest
{
public static void main(String[] args)
{
int iterations = 1000000;
long time1, time2, time3;
System.nanoTime(); //Just to make sure any possible overhead is done...though there shouldn't really be any
int sequential[] = new int[iterations]; //Counting up from 0
int random[] = new int[iterations]; //Same set of values, but randomized (no duplicates)
HashSet<Integer> addedRandoms = new HashSet<>();
for (int i = 0; i < iterations; i++)
{
sequential[i] = i;
int randomVal = random(iterations);
while (addedRandoms.contains(randomVal)) randomVal = random(iterations); //Get another random instead of sequentially finding another unused value, to prevent clumping
addedRandoms.add(randomVal);
random[i] = random(iterations);
}
HashMap<Integer, Integer> hashMap = new HashMap<>();
LinkedHashMap<Integer, Integer> linkedHashMap = new LinkedHashMap<>();
int gcRuns = 0, prevGCRuns;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) gcRuns += gcBean.getCollectionCount();
prevGCRuns = gcRuns;
//Test
time1 = System.nanoTime();
for (int i : sequential) hashMap.put(i, 0);
time2 = System.nanoTime();
for (int i : sequential) linkedHashMap.put(i, 0);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Put: sequential key (from 0 to " + (iterations - 1) + "), no overwrites", time1, time2, time3, prevGCRuns);
//Test
time1 = System.nanoTime();
for (int i : random) hashMap.put(i, 0);
time2 = System.nanoTime();
for (int i : random) linkedHashMap.put(i, 0);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Put: random key (between 0 and " + (iterations - 1) + " inclusive), all overwrites (exactly one per entry, random order)", time1, time2, time3, prevGCRuns);
//Attempt GC
System.gc();
prevGCRuns = 0;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) prevGCRuns += gcBean.getCollectionCount();
//Test
time1 = System.nanoTime();
for (int i : sequential) hashMap.put(i, 0);
time2 = System.nanoTime();
for (int i : sequential) linkedHashMap.put(i, 0);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Put: sequential key (from 0 to " + (iterations - 1) + "), all overwrites (exactly one per entry, sequential order)", time1, time2, time3, prevGCRuns);
//Empty maps
hashMap = new HashMap<>();
linkedHashMap = new LinkedHashMap<>();
//Attempt GC
System.gc();
prevGCRuns = 0;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) prevGCRuns += gcBean.getCollectionCount();
//Test
time1 = System.nanoTime();
for (int i : random) hashMap.put(i, 0);
time2 = System.nanoTime();
for (int i : random) linkedHashMap.put(i, 0);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Put: random key (between 0 and " + (iterations - 1) + " inclusive), no overwrites", time1, time2, time3, prevGCRuns);
//Test
time1 = System.nanoTime();
for (int i : sequential) hashMap.get(i);
time2 = System.nanoTime();
for (int i : sequential) linkedHashMap.get(i);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Sequential get, randomized internal keys", time1, time2, time3, prevGCRuns);
//Test
time1 = System.nanoTime();
for (int i : random) hashMap.get(i);
time2 = System.nanoTime();
for (int i : random) linkedHashMap.get(i);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Random get, randomized internal keys", time1, time2, time3, prevGCRuns);
//Set sequential keys
hashMap = new HashMap<>();
linkedHashMap = new LinkedHashMap<>();
for (int i : sequential)
{
hashMap.put(i, 0);
linkedHashMap.put(i, 0);
}
//Attempt GC
System.gc();
prevGCRuns = 0;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) prevGCRuns += gcBean.getCollectionCount();
//Test
time1 = System.nanoTime();
for (int i : sequential) hashMap.get(i);
time2 = System.nanoTime();
for (int i : sequential) linkedHashMap.get(i);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Sequential get, sequential internal keys", time1, time2, time3, prevGCRuns);
//Test
time1 = System.nanoTime();
for (int i : random) hashMap.get(i);
time2 = System.nanoTime();
for (int i : random) linkedHashMap.get(i);
time3 = System.nanoTime();
prevGCRuns = printAndReset("Random get, sequential internal keys", time1, time2, time3, prevGCRuns);
//Test
time1 = System.nanoTime();
for (int i : hashMap.values()) ;
time2 = System.nanoTime();
for (int i : linkedHashMap.values()) ;
time3 = System.nanoTime();
prevGCRuns = printAndReset("values() iteration, sequential internal keys", time1, time2, time3, prevGCRuns);
//Set random keys
hashMap = new HashMap<>();
linkedHashMap = new LinkedHashMap<>();
for (int i : random)
{
hashMap.put(i, 0);
linkedHashMap.put(i, 0);
}
//Attempt GC
System.gc();
prevGCRuns = 0;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) prevGCRuns += gcBean.getCollectionCount();
//Test
time1 = System.nanoTime();
for (int i : hashMap.values()) ;
time2 = System.nanoTime();
for (int i : linkedHashMap.values()) ;
time3 = System.nanoTime();
prevGCRuns = printAndReset("values() iteration, randomized internal keys", time1, time2, time3, prevGCRuns);
//Test
time1 = System.nanoTime();
for (int i : hashMap.keySet()) ;
time2 = System.nanoTime();
for (int i : linkedHashMap.keySet()) ;
time3 = System.nanoTime();
prevGCRuns = printAndReset("keySet() iteration, randomized internal keys", time1, time2, time3, prevGCRuns);
//Set sequential keys
hashMap = new HashMap<>();
linkedHashMap = new LinkedHashMap<>();
for (int i : sequential)
{
hashMap.put(i, 0);
linkedHashMap.put(i, 0);
}
//Attempt GC
System.gc();
prevGCRuns = 0;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) prevGCRuns += gcBean.getCollectionCount();
//Test
time1 = System.nanoTime();
for (int i : hashMap.keySet()) ;
time2 = System.nanoTime();
for (int i : linkedHashMap.keySet()) ;
time3 = System.nanoTime();
prevGCRuns = printAndReset("keySet() iteration, sequential internal keys", time1, time2, time3, prevGCRuns);
//Test
time1 = System.nanoTime();
for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) ;
time2 = System.nanoTime();
for (Map.Entry<Integer, Integer> entry : linkedHashMap.entrySet()) ;
time3 = System.nanoTime();
prevGCRuns = printAndReset("entrySet() iteration, sequential internal keys", time1, time2, time3, prevGCRuns);
//Set random keys
hashMap = new HashMap<>();
linkedHashMap = new LinkedHashMap<>();
for (int i : random)
{
hashMap.put(i, 0);
linkedHashMap.put(i, 0);
}
//Attempt GC
System.gc();
prevGCRuns = 0;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) prevGCRuns += gcBean.getCollectionCount();
//Test
time1 = System.nanoTime();
for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) ;
time2 = System.nanoTime();
for (Map.Entry<Integer, Integer> entry : linkedHashMap.entrySet()) ;
time3 = System.nanoTime();
prevGCRuns = printAndReset("entrySet() iteration, randomized internal keys", time1, time2, time3, prevGCRuns);
}
protected static int printAndReset(String description, long time1, long time2, long time3, int prevGCRuns)
{
System.out.println(description);
System.out.println("HashMap: " + (time2 - time1) + " nanos");
System.out.println("LinkedHashMap: " + (time3 - time2) + " nanos");
int gcRuns = 0;
for (GarbageCollectorMXBean gcBean : ManagementFactory.getGarbageCollectorMXBeans()) gcRuns += gcBean.getCollectionCount();
System.out.println("GC during test: " + (gcRuns != prevGCRuns));
System.out.println();
return gcRuns;
}
public static int random(int maxvalue)
{
return (int) ((double) maxvalue * Math.random());
}
}
输出...
Put: sequential key (from 0 to 999999), no overwrites
HashMap: 30190070 nanos
LinkedHashMap: 44618672 nanos
GC during test: false
Put: random key (between 0 and 999999 inclusive), all overwrites (exactly one per entry, random order)
HashMap: 118536111 nanos
LinkedHashMap: 110828524 nanos
GC during test: false
Put: sequential key (from 0 to 999999), all overwrites (exactly one per entry, sequential order)
HashMap: 25070771 nanos
LinkedHashMap: 23569874 nanos
GC during test: false
Put: random key (between 0 and 999999 inclusive), no overwrites
HashMap: 93353708 nanos
LinkedHashMap: 106686445 nanos
GC during test: false
Sequential get, randomized internal keys
HashMap: 38817600 nanos
LinkedHashMap: 39499373 nanos
GC during test: false
Random get, randomized internal keys
HashMap: 42636179 nanos
LinkedHashMap: 51062653 nanos
GC during test: false
Sequential get, sequential internal keys
HashMap: 19986540 nanos
LinkedHashMap: 19502021 nanos
GC during test: false
Random get, sequential internal keys
HashMap: 58083205 nanos
LinkedHashMap: 59547574 nanos
GC during test: false
values() iteration, sequential internal keys
HashMap: 21284921 nanos
LinkedHashMap: 18383069 nanos
GC during test: false
values() iteration, randomized internal keys
HashMap: 19616868 nanos
LinkedHashMap: 15392964 nanos
GC during test: false
keySet() iteration, randomized internal keys
HashMap: 18054895 nanos
LinkedHashMap: 16067725 nanos
GC during test: false
keySet() iteration, sequential internal keys
HashMap: 18764430 nanos
LinkedHashMap: 18604873 nanos
GC during test: false
entrySet() iteration, sequential internal keys
HashMap: 18493825 nanos
LinkedHashMap: 18067752 nanos
GC during test: false
entrySet() iteration, randomized internal keys
HashMap: 16252707 nanos
LinkedHashMap: 13175517 nanos
GC during test: false
于 2020-09-08T12:08:55.723 回答