Sort Element of Tree using non natural sorting algorithm

By default TreeMap store element in default natural sorting of element. But if you want to store element other than default natural sorting order than you need to provide your own Comparator.
Java TreeMap class provide following Constructor for this  purpose.

TreeMap(Comparator<? super k> comparator).

Following example use String as key. As you know String class implements Comparable interface and define its compareTo(String o) method. String class sort element in ascending order(dictionary order).

In the first version of example i commented Comparator implementation.

TreeMap Program without Comparator   

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapComparator {

public static void main(String[] args) {
TreeMap<String, String> cityMap = new TreeMap<>(/*
* new Comparator<String>() {
*
* @Override public int compare(String o1, String o2) { return
* o2.compareTo(o1);
*
* }
*
* }
*/);
cityMap.put("DL", "Delhi");
cityMap.put("BOM","Mumbai");
cityMap.put("UP","Uttar Pradesh");
cityMap.put("UK", "UttaraKhand");
cityMap.entrySet().stream().forEach(System.out::println);
}
}

output

BOM=Mumbai

DL=Delhi

UK=UttaraKhand

UP=Uttar Pradesh

TreeMap example with Comparator

import java.util.Comparator;

import java.util.TreeMap;

public class TreeMapComparator {

public static void main(String[] args) {

TreeMap<String,String> cityMap=new TreeMap<>(new Comparator<String>() {

@Override

public int compare(String o1, String o2) {

return o2.compareTo(o1);

}

});

cityMap.put("DL", "Delhi");

cityMap.put("BOM","Mumbai");

cityMap.put("UP","Uttar Pradesh");

cityMap.put("UK", "UttaraKhand");

cityMap.entrySet().stream().forEach(System.out::println);

}

}

output 

UP=Uttar Pradesh

UK=UttaraKhand

DL=Delhi

BOM=Mumbai

From the output of both program you can clearly understood 

Map.Entry Interface in Java

Map store data in form of key-value pair, these pair called entry. These entries are instance of Map.Entry.

Map.Entry is nested interface.

Within Map interface, Entry interface defined as below

interface Entry<K,V>{
getKey();
getValue();
..
.
}

Method in Map.Entry interface 

getKey() - Returns the key corresponding to this entry.

getValue()- Returns the value corresponding to this entry.

setValue(V value)- Replaces the value corresponding to this entry with the specified value (optional operation).

entrySet() - Return Set<Entry<K,V>>  Collection View of map , whose element of type Map.Entry

Java 8 Comparison Method

comparingByKey()- Returns a comparator that compares Map.Entry in natural order on key.

comparingByKey(Comparator<? super K> cmp)- Returns a comparator that compares Map.Entry by key using the given Comparator.

comparingByValue()- Returns a comparator that compares Map.Entry in natural order on value.

comparingByValue(Comparator<? super V> cmp)- Returns a comparator that compares Map.Entry by value using the given Comparator.

Java Collection API - ConcurrentHashMap in Java

ConcurrentHashMap

ConcurrentHashMap extends AbstractMap and implements ConcurrentMap interface.

Features of ConcurrentHashMap

• ConcurrentHashMap in java is similar to HashMap except Thread - safety.
• Null key is not allowed in ConcurrentHashMap
• Thread-Safety in ConcurrentHashMap is achieved by separate lock for each separate buckets.
• Similar to HashMap, ConcurrentHashMap have default capacity of 16 buckets and concurrency level is also 16 because each buckets have its own lock so that 16 thread work concurrently.
• Iterator provided by ConcurrentHashMap is Fail-Safe while HashMap iterator is Fail-Fast, which means that it will not throw ConcurrentModificationException.
• Read operations  don't block whole Map, So may overlap with update operation(including put and remove).

Why another Map required?, While we have Collections.synchronizedMap() method for making any Map Thread-Safe.

Problem with Hashtable or Synchronized Map is that 

1. All the methods are synchronized with common lock thus only single thread can access at a time,

2.  even for a read operation.

ConcurrentHashMap  solve this issue, so that ConcurrentHashMap provide better performance. 

How the performance is improved in ConcurrentHashMap

1. Solved First issue

ConcurrentHashMap is like the HashMap except one difference that its locking strategy for thread saftey. Unlike Hashtable and synchronized Map , it does not synchronized every method on common lock. ConcurrentHashMap uses separate lock for separate buckets thus locking only portion of Map.

When you construct an HashMap using no-args constructor, internally it create  16 buckets. ConcurrentHashMap also create by default 16 buckets but all 16 buckets have separate locks. So default Concurrency level of ConcurrentHashMap is 16. Since there are by default 16 buckets having 16 separate locks which means 16 threads operates concurrently.

So you can see ConcurrentHashMap provide better performance by locking only portion of the map rather than locking whole map at a time for a single operation, resulting greater performance.

2. Solved 2nd issue

Performance of Java ConcurrentHashMap  is further improved by providing read access concurrently without any blocking.

Constructor in ConcurrentHashMap

• ConcurrentHashMap() - Construct an empty ConcurrentHashMap() with default capacity of 16 and default load factor of 0.75
• ConcurrentHashMap(int Capacity) - Construct an empty ConcurrentHashMap with provided capacity and default load factor
• ConcurrentHashMap(int capacity, double loadFactor) - Construct an empty ConcurrentHashMap with provide capacity and loadFactor.
• ConcurrentHashMap(Map<? extends K, ? extends V> map) -construct a ConcurrentHashMap using provided map.

Java ConcurrentHashMap Example

Null key not allowed

Fail-Safe itrator

When is ConcurrentHashMap a better choice

ConcurrentHashMap is a better choice when there are more reads than writes. As mentioned above retrieval operations are non-blocking so many concurrent threads can read without any performance problem. If there are more writes and that too many threads operating on the same segment then the threads will block which will deteriorate the performance.

Difference between ConcurrentHashMap and HashMap

