Map

• Its an interface and its implementations are

  • HashMap: Do not maintains the order.

  • HashTable: Synchronized version of HashMap

  • LinkedHashMap: Maintains the insertion order.

  • TreeMap: sorts the data internally.

• Object that maps key to values.

• Cannot contain duplicate key.

Methods available in Map interface

Entry sub-interface

Entry is the sub-interface of the Map. So, its accessed via Map.Entry

HashMap

• Can store null key or value (HashTable do not contains null key or value)

• Hash Map do not maintiains the insertion order.

• Its not thread safe (instead use ConcurrentHashMap or HashTable for thread safe HashMap implementation)

Example

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> rollNumberVsNameMap = new HashMap<>();
        rollNumberVsNameMap.put(null, "TEST");
        rollNumberVsNameMap.put(0,null);
        rollNumberVsNameMap.put(1, "A");
        rollNumberVsNameMap.put(2,"B");

        //compute if present
        rollNumberVsNameMap.putIfAbsent(null, "test");
        rollNumberVsNameMap.putIfAbsent(0, "ZERO");
        rollNumberVsNameMap.putIfAbsent(3, "C");

        for (Map.Entry<Integer, String> entryMap : rollNumberVsNameMap.entrySet()){
            Integer key = entryMap.getKey();
            String value = entryMap.getValue();
            System.out.println("Key: "+key+ " value: "+ value);
        }

        //isEmpty
        System.out.println("isEmpty(): "+ rollNumberVsNameMap.isEmpty());

        //size
        System.out.println("size: " + rollNumberVsNameMap.size());

        //containsKey
        System.out.println("containsKey(3): "+ rollNumberVsNameMap.containsKey(3));

        //get(key)
        System.out.println("get(1): "+rollNumberVsNameMap.get(1));

        //getOrDefault(key)
        System.out.println("get(9): "+ rollNumberVsNameMap.getOrDefault(9, "default value"));

        //remove(key)
        System.out.println("remove(null): "+ rollNumberVsNameMap.remove(null));

        //keySet()
        for (Integer key: rollNumberVsNameMap.keySet()){
            System.out.println("key: "+ key);
        }

        //values()
        Collection<String> values = rollNumberVsNameMap.values();
        for (String value: values){
            System.out.println("value: "+value);
        }
    }
}

Key: null value: TEST
Key: 0 value: ZERO
Key: 1 value: A
Key: 2 value: B
Key: 3 value: C
isEmpty(): false
size: 5
containsKey(3): true
get(1): A
get(9): default value
remove(null): TEST
key: 0
key: 1
key: 2
key: 3
value: ZERO
value: A
value: B
value: C

Design of HashMap

Entry<K,V>

• Inside Map there is a sub interface called Entry<K,V>

• HashMap has Node<K,V> which implements Map.Entry<K,V>

• By default initial capacity of HashMap is 16 entries

Working

There are 3 main steps involved in using a HashMap:

• Hashing: We compute the hash code for a particular key. There are many hashing algorithms like MD5 and SHA-256. We use these hash(key) functions to generate the hash code.

• Indexing (Modulo): To get the index, we perform a modulo operation.

  index=hash(key) % table_size

• Collision Handling: If an element is already present at index iii, the system checks whether the existing key and the supplied key are the same. If they are the same, the value is updated. If they are different, a new node is created next to the existing node at index iii. The existing node at index iii will then point to the newly created node, forming a linked list.

Let's assume that the initial capacity of the HashMap given by the user is 3.

1. put(1, "SJ")

   hash(1)=1234567

   index=1234567%3=1(Assuming)

2. put(5, "PJ")

   hash(5)=982410

   index=hash(5)%3=2 (Assuming)

3. put(10, "KJ")

   hash(10)=515100

   index=515100%3=1 (Assuming)

   Collision: If an element is already present at index 1, the system checks whether the existing key and the supplied key are the same. If they are the same, the value is updated. Otherwise, a new node is created next to the existing node at index 1. The existing node at index 1 will point to the newly created node.

When we perform put(1,"S"), put(2,"P"), and put(5,"K"), if the hash values modulo 3 are the same, they will map to the same index. In our case, if they all map to index 1, they will form a linked list at that index.

• get(5) will also generate the same hash code i.e hash(5) = 547383

Contract between hashcode and Equal

• If object1 == object2 then their hash should also be same

• If 2 objects hash is same then it doesn't mean that they are equal.

If we compute hash(5) as 547383, then no matter how many times we call the hash function for key 5, we get the same value, 547383.

Suppose hash(10) = 73333 and also hash(61) = 73333

If hash values are the same, it doesn't mean the objects are the same. In this case, the hash of 10 and 61 is 73333, but 10!=61.

Re-Hashing

How HashMap can offer O(1) for insertion, deletion, and seraching? (Rehashing)

If the hash function generates the same index then it will form a big linkedlist around that index.

Average Time Complexity - O(1)

Worst Time Complexity - O(n)

Load Factor

The load factor helps us achieve O(1) time complexity.

The load factor is 0.75. The default size of a HashMap is 16. This means that whenever the HashMap reaches 12 (0.75 * 16 = 12) key-value pairs, it will rehash. This means that it increases the size by doubling it, so from 16 it becomes 32. As soon as we insert the 13th element, it will rehash and increase the size of the HashMap. Additionally, it will recompute the hash values for all the key-value pairs and arrange them in new indices.

