## 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!

Daniel Barczak is a software developer with over 9 years of professional experience. He has experience with several programming languages and technologies and has worked for businesses ranging from startups to big enterprises. Daniel in his leisure time likes to experiment with new smart home gadgets and explore the realm of home automation.

## Leave a Reply