How is the internal implementation of LinkedHashMap different from HashMap implementation?

Question

I read that HashMap has the following implementation:

main array 
   ↓
[Entry] → Entry → Entry      ← linked-list implementation
[Entry]
[Entry] → Entry
[Entry]
[null ]

So, it has an array of Entry objects.

Questions:

1. I was wondering how can an index of this array store multiple Entry objects in case of same hashCode but different objects.

2. How is this different from LinkedHashMap implementation? Its doubly linked list implementation of map but does it maintain an array like the above and how does it store pointers to the next and previous element?

Answer 1

HashMap does not maintain insertion order, hence it does not maintain 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 refers 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

Thanks..!!

Answer 2

So, it has an array of Entry objects.

Not exactly. It has an array of Entry object chains. A HashMap.Entry object has a next field allowing the Entry objects to be chained as a linked list.

I was wondering how can an index of this array store multiple Entry objects in case of same hashCode but different objects.

Because (as the picture in your question shows) the Entry objects are chained.

How is this different from LinkedHashMap implementation? Its doubly linked list implementation of map but does it maintain an array like the above and how does it store pointers to the next and previous element?

In the LinkedHashMap implementation, the LinkedHashMap.Entry class extends the HashMap.Entry class, by adding before and after fields. These fields are used to assemble the LinkedHashMap.Entry objects into an independent doubly-linked list that records the insertion order. So, in the LinkedHashMap class, each entry object is in two distinct chains:

• There are a number of singly linked hash chains that is accessed via the main hash array. This is used for (regular) hashmap lookups.

• There is a separate doubly linked list that contains all of the entry objects. It is kept in entry insertion order, and is used when you iterate the entries, keys or values in the hashmap.

Answer 3

Take a look for yourself. For future reference, you can just google:

java LinkedHashMap source

HashMap uses a LinkedList to handle collissions, but the difference between HashMap and LinkedHashMap is that LinkedHashMap has a predicable iteration order, which is achieved through an additional doubly-linked list, which usually maintains the insertion order of the keys. The exception is when a key is reinserted, in which case it goes back to the original position in the list.

For reference, iterating through a LinkedHashMap is more efficient than iterating through a HashMap, but LinkedHashMap is less memory efficient.

In case it wasn't clear from my above explanation, the hashing process is the same, so you get the benefits of a normal hash, but you also get the iteration benefits as stated above, since you're using a doubly linked list to maintain the ordering of your Entry objects, which is independent of the linked-list used during hashing for collisions, in case that was ambiguous..

EDIT: (in response to OP's comment):
A HashMap is backed by an array, in which some slots contain chains of Entry objects to handle the collisions. To iterate through all of the (key,value) pairs, you would need to go through all of the slots in the array and then go through the LinkedLists; hence, your overall time would be proportional to the capacity.

When using a LinkedHashMap, all you need to do is traverse through the doubly-linked list, so the overall time is proportional to the size.

Answer 4

Since none of the other answers actually explain how something like this could be implemented I'll give it a shot.

One way would be to have some extra information in the value (of the key->value pair) not visible to the user, that had a reference to the previous and next element inserted into the hash map. The benefits are that you can still delete elements in constant time removing from a hashmap is constant time and removing from a linked list is in this case because you have a reference to the entry. You can still insert in constant time because hash map insert is constant, linked list isn't normally but in this case you have constant time access to a spot in the linked list so you can insert in constant time, and lastly retrieval is constant time because you only have to deal with the hash map part of the structure for it.

---

Keep in mind that a data structure like this does not come without costs. The size of the hash map will rise significantly because of all the extra references. Each of the main methods will be slightly slower (could matter if they are called repeatedly). And the indirection of the data structure (not sure if that's a real term :P) is increased, though this might not be as big a deal because the references are guaranteed to be pointing to stuff inside the hash map.

---

Since the only advantage of this type of structure is that it preserves order be careful when you use it. Also when reading the answer keep in mind I don't know that this is the way it's implemented but it is how I would do it if given the task.

---

On the oracle docs there is a quote confirming some of my guesses.

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.

Another relevant quote from the same website.

This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

Answer 5

hashCode will be mapped to any bucket by the hash function. If there is a collision in hashCode than HashMap resolve this collision by chaining i.e. it will add the value to the linked list. Below is the code which does this:

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392             Object k;
393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394         `enter code here`        V oldValue = e.value;
395                 e.value = value;
396                 e.recordAccess(this);
397                 return oldValue;
398             }
399         }

You can clearly see that it traverse the linked list and if it finds the key than it replaces the old value with new else append to the linked list.

But the difference between LinkedHashMap and HashMap is LinkedHashMap maintains the insertion order. From docs:

This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation).