| |
Choosing between Maps
When choosing between implementations of Map, the size of the Map is what most strongly affects performance, and the following test program gives an indication of this trade-off:
//: c11:MapPerformance.java
// Demonstrates performance differences in Maps.
// {Args: 500}
import java.util.*;
import com.bruceeckel.util.*;
public class MapPerformance {
private static int reps = 50000;
private abstract static class Tester {
String name;
Tester(String name) { this.name = name; }
abstract void test(Map m, int size);
}
private static Tester[] tests = {
new Tester("put") {
void test(Map m, int size) {
for(int i = 0; i < reps; i++) {
m.clear();
Collections2.fill(m,
Collections2.geography.reset(), size);
}
}
},
new Tester("get") {
void test(Map m, int size) {
for(int i = 0; i < reps; i++)
for(int j = 0; j < size; j++)
m.get(Integer.toString(j));
}
},
new Tester("iteration") {
void test(Map m, int size) {
for(int i = 0; i < reps * 10; i++) {
Iterator it = m.entrySet().iterator();
while(it.hasNext())
it.next();
}
}
},
};
public static void test(Map m, int size) {
// Strip qualifiers from class name:
System.out.println("Testing " +
m.getClass().getName().replaceAll("\\w+\\.", "") +
" size " + size);
Collections2.fill(m,
Collections2.geography.reset(), size);
for(int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(m, size);
long t2 = System.currentTimeMillis();
System.out.println(": " +
((double)(t2 - t1)/(double)size));
}
}
public static void main(String[] args) {
// Choose a different number of
// repetitions via the command line:
if(args.length > 0)
reps = Integer.parseInt(args[0]);
System.out.println(reps + " repetitions");
// Small:
test(new TreeMap(), 10);
test(new HashMap(), 10);
test(new LinkedHashMap(), 10);
test(new IdentityHashMap(), 10);
test(new WeakHashMap(), 10);
test(new Hashtable(), 10);
// Medium:
test(new TreeMap(), 100);
test(new HashMap(), 100);
test(new LinkedHashMap(), 100);
test(new IdentityHashMap(), 100);
test(new WeakHashMap(), 100);
test(new Hashtable(), 100);
// Large:
test(new TreeMap(), 1000);
test(new HashMap(), 1000);
test(new LinkedHashMap(), 1000);
test(new IdentityHashMap(), 1000);
test(new WeakHashMap(), 1000);
test(new Hashtable(), 1000);
}
} ///:~
Because the size of the map is the issue, you’ll see that the timing tests divide the time by the size to normalize each measurement. Here is one set of results. (Yours will probably be different.)
|
Type
|
Test size
|
Put
|
Get
|
Iteration
|
|
10
|
26.6
|
20.3
|
43.7
|
|
TreeMap
|
100
|
34.1
|
27.2
|
45.8
|
|
1000
|
27.8
|
29.3
|
8.8
|
|
|
10
|
21.9
|
18.8
|
60.9
|
|
HashMap
|
100
|
21.9
|
18.6
|
63.3
|
|
1000
|
11.5
|
18.8
|
12.3
|
|
|
10
|
23.4
|
18.8
|
59.4
|
|
LinkedHashMap
|
100
|
24.2
|
19.5
|
47.8
|
|
1000
|
12.3
|
19.0
|
9.2
|
|
|
10
|
20.3
|
25.0
|
71.9
|
|
IdentityHashMap
|
100
|
19.7
|
25.9
|
56.7
|
|
1000
|
13.1
|
24.3
|
10.9
|
|
|
10
|
26.6
|
18.8
|
76.5
|
|
WeakHashMap
|
100
|
26.1
|
21.6
|
64.4
|
|
1000
|
14.7
|
19.2
|
12.4
|
|
|
10
|
18.8
|
18.7
|
65.7
|
|
Hashtable
|
100
|
19.4
|
20.9
|
55.3
|
|
1000
|
13.1
|
19.9
|
10.8
|
As you might expect, Hashtable performance is roughly equivalent to HashMap. (You can also see that HashMap is generally a bit faster; HashMap is intended to replace Hashtable.) The TreeMap is generally slower than the HashMap, so why would you use it? As a way to create an ordered list. The behavior of a tree is such that it’s always in order and doesn’t have to be specially sorted. Once you fill a TreeMap, you can call keySet( ) to get a Set view of the keys, then toArray( ) to produce an array of those keys. You can then use the static method Arrays.binarySearch( ) (discussed later) to rapidly find objects in your sorted array. Of course, you would probably only do this if, for some reason, the behavior of a HashMap was unacceptable, since HashMap is designed to rapidly find things. Also, you can easily create a HashMap from a TreeMap with a single object creation. In the end, when you’re using a Map, your first choice should be HashMap, and only if you need a constantly sorted Map will you need TreeMap.
LinkedHashMap is slightly slower than HashMap because it maintains the linked list in addition to the hashed data structure. IdentityHashMap has different performance because it uses == rather than equals( ) for comparisons.
|
|
