HashMap, TreeMap and LinkedHashMap

Java Maps — HashMap, TreeMap and LinkedHashMap

The java.util.Map interface maps keys to values. A map cannot contain duplicate keys and each key can map to at most one value.

It provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings.

The three mostly used implementations of Map in Java are HashMap, TreeMap, and LinkedHashMap :—

HashMap is implemented as a hash table, and there is no ordering on keys or values.
TreeMap is implemented based on red-black tree structure, and it is ordered by the key.
LinkedHashMap preserves the insertion order

The order of a map is defined as the order in which the iterators on the map’s collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

Nested Class of Map

Map has got a nested class, which denotes a map entry (i.e. key-value pair) :—

static interface Map.Entry<K,V>

As already mentioned, ‘K‘ denotes the key and ‘V‘ denotes the corresponding value.

Map Methods

Map defines the following methods −

Sl. No.	Method and Description
1	void clear( ) Removes all key/value pairs from the invoking map.
2	boolean containsKey (Object k) Returns true if the invoking map contains k as a key. Otherwise, returns false.
3	boolean containsValue (Object v) Returns true if the map contains v as a value. Otherwise, returns false.
4	Set entrySet( ) Returns a Set that contains the entries in the map. The set contains objects of type Map.Entry. This method provides a set-view of the invoking map.
5	boolean equals (Object obj) Returns true if obj is a Map and contains the same entries. Otherwise, returns false.
6	Object get (Object k) Returns the value associated with the key k.
7	int hashCode( ) Returns the hash code for the invoking map.
8	boolean isEmpty( ) Returns true if the invoking map is empty. Otherwise, returns false.
9	Set keySet( ) Returns a Set that contains the keys in the invoking map. This method provides a set-view of the keys in the invoking map.
10	Object put (Object k, Object v) Puts an entry in the invoking map, overwriting any previous value associated with the key. The key and value are k and v, respectively. Returns null if the key did not already exist. Otherwise, the previous value linked to the key is returned.
11	void putAll (Map m) Puts all the entries from m into this map.
12	Object remove (Object k) Removes the entry whose key equals k.
13	int size( ) Returns the number of key/value pairs in the map.
14	Collection values( ) Returns a collection containing the values in the map. This method provides a collection-view of the values in the map.

Implementing Classes of Map

Java classes HashMap, TreeMap and LinkedHashMap all implement java.util.Map interface and following are their characteristics :—

HashMap

HashMap has complexity of O(1) for insertion and lookup.
HashMap allows one null key and multiple null values.
HashMap does not maintain any order.

TreeMap

TreeMap has complexity of O(logN) for insertion and lookup.
TreeMap does not allow null key but allow multiple null values.
TreeMap maintains order. It stores keys in sorted and ascending order.

LinkedHashMap

LinkedHashMap has complexity of O(1) for insertion and lookup.
LinkedHashMap allows one null key and multiple null values.
LinkedHashMap maintains order in which key-value pairs are inserted.

Coding Example

The following program demonstrates the above mentioned implementing classes of the Map interface−

