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 hashmap does not maintain any order. Here is a java program that demonstrates how elements are put and retrieved from treemap.
4.8 (4,382 ratings)
View Course
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 top differences between HashMap and TreeMap
Key Difference of HashMap vs TreeMap
The following are the points of Key difference HashMap and 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 Abstract Map class and implements a Navigable Map interface. The underlying data structure for 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 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 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 introduction to HashMap vs TreeMap, Differences between Hashmap and Treemap and a Comparison Table. You can also go through our other suggested articles to learn more–
