How is the implementation of LinkedHashMap different from HashMap?

If LinkedHashMap's ti开发者_StackOverflowme complexity is same as HashMap's complexity why do we need HashMap? What are all the extra overhead LinkedHashMap has when compared to HashMap in Java?

LinkedHashMap will take more memory. Each entry in a normal HashMap just has the key and the value. Each LinkedHashMap entry has those references and references to the next and previous entries. There's also a little bit more housekeeping to do, although that's usually irrelevant.

If LinkedHashMap's time complexity is same as HashMap's complexity why do we need HashMap?

You should not confuse complexity with performance. Two algorithms can have the same complexity, yet one can consistently perform better than the other.

Remember that f(N) is O(N) means that:

limit(f(N), N -> infinity) <= C*N  

where C is a constant. The complexity says nothing about how small or large the C values are. For two different algorithms, the constant C will most likely be different.

(And remember that big-O complexity is about the behavior / performance as N gets very large. It tells you nothing about the behavior / performance for smaller N values.)

Having said that:

• The difference in performance between HashMap and LinkedHashMap operations in equivalent use-cases is relatively small.

• A LinkedHashMap uses more memory. For example, the Java 11 implementation has two additional reference fields in each map entry to represent the before/after list. On a 64 bit platform without compressed OOPs the extra overhead is 16 bytes per entry.

• Relatively small differences in performance and/or memory usage can actually matter a lot to people with performance or memory critical applications¹.

^{1 - ... and also to people who obsess about these things unnecessarily.}

• LinkedHashMap additionally maintains a doubly-linked list running through all of its entries, that will provide a reproducable order. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
• HashMap doesn't have these extra costs (runtime,space) and should prefered over LinkedHashMap when you don't care about insertion order.

LinkedHashMap is a useful data structure when you need to know the insertion order of keys to the Map. One suitable use case is for the implementation of an LRU cache. Due to order maintenance of the LinkedHashMap, the data structure needs additional memory compared to HashMap. In case insertion order is not a requirement, you should always go for the HashMap.

There is another major difference between HashMap and LinkedHashMap :Iteration is more efficient in case of LinkedHashMap.

As Elements in LinkedHashMap are connected with each other so iteration requires time proportional to the size of the map, regardless of its capacity. But in case of HashMap; as there is no fixed order, so iteration over it requires time proportional to its capacity.

I have put more details on my blog.

HashMap does not maintains insertion order, hence does not maintains 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 refer 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

LinkedHashMap inherits HashMap, that means it uses existing implementation of HashMap to store key and values in a Node (Entry Object). Other than this it stores a separate doubly linked list implementation to maintain the insertion order in which keys have been entered.

It looks like this :

header node <---> node 1 <---> node 2 <---> node 3 <----> node 4 <---> header node.

So extra overload is maintaining insertion and deletion in this doubly linked list. Benefit is : Iteration order is guaranteed to be insertion order, which is not in HashMap.

• Re-sizing is supposed to be faster as it iterates through its double-linked list to transfer the contents into a new table array.
• containsValue() is Overridden to take advantage of the faster iterator.
• LinkedHashMap can also be used to create a LRU cache. A special LinkedHashMap(capacity, loadFactor, accessOrderBoolean) constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently. In this case, merely querying the map with get() is a structural modification.