TreeMap or HashMap faster

Question

I am writing an dictionary that make heavily use of String as key in Map<String, Index>. What I concern is which one of HashMap and TreeMap will result in better (faster) performance in searching a key in the map?

Answer 1

Given that there are not many collissions hashmaps will give you o(1) performance (with a lot of colissions this can degrade to potentially O(n) where N is the number of entries (colissions) in any single bucket). TreeMaps on the other hand are used if you want to have some sort of balanced tree structure which yields O(logN) retrieval. So it really depends on your particular use-case. But if you just want to access elements, irrespective of their order use HashMap

Answer 2

public class MapsInvestigation {

public static HashMap<String, String> hashMap = new HashMap<String, String>();
public static TreeMap<String, String> treeMap = new TreeMap<String, String>();
public static ArrayList<String> list = new ArrayList<String>();

static {
    for (int i = 0; i < 10000; i++) {
        list.add(Integer.toString(i, 16));
    }
}


public static void main(String[] args) {
    System.out.println("Warmup populate");
    for (int i = 0; i < 1000; i++) {
        populateSet(hashMap);
        populateSet(treeMap);
    }
    measureTimeToPopulate(hashMap, "HashMap", 1000);
    measureTimeToPopulate(treeMap, "TreeMap", 1000);

    System.out.println("Warmup get");
    for (int i = 0; i < 1000; i++) {
        get(hashMap);
        get(treeMap);
    }
    measureTimeToContains(hashMap, "HashMap", 1000);
    measureTimeToContains(treeMap, "TreeMap", 1000);

}

private static void get(Map<String, String> map) {
    for (String s : list) {
        map.get(s);
    }

}

private static void populateSet(Map<String, String> map) {
    map.clear();
    for (String s : list) {
        map.put(s, s);
    }

}


private static void measureTimeToPopulate(Map<String, String> map, String setName, int reps) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < reps; i++) {
        populateSet(map);
    }
    long finish = System.currentTimeMillis();
    System.out.println("Time to populate " + (reps * map.size()) + " entries in a " + setName + ": " + (finish - start));
}

private static void measureTimeToContains(Map<String, String> map, String setName, int reps) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < reps; i++) {
        get(map);
    }
    long finish = System.currentTimeMillis();
    System.out.println("Time to get() " + (reps * map.size()) + " entries in a " + setName + ": " + (finish - start));
}
}

Gives these results:

Warmup populate
Time to populate 10000000 entries in a HashMap: 230
Time to populate 10000000 entries in a TreeMap: 1995
Warmup get
Time to get() 10000000 entries in a HashMap: 140
Time to get() 10000000 entries in a TreeMap: 1164

Answer 3

HashMap is O(1) (usually) for access; TreeMap is O(log n) (guaranteed).

This assumes that your key objects are immutable and have properly written equals and hashCode methods. See Joshua Bloch's "Effective Java" chapter 3 for how to override equals and hashCode correctly.

Answer 4

a HashMap is O(1) average, so it is supposed to be faster, and for large maps will probably have better throughput.
However, a HashMap requires rehashing when Load Balance become too high. rehashing is O(n), so at any time of the program's life, you may suffer unexpectedly performance loss due to rehash, which might be critical in some apps [high latency]. So think twice before using HashMap if latency is an issue!

a HashMap is also vulnerable to poor hashing functions, which might cause O(n), if many items in use are hashed into the same place.

Answer 5

HashMap is faster. However if you would often need to process your dictionary in alphabetical order, you would be better off with the TreeMap since you would otherwise need to sort all your words every time you need to process them in alphabetical order.

For your application HashMap is the better choice since I doubt you will need the alphabetically sorted list often, if ever.