#14 - linkedhashmap vs hashmap in Java || How LinkedHashMap works internally - Naveen AutomationLabs

[@arvindhr.a2315]

Great Video Naveen sir ! Can you add some comments or a short video for collision in linked hashmap ? I see many folks have requested for the same . if you could, it would be great :)

[@rishibharadwaj68]

Good to see a video on the internal implementation of a Collection class! But, I have an interesting question here : What if 2 keys have the same hashCode? As per your logic, they will generate same index. How will you store 2 nodes under the same segment(bucket)? I think instead of 2 pointers the nodes must have 3 pointers. 1. BackwardNode 2. ForwardNode 3. NextNode to point to a Node belonging to the same index(bucket). Not sure if LinkedHashSet is implemented this way. Would like to hear from you.

[@ayushraj-zb6sv]

yaeh, even i have same doubt

[@BitExplorer]

True that we will have 3 pointers in total which are [before, after] to maintain insertion order and [next] pointer to manage collision scenarios.

[@NehaSingh-um5ib]

suppose we have 2 keys with same hashcode key1 and key2 so ....key 1's after node will connect to keys 2's before node and key 2's after node will combine to key of another segment

[@hardiknegi435]

Will collision not be handled like it is handled in normal Maps? like a new Node at same index will be created with its Before Pointer pointing to already present node's After Pointer and new node's Next pointer will point to previous node's after pointer

[@thanga2317]

Thanks for the explanation Naveen. You should've explained about Entry which is wrapper of Node. HashMap.Node subclass for normal LinkedHashMap entries. static class Entry extends HashMap.Node { Entry before, after; Entry(int hash, K key, V value, Node next) { super(hash, key, value, next); } }

[@nehasinghal3785]

How the collision is handled in LinkedHashMap?

[@imdadkhan5047]

Neha in case of collision in linkedhashmap it will simply create one single linkedlist and once the threshold value is reached it will be converted into a balanced binary tree

[@mohdrasid6737]

There will be one more link of name "next", which will store the address of next node of the same bucket(segment). There will be total of 6 fields as below- before - store the address of the node which was just created before this new node node. key - key of the (key - value) pair hash - hash code of the key value - value of (key - value) pair after - store the address of the node which is just created after this node. next - store the address of the next node of the same bucket(segment). so , before and after - are used to maintain insertion order . but "next" is used to main all nodes of the same bucket (segment). Thanks 😇

[@user-fl5iv6nr2k]

Hello @Naveen, I have one question regarding linkedHashMap, as per your explanation, does this mean 1 segment will have only one node created at any given point unlike HashMap where we could have maximum 8 nodes per segment?

[@ramyagunaseelan9435]

If same hashcode here for different keys then? what about collision and threshold applies here.....? naveen pls reply

[@SiyaliShiya]

Hi, Thank you for the explanation, but I have a question when a collision occurs how the behavior be? because we are already pointing before and after node?

[@bharathreddy8918]

how collisions are handled in this?

[@aleksandrefimov8754]

Just copied info from the most helpful comments below about the case of collision in LinkedHashMap. Hope it will help you) "In case of collision in linkedhashmap it will simply create one single linkedlist and once the threshold value is reached it will be converted into a balanced binary tree" - the same principle as in HashMap "There will be one more link of name "next", which will store the address of next node of the same bucket(segment). There will be total of 6 fields as below- -before - store the address of the node which was just created before this new node node. -key - key of the (key - value) pair -hash - hash code of the key -value - value of (key - value) pair -after - store the address of the node which is just created after this node. -next - store the address of the next node of the same bucket(segment). so , before and after - are used to maintain insertion order . but "next" is used to main all nodes of the same bucket (segment)."

[@dikshabaluja]

You explain really well, Thank you so much

[@mollamainuddin6485]

If in case of LinkedHashMap collisions is occured then what will happen?

[@socialmedia434]

Hi Naveen, can collision occur in the LinkedHasMap also. In that case what happens to the before and after nodes?

[@uigreseu5756]

I believe that a nod also has and a link which connects two nodes in the same index. in case that in an index are two nodes then this link also will connect them. Hope this the answer to your question.

[@thanga2317]

He missed those points: HashMap.Node subclass for normal LinkedHashMap entries. static class Entry extends HashMap.Node { Entry before, after; Entry(int hash, K key, V value, Node next) { super(hash, key, value, next); } }

[@manikandan2890]

what an amazing explanation..Thank you sir

[@SarangHoley]

Back to back new video 👍😊, thanks for the video Naveen

[@chetanpalekar376]

Hi Naveen, Thank you for this explanation. Just a quick query, what happens here, if the segment index of the second value I am inserting is calculated to be the same as the index of the first value? In your HashMap implementation video example you have had mentioned that the segment index of different values can be the same. Is is not the same for LinkedHashMap? Thanks!!

[@moonshine4757]

I've same doubt. If index is based on how we insert, what's the use of hash code? Also what about Collison. Did you clear your doubt?

[@Vishalfootball]

nice one Naveen, was waiting for this

[@nirmalabiradar2704]

Thank you Naveen 👍

[@Shreenidhi110]

I have one doubt: what if the aftr calulating index value for 1st entry is 3 and 2nd entry its 1 ,then what will be the insertion order?I am confused here

