1. Introduction
A very important data structure in programming is the Map which is used for extremely fast lookups. In this post, we will take a look at two implementations of the Map data structure in Java, the HashMap and TreeMap classes. The main difference between those two implementations is that the HashMap offers better lookup and insertion times but does not preserve the insertion order, whereas the Treemap is slower but does preserve the insertion order. We will compare the most commonly used methods and their complexity, provide code examples and measure their performance.
The technologies that we will use in the code examples are:
- Java 8
- Eclipse 4.10.0
2. Map Data Structure
The map is a data structure which maps keys to values, hence the name of it. It cannot contain duplicate keys so each key can map to at most one value. The map acts as a dictionary where if you know the key you can find the value at no time. We can find many real-world examples of the map data structure e.g. in books where you can search for a section from the table of contents or in bookstores where you can find books based on the first letter of the author of the book. The following diagram illustrates a map with key-value pairs of countries and their capitals:
The HashMap and TreeMap classes that we will see in this post reside in the java.util package and they both extend the AbstractMap class which implements the Map interface. They are part of the Java Collection Framework..
The most commonly used operations of the Map interface that we will compare for the HashMap and TreeMap classes are:
- Put key, value pair
- Remove by key
- Get value by key
- Contains key
3. HashMap
The HashMap class is the most widely used implementation of the Map interface. It permits null values and one null key and it makes no guarantees as to the order of the map. In particular, it does not guarantee that the order will remain constant over time. The implementation stores key-value pairs in a hash table, which is an array of linked list, also called buckets. The hash table uses a hash function to compute an index of the key and store the value into the appropriate bucket. The hash function should be implemented in a way to disperse the elements properly among the buckets otherwise the lookups will be slow. When the number of elements in the hash table exceeds a specific capacity, then the hash table grows and is rehashed. To achieve better performance in a HashMap we should know the initial size of the map and provide it to the constructor.
Custom Implementation
Below we create our own custom implementation of a HashMap that stores the key-value pairs in an array of linked list entries.
MyHashMap.java
public class MyHashMap {
private final int INITIAL_SIZE = 10;
private Entry[] buckets;
public MyHashMap() {
buckets = new Entry[INITIAL_SIZE];
}
public void put(String key, String value) {
int index = hash(key);
Entry entry = new Entry();
entry.key = key;
entry.value = value;
if (buckets[index] == null) {
buckets[index] = entry;
} else {
Entry curEntry = buckets[index];
while (curEntry.next != null) {
curEntry = curEntry.next;
}
curEntry.next = entry;
}
}
public boolean remove(String key) {
int index = hash(key);
if (buckets[index] != null) {
Entry curEntry = buckets[index];
// found in first entry
if (curEntry.key == key) {
buckets[index] = curEntry.next;
return true;
}
while (curEntry.next != null) {
if (curEntry.next.key == key) {
curEntry.next = curEntry.next.next;
return true;
}
}
}
return false;
}
public String get(String key) {
int index = hash(key);
if (buckets[index] != null) {
Entry curEntry = buckets[index];
while (curEntry != null) {
if (curEntry.key == key) {
return curEntry.value;
}
curEntry = curEntry.next;
}
}
return null;
}
public boolean containsKey(String key) {
int index = hash(key);
if (buckets[index] != null) {
Entry curEntry = buckets[index];
while (curEntry != null) {
if (curEntry.key == key) {
return true;
}
curEntry = curEntry.next;
}
}
return false;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
Entry curEntry = buckets[i];
builder.append("[Index_" + i + "=");
while (curEntry != null) {
builder.append(curEntry.key + ":" + curEntry.value + ",");
curEntry = curEntry.next;
}
// removes last comma
builder.replace(builder.length()-1, builder.length(), "");
builder.append("],");
}
}
builder.replace(builder.length()-1, builder.length(), "");
return builder.toString();
}
// Hash function
private int hash(String key) {
return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);
}
class Entry {
private String key;
private String value;
private Entry next;
}
public static void main(String[] args) {
MyHashMap roleSalary = new MyHashMap();
roleSalary.put("Senior", "50000");
roleSalary.put("Junior", "30000");
roleSalary.put("Architect", "80000");
roleSalary.put("CTO", "100000");
System.out.println("Initial map: " + roleSalary);
System.out.println("The salary of the CTO is: " + (roleSalary.containsKey("CTO") ? roleSalary.get("CTO") : "Uknown"));
System.out.println("The salary of the CEO is: " + (roleSalary.containsKey("CEO") ? roleSalary.get("CEO") : "Uknown"));
System.out.println("Removing the salary of Junior: " + roleSalary.remove("Junior"));
System.out.println("Removing the salary of the CEO: " + roleSalary.remove("CEO"));
System.out.println("Map after removals: " + roleSalary);
}
}
In the above class, we provide a very basic implementation of the HashMap and the put(String key, String value), remove(String key), get(String key) and containsKey(String key) methods. The HashMap uses under the hood the buckets which is an array of singly linkedlist nodes, the Entry objects. The most important method of this class is the hash(String key) method, which calculates the index of the key and stores the Entry object into the appropriate bucket. In this implementation, for simplicity, we do not provide any bucket resize and rehashing. Let’s run the main method which invokes all those methods and see the output.
Output
Initial map: [Index_0=CTO:100000],[Index_2=Senior:50000],[Index_5=Junior:30000,Architect:80000] The salary of the CTO is: 100000 The salary of the CEO is: Uknown Removing the salary of Junior: true Removing the salary of the CEO: false Map after removals: [Index_0=CTO:100000],[Index_2=Senior:50000],[Index_5=Architect:80000]
In the above output, we initially print the HashMap and we specify in which index each linked list belongs to. Then we call the get(String key) method for an existing and a non-existing key. After that, we remove one existing and one non-existing key from the map and finally we print the map again which results in a different output.
4. TreeMap
The TreeMap class is a Red-Black tree based implementation, which is a self-balancing Binary Search Tree. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
Example
Below we provide an example of how to create a TreeMap using a Comparator.
JavaTreeMap.java
public class JavaTreeMap {
static Comparator comparator = new Comparator() {
@Override
public int compare(Role r1, Role r2) {
return r1.hierarchy - r2.hierarchy;
}
};
public static void main(String[] args) {
TreeMap roleSalary = new TreeMap(comparator);
roleSalary.put(new Role(3, "Senior"), 50000);
roleSalary.put(new Role(4, "Junior"), 30000);
roleSalary.put(new Role(2, "Architect"), 80000);
roleSalary.put(new Role(1, "CTO"), 100000);
System.out.println(roleSalary);
}
}
class Role {
int hierarchy;
String name;
public Role(int hierarchy, String name) {
this.hierarchy = hierarchy;
this.name = name;
}
@Override
public String toString() {
return "[" + hierarchy + ":" + name + "]";
}
}
In the above example, we create a Comparator which sorts the Role objects based on the hierarchy field and then we randomly add items in the TreeMap object. Let’s run the main method and see the output.
Output
{[1:CTO]=100000, [2:Architect]=80000, [3:Senior]=50000, [4:Junior]=30000}
In the above output, the objects that we randomly added in the TreeMap are indeed sorted.
5. Methods Comparison
The HashMap provides O(1) constant time when putting, removing and getting entries from the map. When the HashMap requires rehashing then the put method takes O(n) time. It is very important to provide hash functions which disperse the elements properly among the buckets, otherwise, the get operation will run worst-case in O(n) time, as it would have to loop big linked lists. On the other hand, the TreeMap provides O(logn) time for all those methods, as it uses a Red-Black tree under the hood.
The following table display the complexity of the methods we examined before:
| Put key, value pair | Remove by key | Get value by key | Contains key | |
| HashMap | O(1) | O(1) | O(1) | O(1) |
| TreeMap | O(logn) | O(logn) | O(logn) | O(logn) |
6. Performance Comparison
It’s time to measure the performance of the methods we saw in the previous examples. To do that, we use the methods of the HashMap and TreeMap classes provided by Java and we invoke the methods for both classes. The below class demonstrates that:
PerformanceComparison.java
public class PerformanceComparison {
static final int COUNT = 1000000;
public static void main(String[] args) {
System.out.println("*** HashMap Performance ***");
performanceRun(new HashMap(COUNT));
System.out.println("\n*** TreeMap Performance ***");
performanceRun(new TreeMap());
}
static void performanceRun(Map map) {
// warm up
for (int i = COUNT; i >= 0; i--) {
map.put(i, i * 10);
}
// put
long now = System.currentTimeMillis();
for (int i = COUNT; i >= 0; i--) {
map.put(i, i * 10);
}
System.out.println("Put took: " + (System.currentTimeMillis() - now) + " ms");
// get
now = System.currentTimeMillis();
for (int i = COUNT; i >= 0; i--) {
map.get(i);
}
System.out.println("Get took: " + (System.currentTimeMillis() - now) + " ms");
// containsKey
now = System.currentTimeMillis();
for (int i = 0; i = 0; i--) {
map.remove(i);
}
System.out.println("Remove took: " + (System.currentTimeMillis() - now) + " ms");
}
}
In the above class, we initialise a new HashMap and TreeMap objects and we add 1 million elements. Then we invoke the put(String key, String value), get(String key), containsKey(String) and remove(String key) methods and print the time each operation takes. Let’s see the output and verify the time complexity of the methods.
Output
*** HashMap Performance *** Put took: 39 ms Get took: 33 ms Contains took: 105 ms Remove took: 29 ms *** TreeMap Performance *** Put took: 173 ms Get took: 133 ms Contains took: 128 ms Remove took: 219 ms
In the above output, we confirm that all the methods of the HashMap are faster than the TreeMap as far as time complexity is concerned.
7. When to use HashMap vs TreeMap
The HashMap and TreeMap classes should be used in different use cases as they provide different memory consumption, performance and functionality.
We should choose a HashMap when we:
- Don’t want to preserve the insertion order
- Want to achieve better performance over memory allocation
- Know exactly how many items we need in the map, so as to avoid rehashing
- Implement hash function to disperse the items properly among the buckets, otherwise the get method will be slow
We should choose a TreeMap when we:
- Want to preserve the insertion order
- Don’t know how many items we need in the map
- Can accept a O(logn) time in get, put, remove and containsKey methods
- Don’t want to allocate too much memory
8. Equals & HashCode
The equals and hashCode methods that every class extends from the root Object class are very important when it comes to maps. The contract between equals and hashCode, is that if two objects are equal, then they must have the same hash code, however, the opposite is not always true. The hashCode method should have an implementation which disperses the elements properly among the buckets. Let’s see below an example of a good and a bad implementation of the hashCode method and compare the times for the put and get operations.
EqualsHashcodeComparison.java
public class EqualsHashcodeComparison {
static final int COUNT = 10000;
public static void main(String[] args) {
Map map1 = new HashMap();
Map map2 = new HashMap();
System.out.println("*** GoodHashcode Performance ***");
long now = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
map1.put(new GoodHashcode(i), i);
}
System.out.println("Put took: " + (System.currentTimeMillis() - now));
now = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
map1.get(new GoodHashcode(i));
}
System.out.println("Get took: " + (System.currentTimeMillis() - now));
System.out.println("\n*** GoodHashcode Performance ***");
now = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
map2.put(new BadHashcode(i), i);
}
System.out.println("Put took: " + (System.currentTimeMillis() - now));
now = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
map2.get(new BadHashcode(i));
}
System.out.println("Get took: " + (System.currentTimeMillis() - now));
}
}
class GoodHashcode {
int id;
GoodHashcode(int id) {
this.id = id;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
GoodHashcode other = (GoodHashcode) obj;
if (id != other.id) {
return false;
}
return true;
}
}
class BadHashcode {
int id;
BadHashcode(int id) {
this.id = id;
}
@Override
public int hashCode() {
return 10; // DON'T DO THAT !!!
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
BadHashcode other = (BadHashcode) obj;
if (id != other.id) {
return false;
}
return true;
}
}
In the above example, we create the GoodHashcode class which has a good implementation of the hashCode method as it uses the id which is a unique number. Additionally, we create the BadHashcode class which has a bad implementation of the hashCode method as returns the same number for any object created. That would put all the objects in the same bucket and it would create a big linked list. Let’s run the main method and see the time it takes to put and get all the items of the two maps.
Output
*** GoodHashcode Performance *** Put took: 7 Get took: 5 *** GoodHashcode Performance *** Put took: 1081 Get took: 1097
From the above output, we confirm that a good and a bad implementation of the hashCode method result in a huge difference in time complexity.
9. Synchronization
The HashMap and TreeMap classes are not synchronized and should not be used in a multi-threading program. If multiple threads access the lists concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array. In order to synchronize both classes, we can use the Collections.synchronizedMap(map) method. This is best done at creation time, to prevent accidental unsynchronized access to the map.
10. Conclusion
In this post, we compared the most commonly used methods of the HashMap and TreeMap and provided code examples. We measured the time complexity and performance of those methods and saw that as best practice we should avoid using those classes in a multi-threading environment. We also took a look at the importance of the equals and hashCode methods for any map implementation.
11. Download the Eclipse project
You can download the full source code of the above examples here: Java HashMap vs TreeMap Example
HashMap Remove by key, Get value by key and Contains key are O(n), not O(1).