Difference between HashMap and LinkedHashMap in Java

Difference between LinkedHashMap and HashMap in Java
HashMap and LinkedHashMap are two of the most commonly used Map implementation in Java. The main difference between HashMap and LinkedHashMap is that LinkedHashMap maintains the insertion order of keys, the order in which keys are inserted into LinkedHashMap. On the other hand, HashMap doesn't maintain any order or keys, or values. In terms of performance, there is not much difference between HashMap and LinkedHashMap but yes LinkedHashMap has more memory footprint than HashMap to maintain doubly LinkedList which it uses to keep track of the insertion order of keys. 

Sometimes you notice that HashMap also returns elements in order e.g. before Java 8 when you use the Integer key and then iterate over Map, you would see it returning entries in a particular order, but those are not guaranteed. 

Any code which is dependent upon ordering provided by HashMap will likely break in a future release when that behavior changes.

LinkedHashMap and HashMap in Java - Similarities

There are a lot of similarities between LinkedHashMap and HashMap in Java, as they both implement Map interface.  let's have a look :

1. Thread safety

 Both LinkedHashMap and HashMap are not synchronized and subject to race conditions if shared between multiple threads without proper synchronization. You can also use Collections.synchronizedMap() for making them synchronized.


2. Fail Fast Iterator

Iterator returned by HashMap and LinkedHashMap is fail-fast in nature.


3. Performance

The performance of HashMap and LinkedHashMap are similar also.

Difference between LinkedHashMap and HashMap in Java

Now let's see some differences between LinkedHashMap and HashMap in Java:


1. Order

The first and foremost difference between LinkedHashMap and HashMap is order, HashMap doesn't maintain any order while LinkedHashMap maintains the insertion order of elements in Java.


2. Memory Requirement

LinkedHashMap also requires more memory than HashMap because of this ordering feature. As I said before LinkedHashMap uses doubly LinkedList to keep the order of elements.


3. Class Hierarchy

 LinkedHashMap actually extends HashMap and implements the Map interface.

Here is how LinkedHashMap is implemented in Java, which is also important to understand for Java developers. 

Few things to note, while using LinkedHashMap in Java 

Here are a couple of important things to note while using LinkedHashMap in Java :

1. Default ordering provided by LinkedHashMap is the order on which key is inserted, known as insertion order, but LinkedHashMap can be created with another ordering called access order, which is defined by accessing entries.

2. Re-entering a mapping, doesn't alter the insertion order of LinkedHashMap. For example, if you already have mapping for a key, and want to update its value by calling put(key, newValue), the insertion order of LinkedHashMap will remain the same.

3. Access order is affected by calling get(key), put(key, value), or putAll(). When a particular entry is accessed, it moves towards the end of the doubly linked list, maintained by LinkedHashMap.

4. LinkedHashMap can be used to create an LRU cache in Java. Since in LRU or Least Recently Used Cache, the oldest non accessed entry is removed, which is the head of the doubly linked list maintained by LinkedHashMap.

5. Iterator of LinkedHashMap returns elements in the order e.g. either insertion order or access order.

6. LinkedHashMap also provides a method called removeEldestEntry(), which is protected, and default implementation return false. If overridden, an implementation can return true to remove the oldest entry, when a new entry is added.

Given the insertion order guarantee of LinkedHashMap, It's a good compromise between HashMap and TreeMap in Java because with TreeMap you get increased cost of iteration due to sorting and performance drops on to log(n) level from constant time. That's all about the difference between LinkedHashMap and HashMap in Java.

Further Learning
Difference between TreeSet and HashSet in Java
Difference between HashMap and ArrayList in Java

And lastly one question for you? What is difference between HashMap and ConcurrentHashMap in Java? how does ConcurrentHashMap achieves thread safety and better performance then synchronized HashMap?