[@sureshgarine]

Nice explanation Naveen! do we have any methods to retrieve the previous node from a particular node since it's implementing doubly-linked lists?

[@mohammedadnan984]

Best explanation 🔥

[@dineshkumarpanda7287]

I have one doubt, could you please explain- why hashmap doesn't maintain order and why linkedhashmap maintains order. As both uses linkedlist to store elements.

[@manichowdry547]

EXCELLENT

[@ankitmahajan8295]

to the point thank u sir ji

[@mrudulaahire1360]

What will be space complexity here for linkedhashmap?

[@xoda345]

what is the purpose of calculating index in linkedhashmap bcause all the nodes are divided in 4 partition which contains - before address, key,value and after address. Where do the index or the hashcode gets stored? So how would the JVM know which index is assigned to which node??

[@MumPuneMum]

Thanks boss for such explanation. 1 quick doubt - what if the hashcode are same ? like if we get 1 more similar hashcode at index 4th .. how it handles the before and after node of previous segment?

[@nandhinimathivanan3998]

i also have the same doubt Naveen please help us on this

[@sujeetkumar-dt7xk]

I am also having same doubt please tell if anyone knows

[@kumarjadhav6106]

is there any video for internal working of LinkedHashSet

[@moonshine4757]

Since index is decided is based on hash code, how is it ordered collection ? What if some key get index of 2 (which is inserted in the end) & what about Collison? Doesn't it happen here?? I understood o/p will be just like i/p tho.

[@RajkumarVishwakarma]

Sir what happens if index for 2 different keys is same.. Then how the two key value pairs will be stored?

[@superbbcfan]

Hi Naveen ! Can collision occur in LinkedHashMap? If so, what happens in that case?

[@kishorekisu6357]

same doubt!!!!!

[@sheshankgolli2667]

While we are inserting next elements, if we get index is lesser than the previous node, how they will connect before and after and maintains the insertion order. ?

[@kanishkasrivastava9108]

and what will happen when collision happens. Even in HashMap values are stored in the same way. What's the difference between HashMap and LinkedHashMap.

[@TheRajatsaluja]

Naveen can you share the collision in case of LinkedHashMap

[@dasarimanasvi128]

i have one doubt , how exactly its start from 4th index when we executing the entire LHP,

[@kishorekisu6357]

in linkedhashmap .. what happens when multiple values are stored in same index

[@ashishupadhyay8360]

What will happen in case of collision ? Many people commented this question. We all want reply. Please reply.

[@atifpall2007]

Naveen sir how do we handle collision concept here like we discussed in hashMap videos. How the nodes will be created if the indexes are same ? How the get() will work for duplicate indexes? Thank you 🙏

[@atifpall2007]

Does it change to a balanced binary tree once it reaches the threshold 8 nodes?

[@sahuamit30]

how collision will be handled in case of linkedhashmap ?

[@sovanghosh2524]

what about if a collision occurs?

[@rahulsuthar319]

what in case of hash collision ?

[@amolchaure6309]

what happened if we get same index to with different key to store into linked list then how it manage internally?

[@prernach417]

add collision case well.

[@rajatroy100]

How collisions are handled in linkedhashmap?

[@blaxminarayanpatra7311]

if same index no then how it will store ??

[@akashingle3404]

Nice

[@sssrinivas1]

How can we iterate a map which is inside a map? Like HashMap map= new HashMap();

[@emilyding4676]

iterator in java

[@karwannouri8266]

for( Map.Entry outerEntry: map.entrySet()){ for(Map.Entry innerEntry : outerEntry.getValue().entrySet()){ } }

[@glennmaxi7542]

what is hash collision happened in linkedhashmap

[@venkatramanhiregange9096]

What happens if we get same hashcode for the keys?(like in in hash map it maintains the linked list in case hashcode is same)

[@profitableloser3879]

It will be the same, an additinal node will be created and doubly linked list pointers will be appropriately updated.

[@suminshakya5067]

What about hash collision

[@JeetenGandhi]

Can someone share telegram channel link?

[@ai_pni]

t.me/joinchat/COJqZUPB02pj9vVmu8Yv7Q

[@godoffortuneful]

First view n comment

[@berkanyildiz5343]

I think you dreamed of becoming a doctor, but unfortunately, life forced you to become a developer. Dude, what is this writing style?

[@abhineetgarg2045]

why is it required to maintain the previous node when you are not retrieving it? And what if there will be a collision then you will lost the hash concept too.. it will work like linked arraylist if collision starts. Totally disagree with the concept

[@naveenautomationlabs]

Your understanding is wrong about this concept. And why do u think in case of collision you will be loosing hash concept? And first of all its not linekdArraylist (its not even exist), it's a doubly Linkedlist. FYI, this is the internal implementation of LinkedHashMap in java library, so you are not agree with Java or with the concept? And If you don't agree, please explain why r u not agree with this concept? And what solution you propose to maintain an insertion order for maps?

[@naveenautomationlabs]

And you need to maintain the previous node so that you can maintain the insertion order. That's the property of LinkedHashMap as compared to hashmap.

[@BitExplorer]

@@naveenautomationlabs , True that we will have 3 pointers in total which are [before, after] to maintain insertion order and [next] pointer to manage collision scenarios.