Differences in a HashMap, LinkedHashMap and TreeMap

1. Introduction

Have you ever wondered about the differences between a HashMap, LinkedHashMap and TreeMap? While each choice will have pros and cons, it’s essential to understand how these three map implementations are truly different so you can pick the one that best suits your needs. So let’s dive into the nitty gritty details of every aspect, from insertion order to performance.

---

2. Overview of Map Implementations

Let’s compare and contrast HashMap, LinkedHashMap, and TreeMap, three Java Map implementations. These implementations support insertion, deletion, retrieval, and key-value pair storage.

HashMap does not support iteration order. The order changes during the element insertion. LinkedHashMap, on the other hand, will keep the insertion order by default, but it can also provide access order, so the least recent elements are accessed first. Finally, the TreeMap sorts the elements according to the natural order according to the supplied comparator or the compareTo method.

2.1. HashMap

The most straightforward Map interface implementation is a hash map that store key-value pairs in a hash table, enabling quick insertion, deletion, and lookup. These operations have an O(1) time complexity on average.

One null key and numerous null values are permitted in a hash map. It does not, however, keep the entries in any particular order, either based on insertion or based on keys.

Here is a straightforward illustration showing how to use HashMap:

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {

        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        System.out.println("HashMap: " + map);
    }
}

2.2. LinkedHashMap

A LinkedHashMap is a subclass of HashMap that maintains the order of entries based on the order they were inserted or in the order they were last accessed. It can be initialized by specifying the order type in the constructor. LinkedHashMap allows one null key and multiple null values as well.

Here is an example demonstrating the usage of LinkedHashMap:

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {

        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        System.out.println("LinkedHashMap: " + map);
    }
}

2.3. TreeMap

An implementation of a sorted map based on a red-black tree data structure is called a TreeMap. It supports lookup and insertion complexity in O(log N) time. It is appropriate for situations where sorted operations or key-ordered iterations are necessary since it retains the order of the entries depending on their keys. TreeMap does not support null keys, in contrast to HashMap and LinkedHashMap. It can, however, have more than one null value.

Here is a usage case for TreeMap:

import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {

        Map<String, Integer> map = new TreeMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        System.out.println("TreeMap: " + map);
    }
}

3. Data Structures Key Characteristics

3.1. Null Key and Values

HashMap, LinkedHashMap, and TreeMap all provide different methods for managing null keys and values in Java. Selecting the best implementation for your data structure requires understanding these distinctions.

HashMap: A single null key and many null values can be stored in a hash map. This is made possible by the hash table data structure, which treats the null key as a particular case.
LinkedHashMap: Like HashMap, LinkedHashMap allows us to store both a single null key and numerous null values.
TreeMap: TreeMap forbids null keys, in contrast to HashMap and LinkedHashMap. It can, however, hold numerous null values. A NullPointerException will be thrown if a null key is attempted to be inserted into a TreeMap.

3.2. Insertion Order and Maintenance

Another important consideration when deciding between HashMap, LinkedHashMap, and TreeMap is the retention of element order.

HashMap: Insertion order is not preserved in this hash map implementation. There is no assurance that the keys or values will be iterated in any particular sequence.
LinkedHashMap: Key order is maintained in LinkedHashMap based on insertion order, as the name suggests. The entries are stored in a doubly-linked list, which enables this.
TreeMap: TreeMap offers sorted order based on the keys but does not preserve insertion order. The red-black tree structure is used to keep order.

3.3. Key Ordering

When choosing an exemplary implementation, it’s crucial to consider the keys’ order.

HashMap: A hash map’s keys and values can appear in any order.
LinkedHashMap: The keys have no natural, alphabetical, or numerical ordering. However, they are arranged according to their insertion order.
TreeMap: During the instantiation of the TreeMap, the keys are arranged according to their inherent order or by the specified comparator.

Here is an example of each data structure implementation in Java:

HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("Three", 3);
hashMap.put("One", 1);
hashMap.put("Two", 2);

LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("Three", 3);
linkedHashMap.put("One", 1);
linkedHashMap.put("Two", 2);

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Three", 3);
treeMap.put("One", 1);
treeMap.put("Two", 2);

Output:

HashMap: {One=1, Two=2, Three=3}
LinkedHashMap: {Three=3, One=1, Two=2}
TreeMap: {One=1, Three=3, Two=2}

4. Underlying Data Structures

HashMap is a famous data structure in Java based on the idea of a hash table. Thanks to this, key-value pairs may be effectively stored and retrieved, and both the keys and the values can be of any kind. A hash table is the primary data storage method a hash map employs. With constant-time O(1) retrieval and storage, a hash function converts the key into an array index.

However, hash collisions can happen, leading to a more extended search or insertion time that, in the worst case, degrades to O(n). Since HashMap is not synchronised, it is not, by default, thread-safe. When you require a thread-safe implementation, think about utilising ConcurrentHashMap.

4.1. LinkedLists in LinkedHashMap

