Showing posts with label Map. Show all posts

How to create immutable class in Java?

immutable class

Immutable Object
Once created its state can not be altered.
String is good example of Immutable class in Java which you use in your day-to-day programming.

Read: Why String is immutable in Java?

Most important benefit of immutable class is, It provides thread safety so you don't have to worry about its value getting changed in multi-threaded environment. Also immutable class with valid hashCode() and equals() method is good choice for Map key.

Points to be taken care while creating immutable class.

  • Class must be declared as final so it can not be extended. i.e public final class ClassName.
  • All variables/critical methods should be private so it can not be accessed outside of class. i.e private int x;.
  • Make all mutable variables final so it can not be changed after initialization.
    i.e private final int x;.
  • Initialize all variables via constructor only by performing deep copy. (follow example)
  • Do not provide setter methods for variables. i.e public void setX(int x) {this.x = x;}
  • Return cloned object/variable in getter method rather returning actual object. (follow example)

Source code (ImmutableClassLatLon.java)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Example of Immutable class in java.
 * @author javaQuery
 * @date 2019-12-10
 * @Github: https://github.com/javaquery/Examples
 */
public final class ImmutableClassLatLon {
    private final double latitude;
    private final double longitude;
    private final List<String> labels;

    /**
     * @param latitude
     * @param longitude
     * @param labels
     */
    public ImmutableClassLatLon(double latitude, double longitude, List<String> labels) {
        this.latitude = latitude;
        this.longitude = longitude;
        if(labels != null && !labels.isEmpty()){
            this.labels = new ArrayList<>(labels);
        }else{
            this.labels = null;
        }
    }

    /**
     * Will return new copy of List rather returning reference to current list.
     * @return
     */
    public List<String> getLabels() {
        return labels != null ? new ArrayList<>(labels) : null;
    }

    /**
     * Get new object of ImmutableClassLatLon with updated label.
     * @param label
     * @return ImmutableClassLatLon
     */
    public ImmutableClassLatLon addLabel(String label){
        List<String> temporary = new ArrayList<>();
        if(labels != null && !labels.isEmpty()){
            temporary.addAll(labels);
        }
        temporary.add(label);
        return new ImmutableClassLatLon(latitude, longitude, temporary);
    }

    public static void main(String[] args) {
        ImmutableClassLatLon classLatLon = new ImmutableClassLatLon(23.0225, 72.5714, Arrays.asList("India"));
        System.out.println("classLatLon address: " + classLatLon);

        System.out.println("\n- classLatLon getLabels and add label -");
        System.out.println("classLatLon labels before: " + classLatLon.getLabels());
        /* classLatLon.getLabels() will return new copy of List rather returning reference to current list */
        List<String> localLables = classLatLon.getLabels();
        localLables.add("Hindi");
        System.out.println("localLables: " + localLables);
        System.out.println("classLatLon labels after: " + classLatLon.getLabels());

        System.out.println("\n- add new label to classLatLon -");
        System.out.println("classLatLon add label before: " + classLatLon.getLabels());
        /* When new label is added it will return new object of ImmutableClassLatLon rather updating current object's list */
        ImmutableClassLatLon classLatLonNewLabel = classLatLon.addLabel("Asia");
        System.out.println("classLatLon add label after: " + classLatLon.getLabels());
        System.out.println("classLatLonNewLabel address: " + classLatLonNewLabel);
        System.out.println("classLatLonNewLabel labels: " + classLatLonNewLabel.getLabels());

    }
}
Output
As you can see after initialization of ImmutableClassLatLon@36baf30c, user can not change its state even if we provided operation on it.
classLatLon address: com.javaquery.core.immutable.ImmutableClassLatLon@36baf30c

- classLatLon getLabels and add label -
classLatLon labels before: [India]
localLables: [India, Hindi]
classLatLon labels after: [India]

- add new label to classLatLon -
classLatLon add label before: [India]
classLatLon add label after: [India]
classLatLonNewLabel address: com.javaquery.core.immutable.ImmutableClassLatLon@7a81197d
classLatLonNewLabel labels: [India, Asia]
Further Reading
What is the difference between final and effectively final?
How HashMap works internally in Java?
How LinkedHashMap works internally in Java?

How LinkedHashMap works internally in Java?

LinkedHashMap implemented using the HashMap. So before we begin to understand How LinkedHashMap works you should first read How HashMap works internally in Java?

We will understand part of code that defers from HashMap and supports LinkedHashMap implementation.

