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)."
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.
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
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
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); } }
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 :)
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?
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.
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); } }
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
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 😇
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!!
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?
Hi Nabin, I believe the explanation is correct but its important to have a next pointer as well in the node structure of the linkedlist to have multiple nodes for a single index in case of collisions. The major difference of having before and after pointers and a next pointer for a collision scenario should have been a better explanation. Please let me know in case you have any other thoughts. Thanks for the content. - Anshu Bajaj
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?
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. ?
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.
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
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??
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 🙏
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.
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.
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
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 , True that we will have 3 pointers in total which are [before, after] to maintain insertion order and [next] pointer to manage collision scenarios.
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)."
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.
yaeh, even i have same doubt
True that we will have 3 pointers in total which are [before, after] to maintain insertion order and [next] pointer to manage collision scenarios.
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
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
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);
}
}
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 :)
Exactly
If same hashcode here for different keys then? what about collision and threshold applies here.....?
naveen pls reply
Back to back new video 👍😊, thanks for the video Naveen
You explain really well, Thank you so much
nice one Naveen, was waiting for this
what an amazing explanation..Thank you sir
Best explanation 🔥
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?
Hi Naveen, can collision occur in the LinkedHasMap also. In that case what happens to the before and after nodes?
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.
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);
}
}
How the collision is handled in LinkedHashMap?
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
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 😇
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!!
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?
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?
how collisions are handled in this?
Hi Nabin, I believe the explanation is correct but its important to have a next pointer as well in the node structure of the linkedlist to have multiple nodes for a single index in case of collisions. The major difference of having before and after pointers and a next pointer for a collision scenario should have been a better explanation. Please let me know in case you have any other thoughts. Thanks for the content. - Anshu Bajaj
If in case of LinkedHashMap collisions is occured then what will happen?
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?
i also have the same doubt Naveen please help us on this
I am also having same doubt please tell if anyone knows
Nice explanation Naveen! do we have any methods to retrieve the previous node from a particular node since it's implementing doubly-linked lists?
Thank you Naveen 👍
What will be space complexity here for linkedhashmap?
Naveen can you share the collision in case of LinkedHashMap
Sir what happens if index for 2 different keys is same.. Then how the two key value pairs will be stored?
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. ?
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.
Hi Naveen ! Can collision occur in LinkedHashMap? If so, what happens in that case?
same doubt!!!!!
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
EXCELLENT
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??
what happened if we get same index to with different key to store into linked list then how it manage internally?
is there any video for internal working of LinkedHashSet
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 🙏
Does it change to a balanced binary tree once it reaches the threshold 8 nodes?
to the point thank u sir ji
how collision will be handled in case of linkedhashmap ?
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.
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.
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)
It will be the same, an additinal node will be created and doubly linked list pointers will be appropriately updated.
i have one doubt , how exactly its start from 4th index when we executing the entire LHP,
what in case of hash collision ?
in linkedhashmap .. what happens when multiple values are stored in same index
How collisions are handled in linkedhashmap?
what about if a collision occurs?
what is hash collision happened in linkedhashmap
add collision case well.
if same index no then how it will store ??
What will happen in case of collision ? Many people commented this question. We all want reply. Please reply.
What about hash collision
How can we iterate a map which is inside a map? Like HashMap map= new HashMap();
iterator in java
for( Map.Entry outerEntry: map.entrySet()){
for(Map.Entry innerEntry : outerEntry.getValue().entrySet()){
}
}
Can someone share telegram channel link?
t.me/joinchat/COJqZUPB02pj9vVmu8Yv7Q
Nice
First view n comment
I think you dreamed of becoming a doctor, but unfortunately, life forced you to become a developer. Dude, what is this writing style?
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
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?
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.
@@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.