HashMap vs TreeMap

Differences Between HashMap and TreeMap

HashMap has been part of Java’s collection. It provides the basic implementation of the Java Map Interface. The data is stored in (Key, Value) pairs. You need to know its key to access a value. HashMap is known as the HashMap because it uses the Hashing technique. TreeMap is used to implement the Map Interface and NavigableMap with the Abstract Class. The map is sorted by the natural order of its keys or by the comparator provided at the time of the creation of the map, depending on which constructor it is used.

Similarities Between HashMap and TreeMap

Apart from the differences, there are the following similarities between hashmap and treemap:

• Both HashMap and TreeMap classes implement Serializable and Cloneable interfaces.
• Both HashMap and TreeMap extend AbstractMap<K, V> class.
• Both HashMap and TreeMap classes operate on key-value pairs.
• Both HashMap and TreeMap are non – synchronized collections.
• Both HashMap and TreeMap are failing fast collections.

Both implementations are a part of the collection framework and store data in Key-value pairs.

Java Program Showing HashMap and TreeMap

Here is a java program that demonstrates how elements are put and retrieved from hashmap:

package com.edubca.map;
import java.util.*;
class HashMapDemo
{
// This function prints frequencies of all elements
static void printFrequency(int arr[])
{
// Create an empty HashMap
HashMap <Integer, Integer> hashmap =
new HashMap <Integer, Integer>();
// Iterate through the given array
for (int i = 0; i < arr.length; i++)
{
Integer value = hashmap.get(arr[i]);
// If first occurrence of the element
if (hashmap.get(arr[i]) == null)
hashmap.put(arr[i], 1);
// If elements already present in hash map
else
hashmap.put(arr[i], ++value);
}
// Print result
for (Map.Entry m:hashmap.entrySet())
System.out.println("Frequency of " + m.getKey() +
" is " + m.getValue());
}
// Main method to test the above method
public static void main (String[] args)
{
int arr[] = {10, 40, 5, 12, 5, 7, 10};
printFrequency(arr);
}
}

Output:

From the output, it is clear that the hashmap does not maintain any order. Here is a java program that demonstrates how elements are put and retrieved from treemap.

Code:

package com.edubca.map;
import java.util.*;
class TreeMapDemo
{
// This function prints frequencies of all elements
static void printFrequency(int arr[])
{
// Create an empty HashMap
TreeMap <Integer, Integer> treemap =
new TreeMap <Integer, Integer>();
// Iterate through the given array
for (int i = 0; i < arr.length; i++)
{
Integer value = treemap.get(arr[i]);
// If first occurrence of element
if (treemap.get(arr[i]) == null)
treemap.put(arr[i], 1);
// If elements already present in hash map
else
treemap.put(arr[i], ++value);
}
// Print result
for (Map.Entry m: treemap.entrySet())
System.out.println("Frequency of " + m.getKey() +
" is " + m.getValue());
}
// Main method to test above method
public static void main (String[] args)
{
int arr[] = {10, 40, 5, 12, 5, 7, 10};
printFrequency(arr);
}
}

Output:

From the output, it is observed that keys are sorted in a natural order. Hence Treemap maintains sorted order.

Head to Head differences between HashMap and TreeMap(Infographics)

Given below are the top differences between HashMap vs TreeMap.

Key Difference between HashMap and TreeMap

The following are the points of  Key difference between HashMap vs TreeMap:

1. Structure and Implementation

Hash Map is a hash table-based implementation. It extends the Abstract Map class and implements the Map interface. A Hash Map works on the principle of hashing. The Map implementation acts as a bucketed hash table, but when buckets get too large in size, they get converted into Tree nodes, each having a similar structure to the nodes of TreeMap. TreeMap extends the Abstract Map class and implements a Navigable Map interface. The underlying data structure for the treemap is a Red-Black tree.

2. Iteration Order

The Iteration order of Hash Map is undefined, whereas elements of a TreeMap are ordered in natural order or in a custom order specified using a comparator.

3. Performance

As Hashmap is a hashtable based implementation, it provides constant-time performance that is equal to O (1) for most of the common operations. The time required to search an element in a hash map is O (1). But if there is an improper implementation in hashmap, then this may lead to additional memory overhead and performance degradation. On the other hand, TreeMap provides a performance of O (log (n)). Since hashmap is hashtable based, it requires a contiguous range of memory, whereas a treemap uses only the amount of memory required to hold items. Hence HashMap is more time-efficient than treemap, but treemap is more space-efficient than HashMap.

4. Null Handling

HashMap allows almost one null key and many null values, whereas, in a treemap, null cannot be used as a key, although null values are allowed. If null is uses as a key in hashmap, it will throw a null pointer exception because it internally uses compare or compareTo method for sorting elements.

Comparison of Table

Here is a comparison table showing differences between hashmap and treemap:

Basis of Comparison	HashMap	TreeMap
Syntax	public class HashMap extends AbstractMap implements Map, Cloneable, Serializable	public class TreeMap extends AbstractMap implementsNavigableMap, Cloneable, Serializable
Ordering	HashMap does not provide any order for elements.	Elements are ordered in a natural or customized order.
Speed	Fast	Slow
Null Keys and Values	Allows almost one key as null and multiple null values.	It doesn’t allow null as key but allows multiple null values.
Memory Consumption	HashMap consumes more memory because of the underlying Hash Table.	Consumes less memory in comparison to HashMap.
Functionality	Provides only basic features	It provides richer features.
Comparison Method Used	Basically uses the equals () method to compare keys.	Uses compare () or compareTo () method to compare keys.
Interface Implemented	Map, Serializable and Cloneable	Navigable Map, Serializable and Cloneable
Performance	Gives a performance of O (1).	Provides performance of O (log n)
Data Structure	Uses the hash table as a data structure.	Makes use of Red-Black Tree for data storage.
Homogenous and Heterogeneous elements	It allows homogenous as well as heterogeneous elements because it does not perform any sorting.	It allows only homogenous elements as it performs sorting.
Use Cases	Used when we do not require key-value pairs in sorted order.	Used when key-value pairs of a map are required to be sorted.

Conclusion

From the article, it is concluded that hashmap is a general-purpose implementation of the Map interface. It provides the performance of O (1), whereas Treemap provides a performance of O (log (n)). Hence HashMap is usually faster than TreeMap.

Recommended Articles

This is a guide to HashMap vs TreeMap. Here we discuss the key differences between Hashmap and Treemap and a Comparison Table. You can also go through our other suggested articles to learn more–

1. List vs Set
2. Git Fetch vs Git Pull
3. Kafka vs Spark
4. Kafka vs Kinesis