It is good interview Question. ConcurrentHashMap was added in Java 5 and its implementation is modified in Java 8. 

1. Thread-Safety - First Difference is Thread - Safety, ConcurrentHashMap is design for Multi-Threaded environment. While we can make HashMap also Thread - Safe using Collections.synchronizedMap(HashMap map) method but it reduce the performance because Collections.synchronizedMap(HashMap map) method synchronized all the methods hence at a time only one thread can access a Map. While in ConcurrentHashMap Multiple Thread can perform operation. 

2. Locking Concept - 

3. allowed non blocking read access for performance improvement

4. ConcurrentHashMap does not allowed null key while HashMap allowed one and only one null key.

5. Iterator of HashMap is Fail-Fast while ConcurrentHashMap Iterator is Fail-Safe. i.e. After getting iterator if map is modified it will not throw ConcurrentModificationException.

Question and Answer

Q: So Mr.Hash Map, how can I find if a particular key has been assigned to you?

A: Cool, you can use the containsKey(Object KEY) method with me, it will return a Boolean value if I have a value for the given key.

Q: How do I find all the available keys that are present on the Map?

A: I have a method called as keyset() that will return all the keys on the map. In the above example, if you write a line as – System.out.println(objMap.keySet());

It will return an output as-
[Name, Type, Power, Price]

Similarly, if you need all the values only, I have a method of values().
System.out.println(objMap.values());

It will return an output as-
[Suzuki, 2-wheeler, 220, 85000]

Q: Suppose, I need to remove only a particular key from the Map, do I need to delete the entire Map?

A: No buddy!! I have a method of remove(Object KEY) that will remove only that particular key-value pair.

Q: How can we check if you actually contain some key-value pairs?

A: Just check if I am empty or not!! In short, use isEmpty() method against me ;) 

Collection Frame Work : TreeMap in Java

TreeMap

interface SortedMap extends Map

interface NavigableMap extends SortedMap

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable 

TreeMap class extends AbstractMap and implements NavigableMap interface. 

TreeMap is best choice when you want to store key value pair according to some sorting order. Entries in TreeMap sorted according to key.

Entries in TreeMap are sorted according to natural sorting order (default sorting order) of key or Custom Sorting order.

For Custom Sorting order Comparator provided at time of creating of TreeMap.

How TreeMap is Implemented in Java

According to Java Doc TreeMap is a Red-Black tree based NavigableMap implementation. This implementation guaranteed log(n) time cost for the containsKey , get, put and remove operation.

Feature of TreeMap

• TreeMap is Red-Black tree based NavigableMap implementation
• TreeMap stores its entries(key,value) according to some sorting order, this sorting order based on key. 
• If you want to store entries according to some custom sorting order then you need to provide Comparator. 
• TreeMap does not allow null key as other Map like HashMap and LinkedHashMap support one and only one null key.
• TreeMap in java is not Synchronized, Hence it is not Thread Safe. 

Java TreeMap Constructor

• TreeMap() -  Construct new and empty TreeMap using the natural ordering its keys
• TreeMap(Comparator<? super K> comprator) - constructs new, empty TreeMap orerded according to Comparator.
• TreeMap(Map<? extends K, ? extends V> map ) - constructs new TreeMap based on provided Map , ordered according to natural ordering of keys.
• TreeMap(SortedMap<K,? extends V> sortedMap) - construct new TreeMap containing the same mapping and using the same ordering as specified sorted map.

TreeMap Example - Construction , Insertion and Iteration

Following example add pincode as key and Corresponding area as value. This example uses spring for dependency Injection. 


package io.lambda.collection.map.treemap;

import java.util.Map;

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;

public class Zip {

private Map<Integer,String>zipcode;

public Zip(Map<Integer,String>zipcode) {
this.zipcode=zipcode;
}

public void addMockZipCode() {
zipcode.put(226010, "Gomti Nagar");
zipcode.put(110001,"CP");
zipcode.put(110041,"WestDelhi");
zipcode.put(110070,"vasantkunj");
                zipcode.put(110070,"Vasantkunj");

}
public void display() {
                //lambda expression to print entries.
zipcode.forEach((k,v)->{System.out.println(k+":"+v);});
}

public static void main(String[] args) {
ApplicationContext  context=new ClassPathXmlApplicationContext("zipcode.xml");
Zip zip=context.getBean("zipcode", io.lambda.collection.map.treemap.Zip.class);
zip.addMockZipCode();
zip.display();

}
}

//zipcode.xml

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.springframework.org/schema/beans
http://www.springframework.org/schema/beans/spring-beans.xsd
http://www.springframework.org/schema/util
    http://www.springframework.org/schema/util/spring-util.xsd">
    <bean id="zipcode" class="io.lambda.collection.map.treemap.Zip">
    <constructor-arg  ref="treeMap"/>
   
      </bean>
      <bean id="treeMap" class="java.util.TreeMap"></bean>
</beans>

Output : 
110001:CP
110041:WestDelhi
110070:Vasantkunj

226010:Gomti Nagar

The output of the above program clearly show that key is sorted according to its natural sorting order.

It is also noted that Vasantkunj added twice but it store only once, it overwrite old value with new one. [ as calculated hash code for keys are same].

TreeMap doesnot allow null key.

Though HashMap and LinkedHashMap allowed one and only one null as key , TreeMap in java does not allow null as a key. An attempt to add null as key throw NullPointerException.

package io.lambda.collection.map.treemap;

import java.util.Map;

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;