LinkedHasMap#Entry
Entry class in LinkedHashMap extends Node class of HashMap and contains two more variable before and after to hold the before and after references of Entry object.
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
Now when you put(key, value) pair in LinkedHashMap, it creates new node object by calling newNode(..) method. In newNode(..) method linkNodeLast(LinkedHashMap.Entry<K,V> p) method is called which is responsible for pointing head and tail element in LinkedHashMap and also set reference of before and after objects.
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
Following image shows graphical representation of How LinkedHashMap works internally.


Lets understand LinkedHashMap implementation using real Java Program to make everything clear.

Source code (LinkedHashMapExample.java)
Note: Check value of before, after and next to understand example.
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * LinkedHashMap Example.
 * @author javaQuery
 * @date 2019-11-29
 * @Github: https://github.com/javaquery/Examples
 */
public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<>();

        /* Check value of before, after and next to understand example */
        map.put("AaAaAa", "JJJ");
        /**
         * Current bucket data visualization
         *
         * bucket-index: 2
         * EntryObject1 [before = null, hash = 123, key = AaAaAa, value = JJJ, next = null, after = null]
         */

        map.put("xyz", "KKK");
        /**
         * Current bucket data visualization
         *
         * bucket-index: 2
         * EntryObject1 [before = null, hash = 123, key = AaAaAa, value = JJJ, next = null, after = EntryObject2]
         *
         * bucket-index: 11
         * EntryObject2 [before = EntryObject1, hash = 456, key = xyz, value = KKK, next = null, after = null]
         */

        /* since hashcode of 'AaAaBB' is same as 'AaAaAa' so it be added at 2nd index in bucket */
        map.put("AaAaBB", "LLL");
        /**
         * Current bucket data visualization
         *
         * bucket-index: 2
         * [
         *  EntryObject1 [before = null, hash = 123, key = AaAaAa, value = JJJ, next = EntryObject3, after = EntryObject2]
         *  EntryObject3 [before = EntryObject2, hash = 123, key = AaAaBB, value = LLL, next = null, after = null]
         * ]
         *
         * bucket-index: 11
         * EntryObject2 [before = EntryObject1, hash = 456, key = xyz, value = KKK, next = null, after = EntryObject3]
         */
    }
}
Above program can be graphically represented as follows.


References
How HashMap works internally in Java?
Popular Map interview questions in Java

Popular Map interview questions in Java

Question: Why Map interface does not extends Collection interface?
Answer: Map is (key, value) pair not a collection of one type of values so it does not extends Collection interface. Collection interface accept single object via add(E e) but Map interface requires key, value pair in method put(K key, V value)

Question: Does Map accept `null` as key?
Answer: HashMap and LinkedHashMap accepts null key but TreeMap will throws NullPointerException. HashMap stores null key at 0th index in bucket.

Question: Does Map accept `null` values?
Answer: You can have n null values.

Question: What is the initial capacity of HashMap?
Answer: 16. DEFAULT_INITIAL_CAPACITY = (1 << 4)

Question: What is the maximum capacity of HashMap?
Answer: 1073741824. MAXIMUM_CAPACITY = ( 1 << 30)

Question: Does HashMap maintain insertion order?
Answer: No

Question: Is HashMap synchronized?
Question: Is HashMap thread-safe?
Answer: No

Question: How to synchronize Map?
Answer: Using Collections.synchronizedMap(map), best practice Map m = Collections.synchronizedMap(new HashMap(...));

Question: How to avoid concurrent modification exception?
Answer: Synchronize Map using Map m = Collections.synchronizedMap(new HashMap(...)); or Map n = new ConcurrentHashMap();

Question: How HashMap works internally in Java?
Answer: To understand How HashMap works internally read the article https://www.javaquery.com/2019/11/how-hashmap-works-internally-in-java.html

Question: What happens when you put same key again in HashMap?
Answer: When you put(existing-key, value) in HashMap, it will replace old value with new value. And returns old value.
Map<String, String&gt; map = new HashMap<&gt;();
map.put("a", "x");
String oldValue = map.put("a", "y");
System.out.println(oldValue);
//output: x

Question: Can we store duplicate key in HashMap?
Answer: No

Question: Can we store duplicate value in HashMap?
Answer: Yes.

Question: What is Hash code/key collision?
Answer: When two same or different hash code of key generates same index of bucket location by performing bitwise AND is called hash code/key collision. In this situation HashMap forms linked list at given bucket location (index).

For example "AaAaAa".hashCode() and "AaAaBB".hashCode() generates same hash code.

Question: How HashMap handles Hash code/key collision?
Question: What will happens if two objects have same hash code?
Answer: It forms linked list at bucket location.

Question: Why String, Integer and other wrapper classes are good choice for HashMap key?
Answer: String, Integer and other wrapper classes are immutable so its best choice to use it as key. Why String is immutable in Java?

Question: Can we use mutable key in HashMap?
Answer: Yes, You can use mutable key but its not good choice because it'll fail to retrieve correct value in get(key).

Question: Can we use our own custom object/class as key in HashMap?
Answer: Yes, You can use your custom object as key in HashMap but its necessary to consider immutability of that object and also implementing hashCode() and equals() method in your class.

Question: How HashMap is improved in Java 8?
Answer: Prior to Java 8, HashMap forms linked list in case of hash collision. Now from Java 8 when hash collision occurs and it hits following threshold TREEIFY_THRESHOLD = 8 and MIN_TREEIFY_CAPACITY = 64 then it uses TreeNode to store Entry object to improve HashMap get performance.
Why HashMap resize when it hits TREEIFY_THRESHOLD value which is not required?

Question: Which tree stucture is used in Java 8 to improve performance of HashMap?
Answer: red-black tree structure is used to improce performance of HashMap.

Question: How LinkedHashMap works internally in Java?
Answer: To understand How LinkedHashMap works internally read the article https://www.javaquery.com/2019/12/how-linkedhashmap-works-internally-in.html

How HashMap works internally in Java?

HashMap is one of the implementation of java.util.Map interface. We will understand how it internally stores (put) and retrieve (get) values. HashMap uses array known as bucket/table to store (key, value) pair.

This is one of the popular question in Java Interviews, lets understand how it works.

Instantiation: How to create HashMap object?
There are 3 different ways you instantiate HashMap

  1. new HashMap() - It will create HashMap with default capacity of 16 and default load factor 0.75f.
  2. new HashMap(int initialCapacity) - You can provide the initial capacity of HashMap and default load factor 0.75f is used.
  3. new HashMap(int initialCapacity, float loadFactor) - You can provide both initial capacity and load factor.
Note: We will consider HashMap with default capacity and load factor for explanation of this article.

Understanding implementation of HashMap
I extracted Node class (inner class) from HashMap which implements sub-interface Entry of Map interface. Node class plays important role in implementation of HashMap. Every (key, value) pair in HashMap will be stored as Entry object using Node class implementation.

Node class holds - hash code of key, key, value and `next` is used to store next element (node) reference in case of hash code/key collision. We'll understand hash code/key collision later in this article.
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // hash code of key
    final K key; // the key
    V value; // the value to put
    Node<K,V> next; // next element(node) in case of hash code/key collision 

    Node(int hash, K key, V value, Node<K,V> next) {...}
    ...
    ...
}

What happens when you put(K key, V value) in HashMap?
When you put (key, value) pair in HashMap, it generates hash of key by calling hashCode() method of key and follows these steps...

  • put#1.1: Create the bucket (array) of Node<K, V>[] with default capacity or given capacity if not initialized. 
    • In case of bucket (array) is full then it increases capacity by twice the current capacity and transfer all data to new bucket (array). (i.e default capacity [16] > [32] > [64] ...)
  • put#1.2: Now it generates bucket location (array-index) by performing bitwise AND on current capacity of bucket and hash code of key
    /**
     * i = index to store (key, pair) in bucket (array)
     * n = size of bucket (array)
     * hash = hash code of key
     */
    int i = (n - 1) & hash;
    
  • put#1.3: Fetch node (element) from bucket using generated location (index).
    • put#1.3.1: no element found - insert given key, pair in form of Node object (Entry object).
    • put#1.3.2: element found at that location (index) - its the case of Hash code/key collision.
      • put#1.3.2.1: Now it'll compare key of existing node (element) with newly given key. If both the keys are same then it'll replace current Node's value with new value.
      • put#1.3.2.2: If both the keys are different then it forms linked list at the bucket location (index). Current node's next variable will be assigned to reference of newly given Node (key, value). 


What happens when you get(Object key) in HashMap?
When you try to get value using key, it generates hash of key by calling hashCode() method of key and follows these steps...

  • get#1.1: Generates bucket location (array-index) by performing bitwise AND on current capacity of bucket and hash code of key.
  • get#1.2: Find the Entry(Node) object from that bucket index.
    • get#1.2.1: No Entry object found - returns null.
    • get#1.2.2: Entry object found from bucket - It will compare provided hash of key, key and calls equals() method of key with Entry object found from bucket. 
      • get#1.2.2.1: If everything matched then it returns the Entry object. 
      • get#1.2.2.2: If not matched then it check linked list formed at that bucket location (has `next` element) then do the same check as in get#1.2.2 until it find the correct Entry object from linked list.
Now lets discuss question can be asked in interview related to implementation.

