Java Hashmap Tail Traversing

Question

What does tail traversing mean in Java Hashmap? Java reverses the (linked list) bucket having more than one element. The reversal is done to avoid Tail Traversing and adding an element to the head. I cannot understand this concept.

Answer 1

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