Since LinkedHashMap preserves the insertion order of its members, it is appropriate for situations where order is crucial. It accomplishes this by connecting the nodes in the order they are introduced using a doubly-linked list. As a result of its effective utilisation of the linked list data structure, LinkedHashMap provides O(1) time complexity for both insertion and retrieval operations.

4.2. Red-Black Tree in TreeMap

TreeMap is a sorted data structure that stores its items in ascending order according to their keys, unlike HashMap and LinkedHashMap. This sorted structure is kept up-to-date, and a balanced tree is ensured using a Red-Black Tree. Red-Black Trees are self-balancing binary search trees where each node has an extra bit to indicate whether it is red or black. These trees provide O(log n) time complexity for insertion, deletion, and retrieval operations by following particular rules that guarantee tree height remains logarithmic.

5. Comparing Time Complexity

Let’s compare the time complexity of HashMap, LinkedHashMap, and TreeMap in Java for insertion, deletion, and lookup processes.

5.1. Insertion Performance

The speed at which data may be inserted into these data structures is called insertion performance. Their corresponding temporal complexity is as follows:

HashMap:  O(1) average case, O(n) in the worst case (when the hashing function produces many collisions)
LinkedHashMap: Similar to HashMap, LinkedHashMap has O(1) average case and O(n) worst case.
TreeMap: TreeMap uses a balanced Red-Black Tree, which results in a time complexity of O(log(n)) for insertion operations.

5.2. Deletion Performance

Deletion performance refers to how quickly an entry can be removed from these data structures. Here are their respective time complexities:

HashMap:   O(1) average case, O(n) in the worst case (like insertion)
LinkedHashMap: Similar to HashMap, LinkedHashMap has O(1) average case and O(n) worst case for deletion.
TreeMap: TreeMap uses a balanced Red-Black Tree, which results in a time complexity of O(log(n)) for insertion operations.

5.3. Lookup Performance

The speed at which an entry can be retrieved from these data structures is called lookup performance. Their corresponding temporal complexity is as follows:

HashMap:   O(1) average case, O(n) in the worst case (like insertion and deletion)
LinkedHashMap: LinkedHashMap has O(1) average case and O(n) worst case for lookup, just like HashMap.
TreeMap: TreeMap provides O(log(n)) lookup time, as it utilizes a balanced Red-Black Tree for its implementation.

6. Comparing Space Complexity

The key-value pairs are stored in a hash table, making HashMap the option with the best memory use out of the three. The trade-off for this efficiency is that the stored entries are not kept in any particular sequence.

When iterating over elements, LinkedHashMap improves on HashMap by maintaining the order in which the key-value pairs are inserted. The drawback is that it uses more memory than a straightforward HashMap because of the additional complexity of storing a doubly-linked list.

The implementation of TreeMap, on the other hand, uses a Red-Black tree. It is adequate for tasks that demand sorted entries since it arranges the items according to their keys. As a result, TreeMap uses more memory than HashMap and LinkedHashMap do.

7. Concurrency and Synchronization

It’s crucial to guarantee adequate resource synchronisation while working with data structures in a multi-threaded environment. Java’s HashMap, LinkedHashMap, and TreeMap all offer varying degrees of concurrent access capability.

Since HashMap is not synchronised, it is accessible by numerous threads at once. As a result, it operates more quickly in situations with only one thread. However, we can generate a synchronised version of it using the Collections.synchronizedMap() function if we need to use it in a multi-threaded environment:

Map<String, Integer> synchronizedHashMap = 
    Collections.synchronizedMap(new HashMap<>());

Additionally, LinkedHashMap does not come with built-in synchronisation. We need to employ the same Collections.synchronizedMap() method as was shown for HashMap to use it in a multi-threaded setting.

Lastly, in TreeMap, we must enclose it in a synchronized map to enable synchronised access in a multi-threaded environment:

Map<String, Integer> synchronizedTreeMap = 
    Collections.synchronizedSortedMap(new TreeMap<>());

7.1. Thread-Safe Considerations

These data structures can be synchronised using the Collections.synchronizedMap() function, although the resulting Maps are not completely thread-safe. These Maps only offer synchronised access for single operations; compound actions, such as if (map.containsKey(key)) doSomething();, are still subject to race problems.

ConcurrentHashMap is a superior substitute for total thread-safe access. Compared to HashMap and other data structures, it offers better performance and thread safety because it is created explicitly for multi-threaded environments:

Map<String, Integer> concurrentHashMap = new ConcurrentHashMap<>();

In conclusion, while HashMap, LinkedHashMap, and TreeMap don’t have built-in synchronisation, we must use Collections.synchronizedMap( to implement concurrency or choose ConcurrentHashMap for a faster, thread-safe data structure. Recognise the restrictions of synchronizedMap() and select the ideal data structure for our particular needs in a multi-threaded setting.

---

8. Summary

This article has looked at differences in HashMap, LinkedHashMap and TreeMap. If you need a map with no particular preference for order, HashMap is your go-to option. But if speed’s not of the essence and an orderly arrangement matters, LinkedHashMap or TreeMap could be more suitable choices!