When to use linkedhashmap over hashmap in java?

Question

What are the practical scenario for choosing among the linkedhashmap and hashmap? I have gone through working of each and come to the conclusion that linkedhashmap maintains the order of insertion i.e elements will be retrieved in the same order as that of insertion order while hashmap won't maintain order. So can someone tell in what practical scenarios selection of one of the collection framework and why?

Greenlaw

Possible duplicate of Difference between HashMap, LinkedHashMap and TreeMap – Necessarily

A common use for LinkedHashMap is an LRUCache: #23772602 – Athalee

Answer 1

1. LinkedHashMap will iterate in the order in which the entries were put into the map.

2. null Values are allowed in LinkedHashMap.

3. The implementation is not synchronized and uses double linked buckets.

4. LinkedHashMap is very similar to HashMap, but it adds awareness to the order at which items are added or accessed, so the iteration order is the same as insertion order depending on construction parameters.

5. LinkedHashMap also provides a great starting point for creating a Cache object by overriding the removeEldestEntry() method. This lets you create a Cache object that can expire data using some criteria that you define.

6. Based on linked list and hashing data structures with linked list (think of indexed-SkipList) capability to store data in the way it gets inserted in the tree. Best suited to implement LRU ( least recently used ). LinkedHashMap extends HashMap.

It maintains a linked list of the entries in the map, in the order in which they were inserted. This allows insertion-order iteration over the map. That is,when iterating through a collection-view of a LinkedHashMap, the elements will be returned in the order in which they were inserted. Also if one inserts the key again into the LinkedHashMap, the original order is retained. This allows insertion-order iteration over the map. That is, when iterating a LinkedHashMap, the elements will be returned in the order in which they were inserted. You can also create a LinkedHashMap that returns its elements in the order in which they were last accessed.

LinkedHashMap constructors

LinkedHashMap( )

This constructor constructs an empty insertion-ordered LinkedHashMap instance with the default initial capacity (16) and load factor (0.75).

LinkedHashMap(int capacity)

This constructor constructs an empty LinkedHashMap with the specified initial capacity.

 LinkedHashMap(int capacity, float fillRatio)

This constructor constructs an empty LinkedHashMap with the specified initial capacity and load factor.

LinkedHashMap(Map m)

This constructor constructs a insertion-ordered Linked HashMap with the same mappings as the specified Map.

LinkedHashMap(int capacity, float fillRatio, boolean Order)

This constructor construct an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.

Important methods supported by LinkedHashMap

 Class clear( )

Removes all mappings from the map.

containsValue(object value )>

Returns true if this map maps one or more keys to the specified value.

 get(Object key)

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

removeEldestEntry(Map.Entry eldest)

Below is an example of how you can use LinkedHashMap:

Map<Integer, String> myLinkedHashMapObject = new LinkedHashMap<Integer, String>();  
myLinkedHashMapObject.put(3, "car");  
myLinkedHashMapObject.put(5, "bus");  
myLinkedHashMapObject.put(7, "nano");  
myLinkedHashMapObject.put(9, "innova");  
System.out.println("Modification Before" + myLinkedHashMapObject);  
System.out.println("Vehicle exists: " +myLinkedHashMapObject.containsKey(3));  
System.out.println("vehicle innova Exists: "+myLinkedHashMapObject.containsValue("innova"));  
System.out.println("Total number of vehicles: "+ myLinkedHashMapObject.size());  
System.out.println("Removing vehicle 9: " + myLinkedHashMapObject.remove(9));  
System.out.println("Removing vehicle 25 (does not exist): " + myLinkedHashMapObject.remove(25));  
System.out.println("LinkedHashMap After modification" + myLinkedHashMapObject);  

Shy

He asked practical use cases, not how it works. Did you read the question? – Indigent

2. null Values are allowed in LinkedHashMap. -> HashMap also permit null values – Philpot

Answer 2

Shopping Cart is a real life example, where we see cart number against Item we have chosen in order we selected the item. So map could be LinkedHashMap<Cart Number Vs Item Chosen>

Hepatitis

Answer 3

• HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.
• LinkedHashMap will iterate in the order in which the entries were put into the map
• LinkedHashMap also requires more memory than HashMap because of this ordering feature. As I said before LinkedHashMap uses doubly LinkedList to keep order of elements.

Batik

Answer 4

LinkedHashMap maintain insertion order of keys, i.e 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 foot print than HashMap to maintain doubly linked list which it uses to keep track of insertion order of keys.

A HashMap has a better performance than a LinkedHashMap because a LinkedHashMap needs the expense of maintaining the linked list. The LinkedHashMap implements a normal hashtable, but with the added benefit of the keys of the hashtable being stored as a doubly-linked list. Both of their methods are not synchronized. Let's take a look their API documentation:

The HashMap is a hash table with buckets in each hash slot.

API documentation:

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

LinkedHashMap is a linked list implementing the map interface. As said in the API documentation:

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).

Fecundate

what could be the practical scenarios of each? and why we will opt for it? – Greenlaw

Please go through the highlighted part. I hope you will get the answer – Fecundate

Answer 5

In most cases when using a Map you don't care whether the order of insertion is maintained. Use a HashMap if you don't care, and a LinkedHashMap is you care.

However, if you look when and where maps are used, in many cases it contains only a few entries, not enough for the performance difference of the different implementations to make a difference.

Trotman

Answer 6

One way that I have used these at work are for cached backend REST queries. These also have the added benefit of returning the data in the some order for the client. You can read more about it in the oracle docs:

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

This technique is particularly useful if a module takes a map on input, copies it, and later returns results whose order is determined by that of the copy. (Clients generally appreciate having things returned in the same order they were presented.)

A special 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 (access-order). This kind of map is well-suited to building LRU caches. Invoking the put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge methods results in an access to the corresponding entry (assuming it exists after the invocation completes). The replace methods only result in an access of the entry if the value is replaced. The putAll method generates one entry access for each mapping in the specified map, in the order that key-value mappings are provided by the specified map's entry set iterator. No other methods generate entry accesses. In particular, operations on collection-views do not affect the order of iteration of the backing map.

Chromo

Answer 7

People mentioned that LinkedHashMap can serve as the underlying data structure for implementing an LRU (Least Recently Used) cache but nobody provided a code implementation. So here it is.

Explanation for the code below

• In the constructor, we create a LinkedHashMap with accessOrder=true to order entries by access order (get/put) , with the most recently accessed entry at the end of the map.

• When we call get(key):

  • If key exists, it's moved to the end (most recently used). Else, return -1.

• When we call put(key, value):

  • Key-value pair is added/updated.
  • If key exists, its entry is moved to the end.
  • If size exceeds capacity, removeEldestEntry removes the eldest (least recently used) entry.

• removeEldestEntry implementation leverages LinkedHashMap's ordering for LRU cache.

import java.util.*;

class LRUCache {

  // We use a LinkedHashMap as the underlying data structure
  // The third constructor argument, accessOrder=true, ensures that
  // the entries are ordered by their access order (get/put)
  LinkedHashMap<Integer, Integer> linkedHashMap;
  int CAPACITY;

  LRUCache(int capacity) {
    CAPACITY = capacity;

    float loadFactor = 0.75f; // load factor is the measure that decides when to increase the capacity of the Map
    boolean accessOrder = true;
    linkedHashMap = new LinkedHashMap<>(capacity, loadFactor, accessOrder) {
      // This is an anonymous inner class that extends the LinkedHashMap class
      // It overrides the removeEldestEntry method to implement the LRU cache eviction policy

      // The removeEldestEntry method is called by the LinkedHashMap when the map becomes too large
      // It should return true to remove the eldest (least recently used) entry when the cache exceeds its capacity
      protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > CAPACITY;
      }
    };
  }

  int get(int key) {
    // If the key exists, return its value and
    // move it to the end of the map (most recently used)
    return linkedHashMap.getOrDefault(key, -1);
  }

  void set(int key, int value) {
    // Add/update the key-value pair
    // If the key already exists, it will be moved to the end
    // If the size exceeds the capacity after this operation,
    // the eldest entry will be removed
    linkedHashMap.put(key, value);
  }
}

Sarnen