Java TreeMap vs HashMap

In this tutorial, we are going to focus on the core differences between the TreeMap and the HashMap.

TreeMap and HashMap are quite similar, both are collections that implement the Map interface. But they also have some differences that make one better than the other in some situations. Let’s look at those differences.

Table Of Contents

1. 1. Differences between HashMap and TreeMap
   • 1.1. Class Hierarchy
   • 1.2. Internal Implementations
   • 1.3. Null Keys and Values
   • 1.4. Functionality
   • 1.5. Element Ordering
   • 1.6. Performance Comparison
   • 1.7. Memory Usage
   • 1.8. Key Searches
2. 2. When to use HashMap and TreeMap
3. 3. Conclusion
4. 4. References

1.Differences between HashMap and TreeMap

Let’s discuss some of the main differences between the two maps.

1.1. Class Hierarchy

HashMap class extends AbstractMap class and implements Map interface whereas TreeMap class extends AbstractMap class and implements _NavigableMap_ interface.

// HashMap class declaration
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable

// TreeMap class declaration
public class TreeMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K, V>, Cloneable, Serializable

1.2. Internal Implementations

• HashMap internally uses HashTable and works on the principle of Hashing. It contains the buckets in the form of a LinkedList, and when there are more than 8 entries in the bucket, then the LinkedList transforms into a Balanced Tree (TreeNodes).
• TreeMap internally uses Red-Black Tree, a self-balancing Binary Search Tree.

1.3. Null Keys and Values

TreeMap doesn’t allow a null key but may contain any number of null values.

HashMap allows one null key (for other null keys, the existing value will simply be overwritten with a new value) and any number of null values.

// Putting null key in TreeMap
TreeMap<String, String> map = new TreeMap<>();

map.put(null, "value");    //Exception in thread "main" java.lang.NullPointerException

TreeMap internally uses compareTo() or compare() method from Comparable & Comparator Interfaces respectively to maintain the order of elements in the map based on the keys and in case of null key, these method throws ‘NullPointerException‘.

1.4. Functionality

TreeMap is richer in functionality as compared with HashMap. Along with the normal methods (get(), put(), remove()) of Map Interface, it contains methods from NavigableMap interface as well like pollFirstEntry(), pollLastEntry(), tailMap(), firstKey(), lastKey(), etc. which the HashMap class doesn’t have.

// Creating TreeMap
TreeMap<String, String> map = new TreeMap<>();

// Putting values in TreeMap
map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");

// Printing map
System.out.println(map);                       // Prints {key1=value1, key2=value2, key3=value3}

// Getting first key from map
System.out.println(map.firstKey());              // Prints key1
// Getting last key from map
System.out.println(map.lastKey());             // Prints key3

// Getting first entry from map
System.out.println(map.firstEntry());         // Prints key1=value1
// Polling last entry from map
System.out.println(map.pollLastEntry());       // Prints key3=value3

// Printing map again
System.out.println(map);                           // Prints {key1=value1, key2=value2}

1.5. Element Ordering

HashMap does not maintain any order for its elements i.e. it won’t provide any guarantee that the element inserted first in the map will print first during the iteration of the map.

TreeMap stores the elements in the sorting order of their keys. The sorting can be default natural sorting order (ascending order for numbers & alphabetical order for strings) or customized sorting based on the Comparator object specified during the map creation.

// Creating HashMap
HashMap<Integer, String> map = new HashMap<>();

// Putting values in the map
map.put(10, "value1");
map.put(2, "value2");
map.put(13, "value3");
map.put(5, "value4");
map.put(25, "value5");

// Printing map
System.out.println(map);   //{2=value2, 5=value4, 25=value5, 10=value1, 13=value3}  - No ordering

// Creating TreeMap using normal TreeMap() constructor which sorts the elements 
// based on natural sorting order of keys
TreeMap<Integer, String> map = new TreeMap<>();

// Putting values in map
map.put(10, "value1");
map.put(2, "value2");
map.put(13, "value3");
map.put(5, "value4");
map.put(25, "value5");

// Printing map
System.out.println(map);  //{2=value2, 5=value4, 10=value1, 13=value3, 25=value5}

​

// Creating TreeMap using TreeMap(Comparator) constructor by specifying Comparator object 
// as Lambda expression which sorts the elements according to customized sorting of keys
map = new TreeMap<Integer,String>((I1,I2) -> (I1<I2) ? 1 : (I1>I2) ? -1 : 0); 

// Putting values in map
map.put(10, "value1");
map.put(2, "value2");
map.put(13, "value3");
map.put(5, "value4");
map.put(25, "value5");

// Printing map
System.out.println(map);  //{25=value5, 13=value3, 10=value1, 5=value4, 2=value2}

1.6. Performance Comparison

• HashMap is faster than TreeMap and provides constant time performance O(1) for the most basic operations like get(), put(), contains() & remove() in the best case scenario without hash collisions.
• In case of hash collisions (two keys are having the same hashcode), HashMap handles it by using a LinkedList to store the collided elements and hence the performance reduces up to O(n) in this case.
• To improve HashMap’s performance during collisions, LinkedList transforms into a Balanced Tree in case the number of entries in a bucket are more than 8 so that it improves the worst-case performance from O(n) to O(log(n)).

On the other hand, TreeMap provides a performance of O(log(n)) for most basic operations like get(), put(), contains() & remove().

1.7. Memory Usage

TreeMap has better performance in memory management as it does not maintain an array internally to store key-value pairs.

In HashMap, the array size is determined while initialization or resizing which is often more than needed at the time. It wastes memory. There is no such problem with TreeMap.

1.8. Key Searches

HashMap uses hashCode() and equals() method while comparing the keys of the map while TreeMap uses compareTo() or compare() methods during key comparison.

// Creating HashMap
HashMap<Integer, String> hashMap = new HashMap<>();

// Putting values in map
hashMap.put(10, "value1");
hashMap.put(10, "value2");
System.out.println("HashMap: " + hashMap);

// Creating TreeMap
TreeMap<Integer, String> treeMap = new TreeMap<>();

// Putting values in map
treeMap.put(10, "value1");
treeMap.put(10, "value2");
System.out.println("TreeMap: " + treeMap);

Notice the program output. Even though the output is same for both cases, internally HashMap uses equals() while comparing the keys and rejects the second key as it is a duplicate. Whereas, TreeMap uses compareTo() while comparing keys and thus rejects the second key.

Also, both the maps update the previous entry, and a single entry is there on the Map.

HashMap: {10=value2}
TreeMap: {10=value2}

2. When to use HashMap and TreeMap

We should use TreeMap if we need to add elements (key-value pairs) in sorted order. Let’s take an example of creating a Dictionary where the words sort in alphabetical order. So we can easily implement this using a TreeMap.

A TreeMap is more memory efficient, so it is a good map implementation for us in case we are not sure of the number of elements to be stored in the memory.

HashMap is more of a general purpose map implementation and can be used where we don’t want any kind of sorting for our data, and the entries can be maintained in any order or sequence. In high-performance applications, we can prefer using HashMap over TreeMap as it performs better as compared to TreeMap.

3. Conclusion

In this post, we have seen some of the key differences between HashMap and TreeMap and on which factors we can decide between the two while using them in our code.

Happy Learning !!

4.References

• Java TreeMap vs HashMap