Monday, 9 November 2015

LinkedHashMap in Java

LinkedHashMap is also one of the implementation of the Map interface, apart from implementing Map interface LinkedHashMap also extends the HashMap class. So just like HashMap, LinkedHashMap also allows one null key and multiple null values.

How it differs from other implementations of the Map interface like HashMap and TreeMap is that LinkedHashMap maintains the insertion order of the elements which means if we iterate a LinkedHashMap we'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).

How LinkedHashMap is implemented

LinkedHashMap is the Hash table and linked list implementation of the Map interface. It maintains a doubly-linked list running through all of its entries and that's how it maintains the iteration order. Apart from maintaining a doubly linked list the internal implementation of the LinkedHashMap is same as the internal implementation of the HashMap.

LinkedHashMap example code

public class LinkedHashMapDemo {

    public static void main(String[] args) {
        // Creating LinkedHashMap
        Map<String, String> cityTemperatureMap = new LinkedHashMap<String, String>();
        
        // Storing elements
        cityTemperatureMap.put("Delhi", "24");
        cityTemperatureMap.put("Mumbai", "32");
        cityTemperatureMap.put(null, "26");
        cityTemperatureMap.put("Chennai", "35");
        cityTemperatureMap.put("Bangalore", "22" );
        cityTemperatureMap.put(null, "34");
        cityTemperatureMap.put("Kolkata", "28");
        cityTemperatureMap.put("Chennai", "36");
        
        // iterating the map
        for(Map.Entry<String, String> me : cityTemperatureMap.entrySet()){
            System.out.println(me.getKey() + " " + me.getValue());
        }
    }
}

Output

Delhi 24
Mumbai 32
Bangalore 22
null 34
Kolkata 28
Chennai 36

Points to note here

  • It can be seen that the insertion order is maintained. While iterating the LinkedHashMap elements are displayed in the order they were inserted.
  • Even though two null keys were inserted only one is stored (only one null key is allowed in map).
  • Two values were inserted with the same key "Chennai" which results in the overwriting of the old value with the new value (as the calculated hash will be the same for the keys). Thus the last one is displayed while iterating the values.

Use of LinkedHashMap as Least Recently Used Cache

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

General form of the constructor

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
Lets see an example with this constructor
public class LinkedHMAccessOrder {
    public static void main(String[] args) {
        Map<String, String> cityMap = new LinkedHashMap<String, String>(16, 0.75f, true);
        cityMap.put("1","New York City" );
        cityMap.put("2", "New Delhi");
        cityMap.put("3", "Newark");
        cityMap.put("4", "Newport");
        System.out.println("" + cityMap.get("1"));
        System.out.println("" + cityMap.get("4"));
        for(Map.Entry<String, String> me : cityMap.entrySet()){
            System.out.println(me.getKey() + " " + me.getValue());
        }
    }
}

Output

New York City
Newport
2 New Delhi
3 Newark
1 New York City
4 Newport

Here it can be seen that access-order parameter is passed as true, that means ordering mode is Access order, if passed as false that would mean ordering mode is insertion order.

Since keys "1" and "4" are used so while iterating the map these two keys as displayed later as the access order is "from least-recently accessed to most-recently".

LinkedHashMap is not synchronized

LinkedHashMap is not thread safe. In case we need to Synchronize it, it should be synchronized externally. That can be done using the Collections. synchronizedMap method.

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

LinkedHashMap class' iterator is fail-fast

The iterators returned by this class' iterator method are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.

That's all for this topic LinkedHashMap in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

Source: http://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html


Related Topics

  1. How HashMap internally works in Java
  2. Treemap in Java
  3. How to loop through a map in Java
  4. ConcurrentHashMap in Java
  5. LinkedHashSet in Java
  6. fail-fast Vs fail-safe iterator in Java
  7. Java Collections interview questions

You may also like -

2 comments:

  1. please explain this "LinkedHashMap is the Hash table and linked list implementation of the Map interface"

    ReplyDelete
    Replies
    1. I guess you are getting confused between HashTable and hash table.
      https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html If you see there it says "HashTable class implements a hash table, which maps keys to values". So all implementations of Map interface are hash table implementations and HashTable class is also implements hash table. It also implements linked list that's how it maintains insertion order.

      Delete