educative.io

Educative

Query on linked hashmap

Suppose, there are 3 elements in the LHM, to be added. A,B,C. be their keys and lets ignore values. Now assume A is added to bucket 2 all the mapping is done.
B is added to bucket 3.

  • A’s after is B, before is null. B’s before is A, after is null.

C is added to bucket 2.

  • B’s after is C, before is A. C’s before is B, after is null.

But where is the link/node that suggests it belongs to bucket 2?
I guess there’s link missing between A and C which belong to same bucket.


Type your question above this line.

Course: https://www.educative.io/collection/6650775272947712/6368023997317120
Lesson: https://www.educative.io/collection/page/6650775272947712/6368023997317120/5844275779076096

Hi @Rajat_Chikkodikar,

Thank you so much for your feedback. Let me explain it for you. Before putting any record in the Linked hash map, the hash value of the provided key for the same record is calculated, and this is where the placement of this particular record is decided as indicated by the provided array of size 16 in the same lesson.

Now, let’s talk about the query, even though, record A and C belong to the same bucket, it doesn’t mean that there must be a connection link between them, it strictly depends on the insertion order. If record C has been inserted after record B then only the after pointer of B will point to the record C and before pointer of record C will point to the record B.

Important to note:
Each entry/node has two links that are before and after, so this data structure can’t manage to have more than two edges. The purpose of the doubly linked list in the hash map is to preserve the insertion order and iterate over them later in the same order, not to connect each node in the same bucket/hash.

Hope that clarifies the confusion.

Happy Learning!

Hello @Abubakkar_Arshad Thanks for taking time and responding. I’ve couple of queries further.

  • Consider I’m adding elements A to J to the LHM. A and J fall in the same bucket (say bucket 1) rest others are in different bucket. Now I want get(“J”). The hashcode is calculated as 1. We check the first element in bucket 1 is A, as there’s no direct pointer to B I’ll have to traverse all the way through A to I and then I’s next is J. Am I right here?

  • If the above is right then LHM is just LinkedList which can hold <K,V> instead of just Value as in case of LL. Then what is the purpose of maintaining buckets in LHM? as it only points to first entry in the bucket and for all further elements we’ll anyway have to traverse the whole list.

Please clarify and thanks again in advance.

@Rajat_Chikkodikar

The major difference between the Linked hash map and hash map is that the Linked hash map preserves the insertion order which hash map doesn’t. As I discussed earlier about the array of buckets of size 16, this array is being used by the doubly linked list to hold all the nodes of Linked hash map in between the hash threshold ranging from 0-15.

Things got a bit weird when there were multiple values against a single key. So to handle this collision of nodes, there is another next pointer in every Linked hash map node that connects all nodes of the same bucket based on the hash value formulation. By calling the get function, you will get the hash value and then you will iterate over all the sub nodes of the bucket connected through the next pointer in order to find the desired node. The doubly linked list is a feature of the Linked hash map that tracks insertion order and mainly used for traversals rather than anything else. The simple hash map uses a vector or a list o handle the same thing, but Linked hash map sticks with this type of a reference list.

Hope that clarifies the confusion.

Understood! So simply put there are 3 pointers in total. Before and after are used for traversing in insertion order, while another pointer next is used to traverse through bucket.

Thanks a lot @Abubakkar_Arshad @fahim for such good content!

@Rajat_Chikkodikar

You are welcome!

1 Like