Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

  




 

 

Thinking in Java
Prev Contents / Index Next

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.
Thinking in Java
Prev Contents / Index Next


 
 
   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire