Working of LinkedHashMap

The following two tabs change content below.
Prasad Kharkar is a java enthusiast and always keen to explore and learn java technologies. He is SCJP,OCPWCD, OCEJPAD and aspires to be java architect.

Latest posts by Prasad Kharkar (see all)

Nowadays, there is a lot of stuff going around learning internal working of data structures in java. I’ve seen this kind of question being asked in lot of interviews. We have seen how hashmap put method works internally in java. This article will go further and explain working of LinkedHashMap.

 

Working of LinkedHashMap:

LinkedHashMap is just an extension of HashMap as the class definition is as below

LinkedHashMap contains all functionalities that HashMap provides, even hashing of keys, retrieval is same as HashMap. The difference is when you insert key value pairs in a LinkedHashMap. This is straight from oracle official documentation.

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map

We will take the same example of Bike class that we took in understanding HashMap put method. We have bike class as below.

Another class Demo class which is simply creating a LinkedHashMap instance and putting some objects into it.

Now let us try to understand working of LinkedHashMap thoroughly. It would be recommended to read through HashMap put method

  • When bikes.put(cbr250r, null);  is executed, hash for cbr250r is calculated and is referred by some array index.
  • As LinkedHashMap will provide us the retrieval order as insertion order of elements, it needs to keep track of last inserted object. It has two references head and tail which will keep track of the latest object inserted and the first object inserted.When first object i.e. cbr250r is added then head and tail will both point to same object.
  • When bikes.put(cbr1000rr, null);  is executed, its has value is calculated based on which array index from which it needs to be referred is decided.

We will now see working of LinkedHashMap diagrammatically

Structure of Each Node:

Each node in a LinkedHashMap needs to have information about previous node and next node as the order in which they are accessed in important. The structure is as follows.

Structure of Node

Structure of Node

After inserting cbr250r

  • Just like HashMap, an array of buckets is created which will hold the references to LinkedHashMap objects.
  • As soon as cbr250r is added, head and tail will refer to it. Structure will be as below
cbr250r inserted

cbr250r inserted

After Inserting cbr1000rr:

  • hashcode of cbr1000rr will be different than cbr250r and it will be referred from a different array index.
  • But, as we are inserting cbr1000rr after cbr250r, this information must be present in form of some links.
  • So cbr250r.after will refer to cbr1000rrcbr1000rr.before will refer to cbr250r.
  • head refers to cbr250r and tail refers to cbr1000rr as depicted below.
Second Object Inserted

cbr1000rr Inserted

After Inserting ninja250r

  • cbr1000rr will have next object as ninja250r
  • ninja250r will have previous object as cbr1000rr
  • head will remain unchanged and will refer to cbr250r
  • tail will refer to latest added ninja250r
Ninja250r inserted

Ninja250r inserted

After Inserting ninja1000rr:

Just like above,

  • ninja250r will have ninja1000rr as its next object.
  • ninja1000rr will have ninja250r as its previous object.
  • head will remain unchanged to cbr250r.
  • tail will be ninja1000rr
ninja1000rr inserted

ninja1000rr inserted

I hope the article helped understand the working of LinkedHashMap in java.

Share Button

10 comments for “Working of LinkedHashMap

  1. Supriya
    June 7, 2016 at 12:19 pm

    Absolutely helpful. Simple and put in detail. Looking forward to read more on actual implementation of data structures.

  2. Neeraja
    June 16, 2016 at 12:56 am

    very crisp and neat.

    • June 16, 2016 at 9:23 am

      Thanks a lot Neeraja, any constructive feedback will definitely help me improve more.

  3. October 5, 2016 at 4:12 pm

    So, Doesn’t LinkedHashMap maintain next reference as in HashMap ?? I think before and after are only used for retrieval as per insertion / access order.

    • Rahul
      March 1, 2017 at 10:52 am

      It does.

  4. fakhruddin
    December 1, 2016 at 4:49 pm

    you are awesome man!!!!!!!!!!!!!!!!!!!!!!!!!!!

    • December 4, 2016 at 9:31 am

      I hope I was able to explain clearly 🙂 Do provide me any constructive criticism and I will be happy to improvise.

  5. Rahul
    March 1, 2017 at 10:51 am

    Very good and easy explanation

Leave a Reply

Your email address will not be published. Required fields are marked *