public class Zip {

private Map<Integer,String>zipcode;

public Zip(Map<Integer,String>zipcode) {
this.zipcode=zipcode;
}

public void addMockZipCode() {
zipcode.put(226010, "Gomti Nagar");
zipcode.put(110001,"CP");
zipcode.put(110041,"WestDelhi");
zipcode.put(110070,"vasantkunj");
zipcode.put(110070, "Vasantkunj");
zipcode.put(null, "upcomingCity");
}
public void display() {
zipcode.forEach((k,v)->{System.out.println(k+":"+v);});
}

public static void main(String[] args) {
ApplicationContext  context=new ClassPathXmlApplicationContext("zipcode.xml");
Zip zip=context.getBean("zipcode", io.lambda.collection.map.treemap.Zip.class);
zip.addMockZipCode();
zip.display();

}

Output : 
Exception in thread "main" java.lang.NullPointerException
at java.base/java.util.TreeMap.put(TreeMap.java:561)
at io.lambda.collection.map.treemap.Zip.addMockZipCode(Zip.java:22)

at io.lambda.collection.map.treemap.Zip.main(Zip.java:31)

Custom Sorting order of key in TreeMap 

Entries in TreeMap are sorted according to natural sorting order of keys, but if you want to sort TreeMap according to some custom sorting order e.g. Descending order of number , words etc. then you provide Comparator  at Map creating time.

/**

* Student Class

**/

package io.lambda.collection.map.treemap;

public class Student implements Comparable<Student>{

Integer enrollmentId;

String name;

public Student(Integer enrollmentId,String name) {

this.enrollmentId=enrollmentId;

this.name=name;

}

public Integer getEnrollmentId() {

return enrollmentId;

}

public void setEnrollmentId(Integer enrollmentId) {

this.enrollmentId = enrollmentId;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

@Override

public int compareTo(Student student) {

return this.enrollmentId.compareTo(student.enrollmentId);

}

@Override

public String toString() {

return "enrollment : "+this.enrollmentId +"name :"+this.name;

}

}

/**

*Course Class

*/

package io.lambda.collection.map.treemap;

public class Course {

String name;

public Course(String name) {

this.name=name;

}

@Override

public String toString() {

return this.name;

}

}

/**

* Client Class having main method

*/

package io.lambda.collection.map.treemap;

import java.util.Comparator;

import java.util.Map;

import java.util.TreeMap;

public class StudentMap {

Map<Student,Course> classX; 

static Map<Student,Course> classXI; 

public StudentMap(Map<Student,Course> classX) {

this.classX=classX;

}

public void createSection() {

classX.put(new Student(1001,"Yogesh"), new Course("X"));

classX.put(new Student(1002,"Mohan"), new Course("X"));

classX.put(new Student(1000,"Rakesh"),new Course("X"));

}

public void display() {

classX.forEach((student,course)->{System.out.println(student+":"+course);});

}

public static void main(String[] args) {

  StudentMap map=new StudentMap(new TreeMap<Student,Course>());

  

  map.createSection();

  map.display();

                  

                //anonymous implementation of  Comparator interface

  classXI=new TreeMap<Student,Course>(new Comparator<Student>() {

  @Override

  public int compare(Student s1,Student s2) {

  return s1.name.compareTo(s2.name)==0?0:s1.name.compareTo(s2.name)>0?

  5:-1;

  }

}); 

  classXI.putAll(map.classX);

  classXI.entrySet().stream().forEach(System.out::println);

}

}

Output

enrollment : 1000name :Rakesh:X

enrollment : 1001name :Yogesh:X

enrollment : 1002name :Mohan:X

enrollment : 1002name :Mohan=X

enrollment : 1000name :Rakesh=X

enrollment : 1001name :Yogesh=X

Here custom Comparator built with logic to sort entries of TreeMap based on Student Class name attribute.  First part of output highlighted with blue color show the output from TreeMap no-args constrcutor while other Green color show the output which implement Comparator interface.

It sorts entries based one Student Name.

TreeMap is not Synchronized

TreeMap  in Java is not ThreadSafe. In case we need to synchronize it , it should synchronize with the help of Collections.synchronizedSortedMap(TreeMap<K,V>) method.

for example

SortedMap map=Collections.synchronizedSortedMap(classX); // where classX is from above example which is Type of TreeMap<Student,Course>

TreeMap iterator is Fail-Fast

Like other Collection class iterator TreeMap iterator is Fail-Fast. If the map is structurally modified after getting Iterator for Map, then Iterator will throw a ConcurrentModificationException.

TreeMap Iteration 

1. Get only keys using Map.keySet() method

package io.lambda.collection.map.treemap;

import java.util.Iterator;

import java.util.Map;

import java.util.TreeMap;

public class TreeMapIterator {

private Map<String,String>stateCapitalMap = new TreeMap<>(); //No-args constructor

/*

 * add state and there capital 

 */

public void addMockEntries() {

stateCapitalMap.put("Delhi", "New Delhi");

stateCapitalMap.put("Uttar Pradesh", "Lucknow");

stateCapitalMap.put("Uttara Khand", "Dehradun");

stateCapitalMap.put("J&K", "Shri Nagar");

stateCapitalMap.put("Bhiar", "Patna");

}

public void displayKeySetIterator() {

Iterator<String> itr=stateCapitalMap.keySet().iterator();

System.out.println("using Map interface Set<T>keySet().itrator()\tOutput\n");

while(itr.hasNext()) {

System.out.println(itr.next());

}

}

public void displayKeySetForEachLoop() {

System.out.println("\nUsing For - Each loop\t Output\n");

for(String state : stateCapitalMap.keySet()) {

System.out.println(state);

}

}

public void displayKeySetForEachLambda() {

System.out.println("\nusing Stream class stream() method\toutput\n");

stateCapitalMap.keySet().stream().forEach(System.out::println);

}

public static void main(String[] args) {

TreeMapIterator example=new TreeMapIterator();

example.addMockEntries();

example.displayKeySetIterator();

example.displayKeySetForEachLoop();

example.displayKeySetForEachLambda();

}

}

using Map interface Set<T>keySet().itrator() Output

Bhiar

Delhi

J&K

Uttar Pradesh

Uttara Khand

Using For - Each loop  Output

Bhiar

Delhi

J&K

Uttar Pradesh

Uttara Khand

using Stream class stream() method output

Bhiar

Delhi

J&K

Uttar Pradesh

Uttara Khand

2.  Get Value only using Collection<T> values() method

package io.lambda.collection.map.treemap;

import java.util.Iterator;

import java.util.Map;

import java.util.TreeMap;

public class TreeMapIterator {

private Map<String,String>stateCapitalMap = new TreeMap<>(); //No-args constructor

/*

 * add state and there capital 

 */

public void addMockEntries() {

stateCapitalMap.put("Delhi", "New Delhi");

stateCapitalMap.put("Uttar Pradesh", "Lucknow");

stateCapitalMap.put("Uttara Khand", "Dehradun");

stateCapitalMap.put("J&K", "Shri Nagar");

stateCapitalMap.put("Bhiar", "Patna");

}

public void displayValuesIterator() {

Iterator<String>value=stateCapitalMap.values().iterator();

while(value.hasNext()) {

System.out.println(value.next());

}

}

public void displayValuesUsingForEachLoop() {

for(String s: stateCapitalMap.values()) {

System.out.println(s);

}

}

public void displayValuesUsingStreamMethod() {

stateCapitalMap.values().stream().forEach(System.out::println);

}

public static void main(String[] args) {

TreeMapIterator example=new TreeMapIterator();

example.addMockEntries();

System.out.println("Output : Using Iterator\n");

example.displayValuesIterator();

System.out.println("Output : Using For - Each loop \n");

example.displayValuesUsingForEachLoop();

System.out.println("Output : Using forEach() method \n");

example.displayValuesUsingStreamMethod();

}

}

Output : Using Iterator

Patna

New Delhi

Shri Nagar

Lucknow

Dehradun

Output : Using For - Each loop 

Patna

New Delhi

Shri Nagar

Lucknow

Dehradun

Output : Using forEach() method 

Patna

New Delhi

Shri Nagar

Lucknow

Dehradun

3. Iteration Key and Value 

package io.lambda.collection.map.treemap;

import java.util.Iterator;

import java.util.Map;

import java.util.TreeMap;

public class TreeMapIterator {

private Map<String,String>stateCapitalMap = new TreeMap<>(); //No-args constructor

/*

 * add state and there capital 

 */

public void addMockEntries() {

stateCapitalMap.put("Delhi", "New Delhi");

stateCapitalMap.put("Uttar Pradesh", "Lucknow");

stateCapitalMap.put("Uttara Khand", "Dehradun");

stateCapitalMap.put("J&K", "Shri Nagar");

stateCapitalMap.put("Bhiar", "Patna");

}

public void displayEntriesIterator() {

Iterator<Map.Entry<String, String>>itr=stateCapitalMap.entrySet().iterator();

while(itr.hasNext()) {

Map.Entry<String, String>mapEntry=itr.next();

System.out.println(mapEntry.getKey()+" : "+mapEntry.getValue());

}

}

public void displayEntriesUsingForEachLoop() {

for(Map.Entry<String, String> mapEntry:stateCapitalMap.entrySet()) {

System.out.println(mapEntry.getKey()+" : "+mapEntry.getValue());

}

}

public void displayEntriesUsingForEachMethodLambdaMethodReference() {

stateCapitalMap.entrySet().stream().forEach(System.out::println);

}

public void displayEntriesUsingForEachLambda() {

stateCapitalMap.forEach((k,v)->{System.out.println(k+" : "+v);});

}

public static void main(String[] args) {

TreeMapIterator example=new TreeMapIterator();

example.addMockEntries();

System.out.println("Output : Using Iterator\n");

example.displayEntriesIterator();

System.out.println("\nOutput : Using For - Each loop \n");

example.displayEntriesUsingForEachLoop();

System.out.println("\nOutput : Using forEach() method \t Method Reference \n");

example.displayEntriesUsingForEachMethodLambdaMethodReference();

System.out.println("\nOutput : Using forEach() method \t Lambda expression \n");

example.displayEntriesUsingForEachLambda();

}

}

Output : Using Iterator

Bhiar : Patna

Delhi : New Delhi

J&K : Shri Nagar

Uttar Pradesh : Lucknow

Uttara Khand : Dehradun

Output : Using For - Each loop 

Bhiar : Patna

Delhi : New Delhi

J&K : Shri Nagar

Uttar Pradesh : Lucknow

Uttara Khand : Dehradun

Output : Using forEach() method   Method Reference 

Bhiar=Patna

Delhi=New Delhi

J&K=Shri Nagar

Uttar Pradesh=Lucknow

Uttara Khand=Dehradun

Output : Using forEach() method   Lambda expression 

Bhiar : Patna

Delhi : New Delhi

J&K : Shri Nagar

Uttar Pradesh : Lucknow

Uttara Khand : Dehradun

Collection Frame Work - LinkedHashMap in Java

LinkedHashMap in Java

LinkedHashMap extends HashMap and implements Map Interface.

LinkedHashMap is Hash Table and Linked List implementation of Map interface with predictable iteration order. 

LinkedHashMap use doubly Linked List for Storing its entries. Apart from maintaining Doubly LinkedList, LinkeHashMap internal implementation is same as internal implementation of HashMap.

LinkedHashMap is used when  order is important, There are two option for ordering 

1. insertion Order

2. Accessing order 

Insertion ordering- Insertion ordering is default Ordering in the LinkedHashMap.Insertion ordering means if you iterate a LinkedHashMap you'll get the keys in the order in which they were inserted in the Map.  Note that insertion order is not affected if a key is re-inserted into the map (if a same key in inserted more than once the last time it was inserted will be taken into account).

Access ordering- Another option for ordering in LinkedHashMap is access ordering. Which means while iterating order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently. A special constructor is provided to create a LinkedHashMap that follows access ordering. If you pass true in that constructor then access ordering is followed.

How the LinkedHashMap in JAVA is implemented ?

LinkedHashMap is Hash Table and Linked List implementation of Map interface with predictable iteration order. 

LinkedHashMap use doubly Linked List for Storing its entries. Apart from maintaining Doubly LinkedList, LinkeHashMap internal implementation is same as internal implementation of HashMap.

• Unlike  the HashMap which is unordered Collection of entries, LinkedHashMap maintain ordering ot the entries. By default it is insertion order i.e. in which order entries are added to map, in same order entries are fetched . LinkedHashMap(int capacity, double loadFactor, boolean order) constructor change it order to access order i.e. from least recently accessed to most recently accessed elements.
• Like HashMap , LinkedHashMap support only Object type as key and value.
• Like HashMap, LinkedHashMap allowed one and only one null key 
• Like  HashMap , LinkedHashMap does not allow duplicate key while duplicate values are allowed, in case of value inserted with duplicate key LinkedHashMap overwritten old value with new value for that key.
• Like HashMap  , Insertion order does not affect when a key is reinserted into Map. This Class provides all the operation of Map interface.
• Like HashMap, LinkeHashMap is not sychronized i.e. its methods are not thread safe. For Thread safety you need to Convert it's using Collections.synchronizedMap(LinkedHashMap map)
• Like HashMap, LinkedHashMap doesnot implements Iterable interface, so you cannot get iterator directly.

Constructor of Linked HashMap

• LinkedHashMap() - Construct new,empty LinkedHashMap with Default Capacity of 16 and default load factor .75
• LinkedHashMap(Map<? extends K, ? extends V> map) - use  another map to create LinkedHashMap
• LinkedHashMap(int capacity) - create LinkedHashMap by provided capacity and default load factor.
• LinkdedHashMap(int capacity, double loadFactor) - create map by provided capacity and load factor.
• LinkedHashMap(int capacity, double loadFactor boolean order) - this constructor is used to create a LinkedHashMap to override default ordering.

Example of LinkedHashMap in Java

/**

 * 

 * @author yogesh

 *

 */

package io.lambda.collection.map.hashMap;

import java.util.Iterator;

import java.util.LinkedHashMap;

import java.util.Map;

public class LinkedHashMapExample {

private static Integer zip;

private static String area;

public static void main(String[] args) {

Map<Integer,String>zipCode=new LinkedHashMap<>();

zipCode.put(11001, "New Delhi");

zipCode.put(110070, "Vasantkunj");

zipCode.put(110041, "WestDelhi");

zipCode.put(110020, "southDelhi");

zipCode.put(110070, "vasantkunj");//duplicate key

zipCode.put(null,"newArea");// null keys

zipCode.put(110010, null); // null values

zipCode.put(110002,null); //null values for different key

    zipCode.put(null, "area"); //duplicate null keys

zipCode.forEach((k,v)->{System.out.println(k+":"+v);});

}

}

//output

11001:New Delhi

110070:vasantkunj

110041:WestDelhi

110020:southDelhi

null:area

110010:null

110002:null

Output Analysis

1. As you know default order is insertion order, Output of above program clearly show this.

2. key 110070 repeated two times , last of value of key 110070 overwrite its old value, how key maintain its insertion order.

3. above program have two null key, only one null key is inserted into Map, However overwrite old value with latest.

4. key 110010 and 110002 have null values, they  are inserted .

LinkedHashMap with Accessing Order using LinkedHashMap(int capacity, double loadFactor, boolean accessorder) constructor 

Using LinkedHashMap(int capacity, double loadFactor, boolean  accessorder) Constructor you can change default order of iteration, when you set accessorder to true its  Order of iteration is in which entries are last accessed. 

Example

/**

 * 

 * @author yogesh

 *

 */

package io.lambda.collection.map.hashMap;

import java.util.Iterator;

import java.util.LinkedHashMap;

import java.util.Map;

public class LinkedHashMapExample {

private static Integer zip;

private static String area;

public static void main(String[] args) {

Map<Integer,String>zipCode=new LinkedHashMap<>(16,0.75f,true);

zipCode.put(11001, "New Delhi");

zipCode.put(110070, "Vasantkunj");

zipCode.put(110041, "WestDelhi");

zipCode.put(110020, "southDelhi");

zipCode.put(110070, "vasantkunj");//duplicate key

zipCode.put(null,"newArea");// null keys

zipCode.put(110010, null); // null values

zipCode.put(110002,null); //null values for different key

    zipCode.put(null, "area"); //duplicate null keys

zipCode.forEach((k,v)->{System.out.println(k+":"+v);});

}

}

// Output

11001:New Delhi

110041:WestDelhi

110020:southDelhi

110070:vasantkunj

110010:null

110002:null

null:area

Output Analysis

1. Order of iteration is according to last accessed entries key 110070 inserted at second fourth place so this constructor provide last accessed value against key 110070

LinkedHashMap is not Synchronized

LinkedHashMap methods like HashMap and TreeMap are not Synchronized, if you required to make it Thread-Safe , Collections.synchronizedMap(Map<k,v> map) method is used

Map<K,V> map=Collections.synchronizedMap(new LinkedHashMap<k,v>());

Linked HashMap Iterator is Fail-Safe

LinkedHashMap  , does not implements Iterable interface Like other Map Classes, so it does not have its iterator directly while with help of Set<K> keySet() , Collection<V> values() or Map.Entry<K,V> entrySet() you can obtain iterator.

The Iterator returned by LinkedHashMap is fail-safe i.e. after getting the Iterator of LinkedHashMap , if Map is modified then Iterator throw ConcurrentModificationException

Performance of LinkedHashMap / Time Complexity

Collection Frame Work - HashMap in Java

HashMap

HashMap extends AbstractMap and implements Map Interface. HashMap is used when we want to store unordered and unsorted  key value pairs where key is always unique.

HashMap is based on Hash Table data structure. HashMap  uses hash table and bucketing logic to store each entries (key and value).

When you want to retrieve an object out of HashMap, you have to pass the key. Based on the hashcode of the provided key, the underlying algorithms locates the key and returns the associated value.


HashMap, like any other hash based collections, provides constant in time operations like put, get, remove, contains etc. Because, the logic is based on hashcode and the size of the HashMap doesn’t affect the time it requires.

Feature of HashMap

HashMap is used to store object in key value pair where key is always unique.

key and value  both are object type.

HashMap support null key and null value, However one and only one null key allowed.

Value may be duplicated, for a key. HashMap update latest value for given key.

By default  entries in HashMap are unordered and unsorted while  Iterating.

Iterators on the HashMap are fail-fast and throws ConcurrentModificationException when the HashMap is modified, while an iterator is active.

Hashmap operations are not synchronized and you will have to synchronoize the threads accessing HashMap on you own.

Constructor of HashMap

HashMap() - Default HashMap constructor, with default capacity 16 and default loadFactor of 0.75
HashMap(Map<? extends K, ? extends V> map) - This Constructor is used to create Map based on some existing Map.
HashMap(int capacity) - This Constructor is used initialize HashMap with provided capacity and default load factor
HashMap(int capacity, double loadFactor) - this constructor is used to initialize HashMap with provided capacity and load factor.

What is Capacity and Load Factor                                                 

Like any other Collection class HashMap also comes with default Capacity and default load Factor. An instance of HashMap depends upon two factor 1. Capacity and 2 . Load Factor.
The Capacity is number of bucket in hash table.  The HashMap has default capacity 16 and load factor 0.75. Which means when a HashMap is 75 % occupied the background process create a bigger HashMap based on some algorithm, and  migrate all entries of old HashMap to new HashMap. Old HashMap become the candidate of garbage collector.

Example of HashMap

HashMap using Constructor

//Default Constructor default capacity and default load factor

Map<String,String> map=new HashMap<>();
map.put("country","India");
map.put("capital","Delhi");

This is most basic and most used form of HashMap creation. First you will create a HashMap using Default constructor, then using put(K k, V v) method add entries to Map. This is dyanmic and mutable map so you can put , replace or remove entries any number of times.

Create Immutable HashMap using Collections utility Class

Immutable Map once created can't be modified i.e. you cannot add, update, remove any entries. if you try you will get UnsupportedOperationException.

Map<String,String> map=new HashMap<>();

map.put("country","India");

map.put("capital","Delhi");

Map<String,String> immutableMap=Collections.unmodifiableMap(map);

you can create Immutable Map using unmodifiableMap() method of Collections utility class, it is two step process.

