Java Map

In this article, we will talk about Java Map Interface which is under java.util package, how it works, and analyze its main implementations.

1. What is a Map in Java

You can imagine a Map as a Data Structure which contains Key-Value pairs. This mapping is an Entry of the Map. For example, it could contain an id of a Person, mapped by his/her name. This map would look like this (We use the HashMap implementation as it’s the most commonly used):

With regard to classes and interfaces relations, you can check the diagram below:

2. Java Map Interface Methods

In this section, we’ll go through all the methods provided by this interface.

2.1 Modification Methods

Modification methods are methods that can alter a list, either by changing an entry of the map or by removing or adding new entries.

Below you can find all of them:

For code examples of each method, you can check HashMap Java Tutorial, Sections 3.1, 3.3, 3.4.

2.2 Information and Access Methods

3. Iterating a Java HashMap

For this section, we’ll use the HashMap implementation of the Map.

3.1 Using forEach

Map interface provides the method forEach(BiConsumer<? super K,? super V> action). Here is an example of how we can iterate a map using that method:

        Map<String, String> countries = new HashMap<>();
        countries.put("Greece", "Europe");
        countries.put("Spain", "Europe");
        countries.put("Algeria", "Africa");
        countries.put("USA", "North America");
        countries.put("Brazil", "South America");

        countries.forEach((key, value) -> {
            //actions
        });

        //Another way to iterate a map using forEach, is through entrySet() method
        // But this forEach applies to a set, not a map

        //Simplest way to print the whole map
        countries.entrySet().forEach(System.out::println);

        //Doing actions for each entry, by using Map.Entry inner class
        countries.entrySet().forEach(entry -> {
            //actions e.g.
        });

3.2 Using enhanced for loop

If for any reason you don’t want to use the forEach() method, you can use the enhanced for loop.

Here is an example:

        Map<String, String> countries = new HashMap<>();
        countries.put("Greece", "Europe");
        countries.put("Spain", "Europe");
        countries.put("Algeria", "Africa");
        countries.put("USA", "North America");
        countries.put("Brazil", "South America");

        for(Map.Entry<String, String> entry : countries.entrySet()){
            //Actions
        }

        //Or you can use just the keyset method
        for(String key : countries.keySet()){
            //Actions, now using the key instead of entry
        }

        // Print the map
        for(Map.Entry<String, String> entry : countries.entrySet()){
            System.out.println(entry);
        }

4. Main Implementations of Java Map Interface

In this section, we’ll analyze the most used implementation of the map interface.

4.1 HashMap

HashMap is the most popular implementation since it is very fast with regard to inserting, removing, and accessing a mapping. It has O(1) time complexity on average, with the worst-case time complexity being O(n). You can find an in-depth analysis of this implementation here.

The characteristics of HashMap are the following:

• Key can have null value but for example, if we run map.put(null, 5) and then map.put(null, 6), the value will be 6. So null is a unique key and only one can exist in the HashMap.
• Value can be null
• Insertion order can not be guaranteed
• Time complexity of get(), put(), remove(), containsKey()
  • On Average: O(1)
  • Worst case : O(n)

4.2 LinkedHashMap

LinkedHashMap is a Linked List and Hash Table implementation of the Map interface. One of its unique characteristics is that it maintains insertion order by default, unlike TreeMap or HashMap.

The cost of maintaining the order comes at needing more space since it uses a doubly-linked list.

4.3 ConcurrentHashMap

ConcurrentHashMap is a thread-safe implementation of Hashtable(it is generally recommended not to be used unless there is a specific reason). Therefore, it should be used instead of HashMap, only in multi-threaded environments, as it will lead to better performance.

Unlike HashMap, key or value cannot be null.

4.4 TreeMap

A Treemap is a Red-Black Binary Search Tree implementation of Map. The main difference with other implementations is that it sorts the keys in ascending order by default. Of course, this can be overridden by providing a comparator when creating the treemap.

Each node contains the following information:

• Left Node
• Right Node
• Key
• Value
• Color

Below, you can find a visualization of a TreeMap<Integer, String>, a Treemap with an id as key, and a name as value.

The characteristics of this implementation are the following:

• null keys are not allowed(NullPointerException will be thrown).
• Time complexity of get(), put(), remove() and containsKey() is guaranteed to be around O(logn).
• It maintains ascending order unless it’s overriden by a Comparator.

5. Comparison of Java Map Interface Implementations

6. Conclusion

By now you should be confident when it comes to Maps in Java and which implementation should be used based on the requirements of the application you are building. You can find the source code on our GitHub page.

7. Sources

[1] : Map (Java Platform SE 8) – Oracle

[2] : HashMap (Java Platform SE 8 ) – Oracle

[3] : TreeMap (Java Platform SE 8 ) – Oracle

[4]: LinkedHashMap (Java Platform SE 8 ) – Oracle

[5]: ConcurrentHashMap (Java Platform SE 8 ) – Oracle

[6]: Binary search tree – Wikipedia

[7]: Red–black tree – Wikipedia