Java Hashmap Tail Traversing

To answer Sufian's question. Yes you are correct for traversal we need to traverse the whole linked list. But this thread is solely related to hash collision resolution. One of the the method to solve has collision is to restructure the whole linked list that is stored in a bucket. So hashmap creates a new linkedlist from the old one. and this TRAIL TRAVERSING happens only during that time of recreation.

I came to this blog searching for an answer about what tail traversal is and now i had an Epiphany

Dhananjayan, what this basically means is that tail traversing is a concept in linked list. i will try to explain this with an example. lets say you want to add the following elements to a singly linked list

23, 65, 44, 12, 90

Ok fine now. you have added 5 elements. so after some time , you need to add a new element 10. so if our algorithm adds elements to end of linked list, it has to traverse through theese five elements to find the tail which can be quite expensive in case of lengthy linked lists. so one efficient way is to add new elements to head instead of tail and change the head pointer to point to new head.so in this case when you add a new element 10, linked list would look like following

10, 23, 65, 44, 12, 90

As you can see, this is a very efficient approach.

I will answer your second question now(What do they mean by reversing?) So in hashmap when they resize/rehash, they pull up elements from linked list starting from head and make a new linked list and add subsequent elements in order so on each iteration the result will be

• 10
• 23 10
• 65 23 10
• 44 65 23 10

• 12 44 65 23 10

• 90 12 44 65 23 10

so this is the result of adding new elements to head In short this is a LIFO(Last in First out) structure.

Philip