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

20 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.

      • Ashish khare
        November 25, 2017 at 4:26 pm

        Please correct me if I am wrong but your entry object should have 5 elements basically. Key, Value, Next, After and Previous.

        All elements represented as having hashcode mapped to index 8 should be connected with next pointer and same applied to elements having hashcode mapped to index 10. After and Previous will be used for iterating over values else next pointer will be used to store key-value pair in the actual bucket index in order to store each new value coming to already filled bucket index.

        • Santosh
          December 22, 2017 at 12:08 pm

          Yes Ashish, you are right. The “Entry” class in LinkedHashMap extends HashMap.Entry.
          So it has the next pointer, and also these 2 in addition – the before & after pointers

  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

  6. Prasad
    July 3, 2017 at 8:57 am

    Nice article!! My constructive feedback is there is a typo of hash in the sentence: 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.

  7. Rahotman
    January 6, 2018 at 2:31 pm

    Awsome explanation with diagram. Nobody has explained like this.

  8. Ashish Bhatia
    February 12, 2018 at 3:36 pm

    LinkedHashmap retrieval should be o(1). in the example give above if i try to retrieve ninja250r . Its not o(1) because you will map to index 8 and then basically you traverse forward. Am i missing something?

  9. sumit
    February 24, 2018 at 8:28 pm

    Hi Prasad Kharkar,
    Its so good to learn this concept as you explained very sort ,neat and clear.
    I am glad to learn more thing from you, as the way you explain is very good.

  10. Dinesh Yadav
    March 13, 2018 at 1:35 pm

    Wow ! kya baat hai…Nicely explained i am very greatful to you becoz i learned in one shot…Thanks buddy

    • March 13, 2018 at 10:53 pm

      Thank you, keep providing constructive feedback

  11. Onkar Ketkar
    April 12, 2018 at 1:31 pm

    I have not come across such a simple and neat explanation. Great job!!!
    IT would be great if you can clear the point discussed regarding next pointers of the nodes.
    Is there anything maintained like that?

Leave a Reply

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