 1. firstly you create a mutable map

2. then convert this mutable map using Collections class unmodifiableMap() static method.

This will create two physical Map which not good as production point of view.

Create Immutable HashMap using Java 9 of() and ofEntries() method

using Map.of() overloaded method, this method is overloaded upto 10 key value pair

for example:-

Map<String,String> immutableMap = Map.of("Country","India");

Map<String,String>immutableMap=Map.of("country","india","state","delhi");

 Map.ofEntries() method  not restricted like Map.of() method, it have varargs type of Map.Entry<? extends K, ? extends V>. 

Map.entry() method is used to create Map.Entry type object.

Map<String,String> immutableMap=Map.ofEntries(Map.entry("country","India"),Map.entry("Capital","Delhi"));

                                                                         

Create Singleton and Empty HashMap using Collections

What is Singleton Hash Map

Singleton Hash Maps have single entry and immutable in nature, In other words you cannot add , update or remove another entry

Map<String,String> singletonMap=Collections.singletonMap("Country","India");

What is Empty Hash Map

Empty Hash Maps also immutable , you cannot add, update, remove it later. As name suggest you can create an empty Hash Map has no entry.

Map<String,String> emptyHashMap=Collections.emptyMap();

 Using Stream to create HashMap

Java 8 Streams have Collectors.toMap() method to  create Map from different things.

Convert List to Map using Stream Collectors.toMap method

Lets consider Book Class which have two member fields isbn and title and getters and setters and a constructor with both members.

public class Book{

String isbn;

String title;

//getter and setter

//constructor using parameter

}

List of Books

List<Book> bookList = new ArrayList<>();

bookList.add(new Book("isbn1","Java Tech"));

// 

The Java Stream Collectors.toMap() is most popular method to create maps. This method take two Lambda expression, out of which first is key other is value.

Map<String,String> bookMap=bookList.stream().collect(Collectors.toMap(Book::getIsbn, Book::getTitle));

However you can create inline map using Collectors.toMap

Map<String,String>bookinlineMap=Stream.of(

new Book("isbn3","title3");

// more objects if required

).collect(Collectors.toMap(Book::getIsbn, Book::getTitle));

Book class method getIsbn and getTitle are non static method , however they are referred in static way Book::getIsbn and Book::getTitle . Because, when you iterate a collection, like the one above, the Java Stream will smartly replace the Class Name with the instance of current object. Hence the call actually happens on the nth Book in the list – where n is the index of current iteration.