What is the initial capcity and load factor of HashMap?
Initial capacity of HashMap is 16 and load factor is 0.75f.

How HashMap stores data in bucket (array/table)?
Its important to remember that HashMap stores not just hash code of key in Array. It stores hash code, key, value and `next` as Entry object in Array.

What is Hash code/key collision?
When two same or different hash code of key generates same index of bucket location by performing bitwise AND is called hash code/key collision. In this situation HashMap forms linked list at given bucket location (index).

For example "AaAaAa".hashCode() and "AaAaBB".hashCode() generates same hash code.

How HashMap handles Hash code/key collision?
What will happend if two objects have same hash code?
It forms linked list at bucket location.

How HashMap will retrieve value when two keys have same hash code?
Linked list formed at bucket location when two keys have same hash code so it'll travese through all linked list node until it find the correct key and equals method of key retruns true. Read get1.2.2 for complete understanding.

Where does HashMap stores null key?
null key will be stored at 0th index of bucket.

Why String, Integer and other wrapper classesare good choice for HashMap key?
String, Integer and other wrapper classes are immutable so its best choice to use it as key. Why String is immutable in Java?

Can we use mutable key in HashMap?
Yes, You can use mutable key but its not good choice because it'll fail to retrive correct value in get(key).

Can we use our own custom object as key in HashMap?
Yes, You can use your custom object as key in HashMap but its necessary to consider immutablity of that object and also implementing hashCode() and equals() method in your class.

How HashMap is improved in Java 8?
Prior to Java 8, HashMap forms linked list in case of hash collision. Now from Java 8 when hash collision occurs and it hits following threshold TREEIFY_THRESHOLD = 8 and MIN_TREEIFY_CAPACITY = 64 then it uses TreeNode to store Entry object to improve HashMap get performance.
Why HashMap resize when it hits TREEIFY_THRESHOLD value which is not required?

Which tree stucture is used in Java 8 to improve performance of HashMap?
red-black tree structure is used to improce performance of HashMap.

References
Popular Map interview questions in Java
How LinkedHashMap works internally in Java?

How to sum values from List, Set and Map using stream in Java 8?



Following examples shows how you can use java 8 Stream api to do summation of Integer, Double and Long in List, Set and Map.

Source code (Item.java)
public class Item {

    private Long id;
    private String name;
    private Double price;
    
    public Item(String name, Double price) {
        this.name = name;
        this.price = price;
    }
    
    /* getter - setter */

    public Double getPrice() {
        return price;
    }

    public void setPrice(Double price) {
        this.price = price;
    }
}

List
  • Summation of Integers in List.
  • Summation of Price from List of beans(Item).

Source code (ListStreamSum.java)
import com.javaquery.bean.Item;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Summation of element in List using Stream api in java 8.
 *
 * @author javaQuery
 * @date 17th October, 2016
 * @Github: https://github.com/javaquery/Examples
 */
public class ListStreamSum {

    public static void main(String[] args) {
        /* Summation of Integers in List */
        List<Integer> integers = new ArrayList<>(Arrays.asList(10, 20, 30));

        Integer integerSum = integers.stream().mapToInt(Integer::intValue).sum();
        System.out.println("summation: " + integerSum);

        /* Summation when you have list of beans */
        Item motoG = new Item("MotoG", 100.12);
        Item iPhone = new Item("iPhone", 200.12);

        List<Item> listBeans = new ArrayList<>(Arrays.asList(motoG, iPhone));

        Double doubleSum = listBeans.stream().mapToDouble(Item::getPrice).sum();
        System.out.println("summation: " + doubleSum);
    }
}

Output
summation: 60
summation: 300.24

Set
  • Summation of Integers in Set.
  • Summation of Price from Set of beans(Item).

Source code (SetStreamSum.java)
import com.javaquery.bean.Item;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Summation of element in Set using Stream api in java 8.
 *
 * @author javaQuery
 * @date 17th October, 2016
 * @Github: https://github.com/javaquery/Examples
 */
public class SetStreamSum {

    public static void main(String[] args) {
        /* Summation of Integers in Set */
        Set<Integer> integers = new HashSet<>(Arrays.asList(10, 20, 30));

        Integer integerSum = integers.stream().mapToInt(Integer::intValue).sum();
        System.out.println("summation: " + integerSum);

        /* Summation when you have set of beans */
        Item motoG = new Item("MotoG", 100.12);
        Item iPhone = new Item("iPhone", 200.12);

        Set<Item> listBeans = new HashSet<>(Arrays.asList(motoG, iPhone));

        Double doubleSum = listBeans.stream().mapToDouble(Item::getPrice).sum();
        System.out.println("summation: " + doubleSum);
    }
}