Treeify Threshold

What if we have sufficient space, but whatever we insert turns out to be a collision?

The default treeify threshold is 8, which means that whenever the linked list size is greater than 8, it converts the linked list into a tree. The tree is a balanced binary search tree, specifically a Red-Black Tree internally. Hence, the search time is O(logn) because the height of a balanced binary search tree is O(logn).

Time Complexity (Peformance)

Amortized meaning Average

Avg: O(1) - Insertion, Searching and Deletion

Worst Case: For Linked List - O(n), For Tree - O(logn)

LinkedHashMap

• Helps in Maintain insertion order

• (Or) Helps in Maintiain Access order.

• Similar to HashMap, but also uses Double LinkedList.

Entry<K,V>

LinkedHashMap is exactly same as HashMap with extra addition after and before fields in Entry<K,V>

• next: Stores the address of the node that falls under the same index or bin.

• before: Stores the address of the previous node that was inserted into the map before the current value.

• after: Stores the address of the next node that was inserted into the map after the current value.

Working

Lets consider example. We insert the following 6 values to LinkedHashMap.

map.put(1, "A");
map.put(21, "B");
map.put(23, "C");
map.put(141, "D");
map.put(25, "E");

next representation

before and after representation

Line Representations

after and before are used only for accessing the elements in the same order in which they were initially inserted into the LinkedHashMap.

public class Main {
    public static void main(String[] args) {
        System.out.println("------below is LinkedHashMap output ------------");

        Map<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "A");
        map.put(21, "B");
        map.put(23, "C");
        map.put(141, "D");
        map.put(25, "E");

        map.forEach((Integer key, String val) -> System.out.println(key+" : "+ val));

        System.out.println("-------below is normal hash map output -----------");

        Map<Integer, String> map2 = new HashMap<>();
        map2.put(1, "A");
        map2.put(21,"B");
        map2.put(23, "C");
        map2.put(141,"D");
        map2.put(25,"E");

        for (Map.Entry<Integer, String> entry : map2.entrySet()){
            System.out.println(entry.getKey()+":"+entry.getValue());
        }
    }
}

------below is LinkedHashMap output ------------
1 : A
21 : B
23 : C
141 : D
25 : E
-------below is normal hash map output -----------
1:A
21:B
23:C
25:E
141:D

ACCESS ORDER = TRUE

So, when access order is set to true, the map is arranged such that the most frequently accessed elements are placed at the end.

This means that less frequently accessed elements will be at the beginning and the most frequently accessed ones will be at the end.

This is achieved directly putting the element to the last.

public class Main {
    public static void main(String[] args) {
        System.out.println("------below is LinkedHashMap output ------------");
        Map<Integer, String> map = new LinkedHashMap<>(16, 0.75F, true);
        map.put(1, "A");
        map.put(21, "B");
        map.put(23, "C");
        map.put(141, "D");
        map.put(25, "E");

        //accessing some data
        map.get(23);
        map.get(23);
        map.get(21);
        map.forEach((Integer key, String val) -> System.out.println(key + ":"+ val));
    }
}
/*
------below is LinkedHashMap output ------------
1:A
141:D
25:E
23:C
21:B
*/

• Time complexity is same as of HashMap: Average O(1)

Thread Safe Version

• Its not thread safe and there is no thread safe version available for this.

• So we have to explicitly make it this collection thread safe like this

• synchronizedMap puts synchronized keyword while doing all the operations on LinkedHashMap.

Map<Integer, String> map2 = Collections.synchronizedMap(new LinkedHashMap<>());

TreeMap

• Map is Sorted according to its natural ordering of its Key or by Comparator provided during map creation.

• Its based on Red-black tree (Self Balancing Binary Search Tree)

• O(logn) time complexity of insert, remove, get operations.

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map1 = new TreeMap<>((Integer key1, Integer key2) -> key2-key1);
        map1.put(21, "SJ");
        map1.put(13, "KJ");
        map1.put(5, "TJ");

        //decreasing order
        map1.forEach((Integer key, String value) -> System.out.println(key + " : "+ value));

        System.out.println("----------------------");
        Map<Integer, String> map2 = new TreeMap<>();
        map2.put(21, "SJ");
        map2.put(11, "PJ");
        map2.put(13, "KJ");
        map2.put(5, "TJ");

        //increasing order
        map2.forEach((Integer key, String value) -> System.out.println(key + ":"+value));

    }
}

21 : SJ
13 : KJ
5 : TJ
----------------------
5:TJ
11:PJ
13:KJ
21:SJ

Representation

It is represented as tree.

Methods available in SORTEDMAP interface

public class Main {
    public static void main(String[] args) {
        SortedMap<Integer, String> map2 = new TreeMap<>();
        map2.put(21, "SJ");
        map2.put(11, "PJ");
        map2.put(13, "KJ");
        map2.put(5, "TJ");

        System.out.println(map2.headMap(13));
        System.out.println(map2.tailMap(13));
        System.out.println(map2.firstKey());
        System.out.println(map2.lastKey());
    }
}

{5=TJ, 11=PJ}
{13=KJ, 21=SJ}
5
21

Methods Available in NAVIGABLEMAP interface

(rarely used)