How LinkedHashMap maintains order if two or many objects get stored in the same index

Question

If two elements in the linkedlist finds same hash code then they will get store in the same index but different nodes . this case how it would find the correct order .

for suppose 1st element sits at index 2 and 2nd element sits at index 3 and 3rd element also sits at index 3 and 4th element sits at index 2 and fifth element sits at index 3 based on hash code .

this case how it maintains insertion order ??

Look at the source code. The short answer is that there is a *second* linked list that links alls of the entries in the required order. — Stephen C, Jul 18 '18 at 02:41
I don't understand the question. Why would the fact that they're stored in the same bucket make it any harder to maintain order? — shmosel, Jul 18 '18 at 02:41

score 4 · Answer 1 · edited Jun 20 '20 at 09:12

LinkedHashMap is a combination of both a HashMap and a LinkedList.

The HashMap allows quick lookup.
The LinkedList maintains insertion order.

Read the documentation, i.e. the javadoc, which explains this:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)

Please don't confuse the data structure (usually a linked list) that maintains keys that fall into the same hash bucket with the linked list used to maintain insertion order. They are entirely distinct from each other. Besides, recent versions of HashMap uses a tree structure, not a simple linked list, to maintain keys in a hash bucket.

How LinkedHashMap maintains order if two or many objects get stored in the same index

1 Answers1