How is the internal implementation of LinkedHashMap different from HashMap implementation?

Question

I read that HashMap has the following implementation:

main array     ↓ [Entry] → Entry → Entry      ← linked-list implementation [Entry] [Entry] → Entry [Entry] [null ] 

So, it has an array of Entry objects.

Questions:

1. I was wondering how can an index of this array store multiple Entry objects in case of same hashCode but different objects.

2. How is this different from LinkedHashMap implementation? Its doubly linked list implementation of map but does it maintain an array like the above and how does it store pointers to the next and previous element?

Answer 1

HashMap does not maintain insertion order, hence it does not maintain any doubly linked list.

Most salient feature of LinkedHashMap is that it maintains insertion order of key-value pairs. LinkedHashMap uses doubly Linked List for doing so.

Entry of LinkedHashMap looks like this-

  static class Entry<K, V> {      K key;      V value;      Entry<K,V> next;      Entry<K,V> before, after;        //For maintaining insertion order          public Entry(K key, V value, Entry<K,V> next){          this.key = key;          this.value = value;          this.next = next;      }   } 

By using before and after - we keep track of newly added entry in LinkedHashMap, which helps us in maintaining insertion order.

Before refers to previous entry and after refers to next entry in LinkedHashMap.

For diagrams and step by step explanation please refer http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

Thanks..!!