Output
summation: 60
summation: 300.24

Map
  • Summation of Integers in Map as a value.
  • Summation of Integers in List as a value.
  • Summation of Price from List of beans(Item) in Map.

Source code (MapStreamSum.java)
import com.javaquery.bean.Item;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Summation of element in Map using Stream api in java 8.
 *
 * @author javaQuery
 * @date 17th October, 2016
 * @Github: https://github.com/javaquery/Examples
 */
public class MapStreamSum {

    public static void main(String[] args) {
        /* Summation of Integers in Map */
        Map<String, Integer> integers = new HashMap<>();
        integers.put("A", 10);
        integers.put("B", 20);
        integers.put("C", 30);

        Integer integerSum = integers.values().stream().mapToInt(Integer::intValue).sum();
        System.out.println("summation: " + integerSum);

        /* Summation when you have List/Set in Map */
        Map<String, List<Integer>> listInMap = new HashMap<>();
        listInMap.put("even_numbers", new ArrayList<>(Arrays.asList(2, 4, 6)));

        integerSum = listInMap.values().stream()
                .flatMapToInt(list -> list.stream().mapToInt(Integer::intValue))
                .sum();
        System.out.println("summation: " + integerSum);

        /* Summation when you have List/Set of beans in Map */
        Item motoG = new Item("MotoG", 100.12);
        Item iPhone = new Item("iPhone", 200.12);

        List<Item> items = new ArrayList<>(Arrays.asList(motoG, iPhone));

        Map<String, List<Item>> itemMap = new HashMap<>();
        itemMap.put("items", items);

        Double doubleSum = itemMap.values().stream()
                .flatMapToDouble(list -> list.stream().mapToDouble(Item::getPrice))
                .sum();
        System.out.println("summation: " + doubleSum);
    }
}

Output
summation: 60
summation: 12
summation: 300.24

How to convert List to Map in Java 8 using Stream API?

Code snippet demonstrate converting List<T> to Map<K,V>.

Source code(User.java)
public class User {
   private Long id;
   private String name;
 
   public Long getId() {
    return id;
   }
   public void setId(Long id) {
    this.id = id;
   }
   public String getName() {
    return name;
   }
   public void setName(String name) {
    this.name = name;
   }
}

Source code(ExampleListToMap.java)
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import javaQuery.beans.User;

public class ExampleListToMap {

    public static void main(String[] args) {
        /* Creating List<String> */
        List<String> listStrings = new ArrayList<String>();
        listStrings.add("Vicky");
        listStrings.add("Thakor");

        /**
         * Convert List<String> to Map<String, String> using `stream` API
         * Explanation:
         * Collectors.toMap(String::toString, listStringName -> listStringName)
         * - String::toString => Calling `toString()` method of `String` class. 
         *                       (Note: Its compulsory to set `key` of Map from String class.)  
         * 
         * - listStringName -> listStringName => Value of Map.
         */
        Map<String, String> mapName = listStrings.stream()
                                                 .collect(Collectors.toMap(String::toString, listStringName -> listStringName));
        /* Print the Map */
        System.out.println("List<String> to Map<String, String>: " + mapName);
        System.out.println("+++++++++++++++++++++++++++++++++++++++++++");

        /* Creating User objects */
        User objUser = new User();
        objUser.setId(1L);
        objUser.setName("Vicky Thakor");

        User objUser2 = new User();
        objUser2.setId(2L);
        objUser2.setName("Chirag Thakor");

        /* Add users to List<User> */
        List<User> listUsers = new ArrayList<User>();
        listUsers.add(objUser);
        listUsers.add(objUser2);

        /**
         * Convert List<User> to Map<Long, User> using `stream` API.
         * Explanation:
         * Collectors.toMap(User::getId, user -> user)
         * - User::getId => Calling `getter` method of `User` class. 
         *                  (Note: Its compulsory to set `key` of Map from User class.)  
         * 
         * - user -> user => Value of Map.
         */
        Map<Long, User> mapUsers = listUsers.stream().collect(Collectors.toMap(User::getId, user -> user));
  
        /* Print the Map */
        System.out.println("List<User> to Map<Long, User>:");
        mapUsers.keySet()
                .forEach(key -> {
                            User getUser = mapUsers.get(key);
                            System.out.println(key + "=" + getUser.getName());
                });
    }
}

Output
List<String> to Map<String, String>: {Vicky=Vicky, Thakor=Thakor}
+++++++++++++++++++++++++++++++++++++++++++
List<User> to Map<Long, User>:
1=Vicky Thakor
2=Chirag Thakor