 Convert Entrie object to Map Value List<V> to Map<K,V>  using Stream Collectors.toMap() method

In the above example only isbn and title member are used to create map entries. But in some situation you want to create Book object as value.

public Class Book{

private String isbn;

private String title;

private String author;

private double price;

// getter and setter 

// public Book(String isbn,String title,String author, double price){

this.isbn=isbn;

this.title=title;

this.author=author;

this.price=price;

}

}

In this case we use following

Map<String,Book> map=bookList.stream().collect(Collectors.toMap(Book::getIsbn, Function.identity()));

Here, we have used Function.identity() to refer to the actual Book instance. Where the identity() method returns a function that returns the input object.

How to group by a Field using Stream groupingBy

Many a times, we have to iterate through a Collection and group by id or any other field. To demonstrate we will iterate the above list of books to group by books with same name.
List<bookList> ————> Map<String, List<Book>>

Map<String, List<Book>> groupedByName = bookList.stream().collect(Collectors.groupingBy(Book::getTitle));

Here, we have used Collectors.groupingBy and passed a Method Reference to users name.
And, the output we get:

Using Guava Library to Create HashMap

Using Google’s Guava Library, you can create and initialize maps inline.

Immutable Map using Google Guava

Map<String, String> map = ImmutableMap.of("country", "India", "capital", "Delhi", "Flag", "Tricolor");

However, it creates an Immutable map of n key/value pairs. The of function takes varargs and you can pass any number of entries inline.

There is a way to create a Mutable map using Google Guava.

Mutable Map using Google Guava

Map<String, String>ImmutableMap 
                                       =ImmutableMap.of("country", "India", "capital", "Delhi", "Flag", "Tricolor"

Map<String, String> mutuableMap = Maps.newHashMap(immutableMap);

However, it creates two different maps. Firstly create an immutable map with the entries and then create a mutable map.

Iterating HashMap 

HashMap/ Map does not have iterator itself.

1. Iterating Key of HashMap

• Via key Iterator using Set<K> keySet() method 
• Via for-each loop
• Via a Stream

 Via Key Iterator using Set<K> keySet() method 

you can iterate all the key of Map using keySet() method, It return Set<K> from this we get iterator of the set following example demonstrate.

public static void main(String[] args) {

Map<String,String> map=new HashMap<>();

map.put("Country", "India");

map.put("Capital", "Delhi");

map.put("Population", "125M");

Iterator<String> iterator =map.keySet().iterator();

while(iterator.hasNext()) {

String key=iterator.next();

String value =map.get(key);

System.out.println(key +" :" +value);

}

}

//output 

Country :India

Population :125M

Capital :Delhi

Via For-Each loop

from Java 5 you can use for each loop to iterate Map .

for example :

public static void main(String[] args) {

Map<String,String> map=new HashMap<>();

map.put("Country", "India");

map.put("Capital", "Delhi");

map.put("Population", "125M");

for(String key : map.keySet()) {

System.out.println(key +":"+map.get(key));

}

}

// output

Country :India

Population :125M

Capital :Delhi

Via Stream
From Java 8 you can use Java Stream to iterate key of the Map. First obtain keySet from Map then obtain stream from keySet .
Following example demonstrate this

public static void main(String[] args) {
Map<String,String> map=new HashMap<>();
map.put("Country", "India");
map.put("Capital", "Delhi");
map.put("Population", "125M");

Stream<String> stream=map.keySet().stream();
stream.forEach(key ->System.out.println(key+":"+map.get(key)));
//map.keySet().stream().forEach(System.out::println);
}

// output

Country :India

Population :125M

Capital :Delhi

2. Iterating the Value of Map

• Via values() method
• via for-each
• via stream

public static void main(String[] args) {

Map<String,String> map=new HashMap<>();

map.put("Country", "India");

map.put("Capital", "Delhi");

map.put("Population", "125M");

/*

 * Iterator<String> iterator =map.keySet().iterator(); while(iterator.hasNext())

 * { String key=iterator.next(); String value =map.get(key);

 * System.out.println(key +" :" +value); }

 */

/*

 * for(String key : map.keySet()) { System.out.println(key +":"+map.get(key)); }

 */

/*

 * Stream<String> stream=map.keySet().stream(); stream.forEach(key

 * ->System.out.println(key+":"+map.get(key)));

 */

//Via Iterator

Iterator<String> value=map.values().iterator();

while(value.hasNext())

System.out.println(value.next());

//via For-each

for(String viaForEachValue :map.values()) {

System.out.println(viaForEachValue);

}

//Via Stream

map.values().stream().forEach(viaStreamValue->System.out.println(viaStreamValue));

}

3. Iterating Entries of HashMap

• Using Iterator
• Using for-each loop
• Using JAVA 8

Using Iterator

public class Student{
private int id;
private String firstName;
private String lastName;
private String zipCode;
//accessor and mutator methods
// constructor
......
}
List<Student> students=new ArrayList<>();
students.add(new Student(1 ,"Yogesh","Kumar","110010"));
students.add(new Student(2, "Mohan","P","111011"));

Map<Integer,Student> map=students.stream().collect(Collectors.toMap(Student::getId, Function.identity());

Iterator<Map.Entry<Integer,Student>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry<Integer,Student> mapEntry=iterator.next();
Integer key=mapEntry.getKey();
Student student=mapEntry.getValue();

}

for(Map.Entry<Integer,Student> mapEntry : map.entrySet()){

Integer key=mapEntry.getKey();
Student student=mapEntry.getValue();

}

map.stream().forEach((k,v)->{System.out.println(k +":"+v)});

map.entrySet().forEach(System.out::println); //method reference;

HashMaps and Multi Threading.

Working with multi-threading is always tricky. But, when it comes to HashMaps along with multi threading, it is straightforward. However, you need to know few of the basics. Let’s cover those basics here.
HashMaps are not synchronized. This means, you can actually have multiple threads reading and writing from same Hashmap.
For example, consider you have a thread that is iterating a HashMap of size 10. Meanwhile, another thread removes an element from the Hashmap and the size now became 9. This can cause the iteration logic go on toss. To make it easier the iterators are made fail-fast. In other words, when the iterator senses modification of the underlying HashMap, they immedietly throw ConcurrentModificationException.
This behavior is really helpful, as you can rely on the application to fail and hence no need to worry about having dirty reads. Although, if snychronization between threads is really important for you, you can still synchnronize the blocks or the objects accessing the HashMaps.
Alternatevly, you can use a Synchrnoized copy of your Hashmap. Refer to below example to learn how to get a synchronized copy of your HashMap.

1. Map synchronizedMap = Collections.synchronizedMap(hashMap);

The synchronizedMap is a synchrnozed copy of your map. You can use this map safely with the threads. However, remember this is a copy of your existing hashmap. Therefore, if you have a really big hashmap this will be expensive on the memory.

When to use HashMaps

HashMaps have variety of usages. Having a key value structure they can be used to store many different type of elements. They are useful, when you do not have to worry about sorting or ordering.
Consider, you have a properties file to read and keep in memory whenever you application wants to access any property. You can read the file once and store all they key value pairs in a HashMap and keep the map accessible to your code. Then your application can query the map with a specific key and access the associated value in constant amount of time.
Moreover, because of its structure it can be used to hold entire database table in a List<Map<String, Object>>. Where each map in the list represent entire row of a table. Similarly, it can also used to generically hold entire request body in a web application.
Additionally, in below example we will create an User instance and map it to a HashMap using fasterxml library.

1. User user = new User(1L, "Arya", "Stark", 14);
3. ObjectMapper objectMapper = new ObjectMapper();
5. // Covert object to a Map
6. Map<String, Object> objectMap = objectMapper.convertValue(user, Map.class);
8. System.out.println(objectMap);
10. // Output:
11. // {id=1, name=Arya, lastName=Stark, age=14}

Java Collection Frame Work - Map Interface

Map Interface

Map is an Interface in java.utils package. However it does not implements java.utils.Collection interface, but Map is still the part of Collection API you can say it second half of Collection Cinema.

Feature of Map 

• Map is used to store object in key value pair.
• key and value both are Object, Primitive values(int,char etc) not allowed like other Collection .
• Map does not implement Collection interface.
• Like the Set interface Map only allowed unique keys. if you call put(k,v) more than once with same key than latest value replaces the existing value for given key. 
• Value may be repeated
• The key and value represent an  entry of the Map, called entries
• value can be null 
• key can hold one and only null value.
• By default  entries in Map are unordered while some implementation of Map interface provide ordered and sorted entries e.g. TreeMap
• Map are not synchronized while legacy class Hashtable and ConcurrentHashMap are synchronize , performance wise Map is best choice if thread safety is not a matter.
• The Map took constant time to perform operation like get put contains etc because it use hash table algorithm.
• Map is best choice for Mock Implementation.
• if no element exist in Map , it will throw a NoSuchElementException

Internal Storage and Retrieve Strategy of Map

Terminology to know 

bucket - bucket is array 

Map used Hash Table algorithm to store entries. When we put an entry to Map , the Map use hashcode() and equals() method to find associate buckets. it then store entry into the bucket. Different key produce same hashcode value this situation called collision, so they are stored in same buckets.

When we retrieve an entry from Map, we pass the respective key. again hashcode obtain for that key to locate bucket. After locating bucket Map then does the equality check with key when the matched key found map return the value of that keys.

Abstract Method of Map Interface

Add entry to Map<K,V>

• V put(K key, V value) - add an entry to Map, if key is found already in Map then current value is replaced by new value of this key.
• void putAll(Map<? extends K , ? extends V>map) - Copies all the entry from passed map to this map
• default V putIfAbsent(K key, V value): it is default method of Map interface, Checks if the given key is present. If present, returns the existing value and does nothing. If absent, it will store the new entry and return null.

Remove entry from Map<K,V>

• V remove(Object key) - remove the entry from map of given key if it is presented
• default boolean remove(Object key, Object value) - Removes the entry only if the given key has given value in the collection
• default V replace(K key, V value)- Replaces the value of given key with given value. Note: replace happen only if the key is present in the collection
• default boolean replace(K key, V oldValue, V newValue) -  It will replace the value only if the given key has given old value.
• default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) - It applies the given function on all the entries of the collection. 
• Void clear() - clear Map  

Get a Value for given Key

• V get(Object key) - return the value of given key if found , if not found then return null
• deafult V getOrDefault(Object key, V defaultValue) - if given key found in Map return value otherwise return default value. 

Check if map contain a key

• boolean containsKey(Object key) throws ClassCastException, NullPointerException

Check if map contain a value

• boolean containsValue(Object value) throws ClassCastException, NullPointerException

Check if map is empty or not 

• boolean isEmpty()

Iterating the keys of Map

• Set<K> keySet() - retrurned SET view of key contained in the map

Iterating the entries of Map

• Set<Map.Entry<K,V>> entrySet() - returned Set View of entries contained in the map, this method  used for fetching entries from Map.

Iterating the value of Map

• Collection<V> values()

Static Method of Map Interface for Creating Immutable Map

1. static<K,V> Map<K,V> of() method - This is overloaded method , this method is used to create Immutable Map upto 10 entries only

static <K,V> Map<K,V> of (K k1, V v1); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9); 
static <K,V> Map<K,V> of (K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9, K k10, V v10); 