MapsDemo.java

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MapsDemo {

    public static void main(String args[]) {       
        // Create an empty HashMap object
        HashMap<Integer, String> hMap = new HashMap<>();

        System.out.println("HashMap related operations:~");
        System.out.println("==========================");
        
        // Add elements to this HashMap object
        hMap.put(60, "Friday");
        hMap.put(40, "Wednesday");
        hMap.put(30, "Tuesday");
        hMap.put(50, "Thursday");
        hMap.put(20, "Monday");
        hMap.put(70, "Saturday");
        hMap.put(10, "Sunday");
        
        System.out.println("HashMap object: " + hMap + "\n");
        
        System.out.println("HashMap key-value pairs:-> ");
        // Using nested class Map.Entry of Map interface
        for (Map.Entry<Integer, String> entry : hMap.entrySet()) {
            Integer key = entry.getKey();
            String value = entry.getValue();
            System.out.println("Key = " + key + "; Value = " + value);
        }
        System.out.println();
        
        // Create a TreeMap object using existing HashMap object
        TreeMap<Integer, String> tMap = new TreeMap<>(hMap);
        
        System.out.println("\nTreeMap related operations:~");
        System.out.println("==========================");
        
        System.out.println("TreeMap object: " + tMap + "\n");
        
        // Retrieve all keys
        System.out.println("Keys of tree map: " + tMap.keySet());
        
        // Retrieve all values
        System.out.println("Values of tree map: " + tMap.values());
        
        // Retrieve the First key and its value
        System.out.println("First key: " + tMap.firstKey()
                + " and Value: " + tMap.get(tMap.firstKey()) + "\n");

        // Remove the first key and value
        System.out.println("Removing first data: "
                + tMap.remove(tMap.firstKey()));
        System.out.println("Now the tree map Keys: " + tMap.keySet());
        System.out.println("Now the tree map contains: " + tMap.values() + "\n");
        
        // Retrieve the Last key and value
        System.out.println("Last key: " + tMap.lastKey()
                + " and Value: " + tMap.get(tMap.lastKey()) + "\n");
        
        // Remove the last key and value
        System.out.println("Removing last data: "
                + tMap.remove(tMap.lastKey()));
        System.out.println("Now the tree map Keys: " + tMap.keySet());
        System.out.println("Now the tree map contains: " + tMap.values());
        
        // Create a LinkedHashMap object using existing HashMap object
        LinkedHashMap<Integer, String> lhMap = new LinkedHashMap<>(hMap);
        
        System.out.println("\n\nLinkedHashMap related operations:~");
        System.out.println("================================");
        System.out.println("LinkedHashMap object: " + lhMap + "\n");
        
        // Search for a key in LinkedHashMap object
        Integer key = 30;
        if(lhMap.containsKey(key)) {
            System.out.println("Key " + key + " in LinkedHashMap has value " + lhMap.get(key));
        }
        else {
            System.out.println("Key " + key + " is not found!");
        }
        
        // Returns a Set view of the keys contained in this map
        Set<Integer> set = lhMap.keySet();
        System.out.println("Key Set: " + set);
    }

}

Output:

HashMap related operations:~
==========================
HashMap object: {50=Thursday, 20=Monday, 70=Saturday, 40=Wednesday, 10=Sunday, 60=Friday, 30=Tuesday}

HashMap key-value pairs:-> 
Key = 50; Value = Thursday
Key = 20; Value = Monday
Key = 70; Value = Saturday
Key = 40; Value = Wednesday
Key = 10; Value = Sunday
Key = 60; Value = Friday
Key = 30; Value = Tuesday


TreeMap related operations:~
==========================
TreeMap object: {10=Sunday, 20=Monday, 30=Tuesday, 40=Wednesday, 50=Thursday, 60=Friday, 70=Saturday}

Keys of tree map: [10, 20, 30, 40, 50, 60, 70]
Values of tree map: [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday]
First key: 10 and Value: Sunday

Removing first data: Sunday
Now the tree map Keys: [20, 30, 40, 50, 60, 70]
Now the tree map contains: [Monday, Tuesday, Wednesday, Thursday, Friday, Saturday]

Last key: 70 and Value: Saturday

Removing last data: Saturday
Now the tree map Keys: [20, 30, 40, 50, 60]
Now the tree map contains: [Monday, Tuesday, Wednesday, Thursday, Friday]


LinkedHashMap related operations:~
================================
LinkedHashMap object: {50=Thursday, 20=Monday, 70=Saturday, 40=Wednesday, 10=Sunday, 60=Friday, 30=Tuesday}

Key 30 in LinkedHashMap has value Tuesday
Key Set: [50, 20, 70, 40, 10, 60, 30]

-: NOTE :-

Here we can see that HashMap has random order of Keys, LinkedHashMap has preserved the order in which keys are inserted and TreeMap has sorted order of keys.