LinkedHashMap implements Map and extends HashMap.Please visit HashMap for understanding the internal working of HashMap before you read further so that it becomes easier to grasp the working of LinkedHashMap.
While HashMap does not maintain insertion order,LinkedHashMap maintains insertion order of key-value pairs by maintaining a doubly Linked List running through all of its entries.
LinkedHashMap uses the below Entry for storing it’s entries.
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
Entry basically contains the following:
K key,
V value,
Entry<K,V> next (i.e. next entry on that location of bucket),
Entry<K,V> before
Entry<K,V> after
Entry<K,V> before and Entry<K,V> after helps in maintaining insertion order.
We will take a very simple example here. Let’s say we want store the population of a city in the Map. Now city name is the key and population is the value. Let us create the below LinkedHashMap for our purpose.
Map<String,Long> map = new LinkedHashMap<String,Long>(4,0.75);
Here we the given the initial capacity as 4 and the load factor as 0.75.A LinkedHasMap with 4 buckets is created. All the buckets initially contain null Entry.
So the Threshold = capacity * load factor = 4 * 0.75 = 3. It means when we will try to put the 4th entry the LinkedHashMap will double it’s capacity to 8.
Let us add the first entry, map.put(“Delhi”,100000);
The first thing to do is to find the bucket.
In Java 8, the bucket index is calculated by the following formula:
Bucket index= (n – 1) & hashcode of key. Here n is the number of buckets. & -> is bitwise AND operator.
In our case, n = 4 and hashcode of Delhi is 65915436(please check hashcode of String class).
Bucket index = 3 & 65915436 = 0, so the entry will go to Bucket 0. Bucket 0 does not have any entry, so the new entry will be put in Bucket 0. The next, before and after all will refer to null.
Let us add the 2nd entry, map.put(“Kolkata”,200000);
Hashcode of Kolkata is 1124159915.
Bucket index = 3 & 1124159915 = 3, so the entry will go to Bucket 3. Bucket 3 does not have any entry, so the new entry will be put in Bucket 3. The before of “Kolkata” entry will refer to the previous “Delhi” entry. The after of the “Delhi” entry will refer to “Kolkata” entry.
Let us put one more entry- 3rd entry, (“Bangalore”,100000); Hashcode of Bangalore is 103869311.Bucket index = 3 & 103869311 = 3.
Now Bucket 3 already contains an entry (“Kolkata”,200000).
LinkedHashMap uses equals() method to check if any entry for the same key is already there in the identified bucket. In our case, it checks if there is already any entry for “Bangalore” in the Bucket 3.In this case, there is no such entry. So Bangalore needs to be put in the Bucket 3.
This leads to hashing collision which means more than one entry in the same bucket.In that case entries are stored in a linked list. So Bangalore entry is set as Next of Kolkata entry.
The before of “Bangalore” entry will refer to the “Kolkata” entry. The after of the “Kolkata” entry will refer to “Bangalore” entry.
So the insertion order is maintained as below.