for example : - 

Map<String,String> employee=Map.of("name","Yogesh");

2. static<K,V>Map.Entry<K,V> entry(K k, V v) :  

This method is used Map.Entry type of object.

3.  static<K,V> Map<K,V> ofEntries(Map.Entry<? extends K,?extends V>...) method -  This method take varags of type Map.Entry i.e. if we want to create inline Map of infinite entries then we use ofEntries() method.

for example : - 

Map<String,String> map=Map.ofEntries(

                                                    Map.Entry("Country","India"),

                                                    Map.Entry("Capital","Delhi")

                                            );

Immutable Map : Immutable Map are not modifiable after creation.  Java 9 Provide static method of() and ofEntries() for this purpose. if you try to modified Immutable Map you will get UnsupportedOperationException.

Children of Map Interface

• java.util.SortedMap
• java.util.NavigableMap
• java.util.concurrent.ConcurrentMap
• java.util.concurrent.ConcurrentNavigableMap

Implementation of Map Interface

• AbstractMap
• Attributes
• AuthProvider
• ConcurrentHashMap
• ConcurrentSkipListMap
• EnumMap
• HashMap
• Hashtable
• IdentityHashMap
• LinkedHashMap
• PrinterStateReasons
• Properties
• Provider
• RenderingHints
• SimpleBindings
• TabularDataSupport
• TreeMap
• UIDefaults
• WeakHashMap