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