Why iteration through buckets in LinkedHashMap is faster than HashMap?

Question

I am struggling a lot to understand this.

Googling, I found

"HashMap iterator has to iterate through all the buckets including empty buckets"

and

"in LinkedHashMap all the entries are doubly linked".

If this is the case why the only HashMap has to iterate through empty buckets, but not LinkedHashMap, though both were implemented using the same buckets concept? All the entries are doubly linked in sense "all the buckets and elements are doubly linked" or only the "the elements are doubly linked".

Please provide me with a diagram explaining doubly linked buckets implementation in LinkedHashMap.

Many thanks in advance.

Answer 1

LinkedHashMap bucket nodes(entry) hold extra two pointers(before, after) for maintaining order.

This is the structure when it's created.

Map<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>();

Now let's add one element to it.

linkedHashMap.put(1, "obj1");

here linkedHashMap header before, after is pointing to entry object.

let's add another element to it.

linkedHashMap.put(15, "obj15");

check out the pointer changes with previous state in red color

let's add one more element.

linkedHashMap.put(4, "obj4");

and next pointer in each entry to form SingleLikedList when another entry inserted with the same hash.

Answer 2

The whole point of LinkedHashMap is to have a separate linked list of nodes (only; the buckets themselves are not linked) to iterate through, so that you could have a predictable iteration order. So yes, LinkedHashMap can be faster to iterate through.

To answer your question about "though both were implemented using the same buckets concept": HashMap has only a hash table, whereas a LinkedHashMap has both a hash table and a linked list; by-key lookups use the hash table and iterations use the linked list.

The tradeoff with LinkedHashMap is that you have to keep an extra linked list (in addition to the hash table, which both HashMap and LinkedHashMap have), which is extra space usage.