• ← Previous
• Next →

We can use a Map to store Key/Value pairs, where key and value are objects; the key/value objects can be same or different objects. One additional constraint is that each "key" in the Map object can at most relate/map/correspond to one "value" -- thus, a Map cannot contain duplicate keys. More details about Map interface is available here. One of the classes that implements the interface Map is an LinkedHashMap; more precisely, the LinkedHashMap class extends HashMap. The LinkedHashMap class implements all the methods defined in the Map interface and so the above behavior of a Map (storing key/value and keys being unique) holds true for the LinkedHashMap as well.

Figure: Map Interface and Class Hierarchy

Before we go into the details of the LinkedHashMap class, let us take a detour and understand the concepts hash tables, load factor, collisions, and hashing function.

A hash table is a popular data structure for doing faster search. In fact, a well-designed hash table can provide an average lookup complexity of O(1). To achieve this fast lookup, a hash table data structure uses a hashing function that maps a given key to one of the indices (also referred to as slots) in the hash-table. For a hash-table, indices are identified using an integer and the hashing function converts the passed key (which can be string, number, an object, etc) into an integer that points to an index in the hash table. In other words, if the hash-table has size S and if the first index is indexed as 0, then we can find the table index, y, such that y would be greater than or equal to 0 but but less than S. You can find additional details about hash table/hash functions in our data structures module: Understanding Hash Tables.

For hash tables, the key consideration (pun intended!) is that it should be able to handle collisions. Well, what is a collision -- you may ask. A collision happens when we have two or more elements get indexed to the same slot. Collisions can potentially increase the time-complexity for lookups. So, a good hashing function must be designed to reduce these collisions. The average lookup complexity of O(1) can become difficult to achieve when there are collisions in the Hashtable.

It is easy to see that if the size of the hash table (let us say, S) is less than the number of entries (let us say, N), then collisions are bound to happen. For an ideal hashing function, if S where to be same as N, then each index would have one entry. In reality, this may not be true and even if N is smaller than S, collisions can still occur! The ratio of N and S does provide an insight into an average number of collisions. This ratio is often known as load factor of the hash table. Load factor is an important consideration for estimating the amount of collisions in a hash table. In an ideal world, the load factor should be always less than 1.0. In fact, its recommended upper limit is around 0.7. For Instance, if an applications intends to store 700 entries, it is recommended to use an Hash table of size/capacity equal to 1000. so that the load factor will be equal to 700/1000 = 0.70 or 70%.

As described above, LinkedHashMap does not allow duplicate keys. However, unlike HashMap, LinkedHashMap preserves the insertion order! So, if the requirement of an application is such that it needs to perform a large number of lookup requests and also the insertion order needs to be maintained, then, the LinkedHashMap would be the way to go!

In terms of data-structures, a LinkedHashMap uses two underlying data-structures: Hash Table and Linked List. LinkedHashMap uses HashTable for quick insertion/removal of elements from the Map and uses LinkedList to preserve the order of insertions. So, how does it work internally? Well, whenever an entry is added to a Hashtable, the same entry is also added to the end of the LinkedList. Since the LinkedList used is a circular double linked List, the insertion/removal operation from a double linked list happens in constant time O(1). When it comes to performance, LinkedHashMap takes slightly more time (for insertions/removals) than a HashMap for the very obvious reason -- it has the overhead of maintaining a linked list. But, when it comes to walking through the Map, LinkedHashMap performs much better.

LinkedHashMap Class Constructors

LinkedHashList class provides four Constructors. We list them in the table below.

Now that we are done with the basic introduction of a LinkedHashMap, let us see an example program to demonstrates their usage.

 import java.util.LinkedHashMap;

 public class LinkedHashMapDemo {
     public static void main(String[] args) {
         LinkedHashMap lhmobj1 = new LinkedHashMap();

         lhmobj1.put(1237,"John");
         lhmobj1.put(2013,"Ray");
         lhmobj1.put(1024,"Mike");
         System.out.println(" Linked Hash Map 1: " + lhmobj1);

         LinkedHashMap lhmobj2 = new LinkedHashMap(lhmobj1);
         System.out.println(" Linked Hash Map 2: " + lhmobj2);

         LinkedHashMap lhmobj3 = new LinkedHashMap(30);
         LinkedHashMap lhmobj4 = new LinkedHashMap(30, (float)0.80);
         LinkedHashMap lhmobj5 = new LinkedHashMap(30, (float)0.80, true);
     }
 }

The above example program creates five new LinkedHashMaps using different constructors. The order of the elements in a LinkedHashMap is preserved and guaranteed. LinkedHashMap objects, lhmobj3, and lhmobj4 are created with a capacity and load factor different from the default values. Notice the map represented by the object "lhmobj5", the constructor takes an extra bool argument, which tells the order in which the Map elements are retrieved. If the argument is "true", the elements in the Map are retrieved in the recently accessed order. If the argument is false, the elements are retrieved in the insertion order.

Let us compile/run the above program. Here is the output:

  Linked Hash Map 1: {1237=Joshn, 2013=Ray, 1024=Mike}
  Linked Hash Map 2: {1237=Joshn, 2013=Ray, 1024=Mike}

LinkedHashMap Class Methods

As we already know, HashMap is one of the Classes that implements the Map interface. So, HashMap class implements all the methods that are defined in the Map interface: put(), putIfAbsent(), putAll(), get(), entrySet(), keySet(), remove(), clear(), replace(), etc. These methods provided by the Map interface are discussed here: Map Interface Methods List. In addition, the LinkedHashMap class extends the HashMap class and overrides the methods. However, it does not define any specific methods.

With that, let us see our next example that demonstrates the usage of the LinkedHashMap methods that are inherited from the Map interface.

 import java.util.LinkedHashMap;

 public class LinkedHashMapDemo2 {
     public static void main(String[] args) {
         LinkedHashMap lhmobj = new LinkedHashMap();

         lhmobj.put(1237,"John");
         lhmobj.put(2013,"Ray");
         lhmobj.put(1024,"Mike");
         int key = 1237;
         System.out.println(" Key: " + key + ", Name: " + lhmobj.get(key));		
         System.out.println(" Value associated with key: " + lhmobj.put(1237,"John2"));
         System.out.println(" All map keys " + lhmobj.keySet());
         System.out.println(" All map Elements " + lhmobj);

         lhmobj.remove(1237);
         System.out.println(" All map Elements " + lhmobj);
     }
 }

Let us no go ahead and compile/run the program. Here is the output:

  Key: 1237, Name: John
  Value associated with key: John
  All map keys [1237, 2013, 1024]
  All map Elements {1237=John2, 2013=Ray, 1024=Mike}
  All map Elements {2013=Ray, 1024=Mike}

• ← Previous
• Next →