Choosing Between HashMap and TreeMap in Java

Question

How to decide whether to use HashMap or TreeMap?

Introduction

TreeMap<K,V> 's key must implement java.lang.Comparable , so iteration yields keys in ascending order; TreeMap is implemented on a red‑black tree and is suitable for traversing keys in natural or custom order.

HashMap<K,V> 's key uses hashCode() for hashing, resulting in a uniform distribution without ordering; its internal structure consists of buckets (array) whose entries are stored as linked lists or red‑black trees, making it ideal for fast insertion, deletion, and lookup.

Conclusion

If an ordered result is required, use TreeMap because HashMap does not guarantee element order; otherwise, HashMap generally offers better performance and is preferred when ordering is unnecessary.

Extended Details

1. Implementation of HashMap and TreeMap

HashMap: Based on a hash table. Keys must properly override hashCode() and equals() . Capacity and load factor can be tuned. Constructors include HashMap() , HashMap(Map m) , HashMap(int initialCapacity) , and HashMap(int initialCapacity, float loadFactor) .

HashMap(): creates an empty hash map.

HashMap(Map m): creates a hash map and adds all mappings from m.

HashMap(int initialCapacity): creates an empty hash map with the specified capacity.

HashMap(int initialCapacity, float loadFactor): creates an empty hash map with the specified capacity and load factor.

TreeMap: Based on a red‑black tree. No tuning options because the tree remains balanced. Constructors include TreeMap() , TreeMap(Map m) , TreeMap(Comparator c) , and TreeMap(SortedMap s) .

TreeMap(): creates an empty map tree.

TreeMap(Map m): creates a map tree and adds all entries from m.

TreeMap(Comparator c): creates a map tree using the provided comparator for key ordering.

TreeMap(SortedMap s): creates a map tree, adds all entries from s, and uses the same comparator as s.

2. Thread‑safety

Both HashMap and TreeMap are not thread‑safe. HashMap extends AbstractMap , while TreeMap implements the SortedMap interface.

AbstractMap: Provides default implementations of equals() and hashCode() so that two equal maps produce the same hash code, regardless of internal entry order.

SortedMap: Maintains keys in a sorted order. Implementations must ensure keys are comparable or supplied with a Comparator . TreeMap is the sole standard implementation.

3. Making TreeMap sort in descending order

Define a custom comparator that reverses the natural ordering by returning the negative result of compareTo . Example comparator:

static class MyComparator implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        // TODO Auto-generated method stub
        String param1 = (String) o1;
        String param2 = (String) o2;
        return -param1.compareTo(param2);
    }
}

Instantiate the comparator and pass it to the TreeMap constructor:

MyComparator comparator = new MyComparator();
Map
map = new TreeMap
(comparator);

Now the TreeMap will iterate keys in descending order.

public class MapTest {
    public static void main(String[] args) {
        // Initialize custom comparator
        MyComparator comparator = new MyComparator();
        // Initialize map
        Map
map = new TreeMap
(comparator);
        // Insert data
        map.put("a", "a");
        map.put("b", "b");
        map.put("f", "f");
        map.put("d", "d");
        map.put("c", "c");
        map.put("g", "g");
        // Iterate and output
        Iterator iterator = map.keySet().iterator();
        while(iterator.hasNext()){
            String key = (String)iterator.next();
            System.out.println(map.get(key));
        }
    }
    static class MyComparator implements Comparator {
        @Override
        public int compare(Object o1, Object o2) {
            // TODO Auto-generated method stub
            String param1 = (String) o1;
            String param2 = (String) o2;
            return -param1.compareTo(param2);
        }
    }
}