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

Prasad Kharkar

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.

22 thoughts on “Working of LinkedHashMap

  • June 7, 2016 at 12:19 pm
    Permalink

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

    Reply
  • Pingback:Working of TreeMap - theJavaGeek

  • June 16, 2016 at 12:56 am
    Permalink

    very crisp and neat.

    Reply
    • June 16, 2016 at 9:23 am
      Permalink

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

      Reply
      • June 29, 2018 at 1:03 pm
        Permalink

        It is one of the best explanation.Can you explain how Get will work in linked hashmap

        Reply
  • Pingback:Core Java Interview Questions – Pankaj Patel

  • October 5, 2016 at 4:12 pm
    Permalink

    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.

    Reply
      • November 25, 2017 at 4:26 pm
        Permalink

        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.

        Reply
        • December 22, 2017 at 12:08 pm
          Permalink

          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

          Reply
  • December 1, 2016 at 4:49 pm
    Permalink

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

    Reply
    • December 4, 2016 at 9:31 am
      Permalink

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

      Reply
  • March 1, 2017 at 10:51 am
    Permalink

    Very good and easy explanation

    Reply
  • July 3, 2017 at 8:57 am
    Permalink

    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.

    Reply
  • January 6, 2018 at 2:31 pm
    Permalink

    Awsome explanation with diagram. Nobody has explained like this.

    Reply
  • February 12, 2018 at 3:36 pm
    Permalink

    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?

    Reply
  • February 24, 2018 at 8:28 pm
    Permalink

    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.

    Reply
  • March 13, 2018 at 1:35 pm
    Permalink

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

    Reply
  • April 12, 2018 at 1:31 pm
    Permalink

    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?

    Reply
  • July 18, 2018 at 8:00 am
    Permalink

    Hi Prasad .

    Good explanation .

    If two elements in the linkedlist finds same hash code then they will get store in the same index but different nodes . this case how it would find the correct order in retrieval .

    for suppose 1st element sits at index 2 and 2nd element sits at index 3 and 3rd element also sits at index 3 and 4th element sits at index 2 and fifth element sits at index 3 based on hash code .

    this case how it maintains insertion order ??

    Reply

Leave a Reply

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