1

I know how HashMap works and that in the case of hash collisions it forms a Linked List in that bucket. I get that in a LinkedHashMap it maintains insertion order by the 'before' & 'after' fields but how would it maintain the insertion order if there are hash collisions like in a HashMap.

More specifically, the values in the array and any particular bucket could have been inserted at different time intervals, and at the time of retrieving them, wouldn't it be a mess?

Arvind Kumar Avinash
  • 71,965
  • 6
  • 74
  • 110
Sumant Dange
  • 33
  • 5
  • Insertion order doesn't have anything to do with hash collisions. Unclear what you're asking. – user207421 Aug 23 '20 at 09:45
  • Let me provide an example, suppose I initially add 3 values to the LinkedHashMap: a,b,c; on different bucket locations at start, on adding a 4th entry: d, assume it produces a hash collision on bucket index 1. So now the bucket 1 has a linked list (b-d). Now when I want to retrieve the values I would expect a,b,c,d. My question is how does LinkedHashMap retrieve them with their insertion order intact like how does it know where to jump to obtain the value 'd' after retrieving the value 'c'? – Sumant Dange Aug 23 '20 at 11:50
  • The linked list comprising the insertion order is distinct from the linked list for each bucket. – user207421 Aug 24 '20 at 01:31
  • 1
    Do you understand, how the insertion order is maintained when there are no collisions? – Holger Aug 26 '20 at 09:56

2 Answers2

2

A LinkedHashmap maintains a doubly-linked list running through all of its entries. It means that each entry knows the entry inserted before and after itself. Therefore, it doesn't matter which bucket an entry belongs to; while iterating, you get the entries in the order of their insertion.

I am sure you know the concept of Map that it stores entries consisting of a Key-Value pair. However, in your comment, you have mistakenly mentioned about values only.

Arvind Kumar Avinash
  • 71,965
  • 6
  • 74
  • 110
  • As we know LinkedHashMap maintains two linked lists: One doubly-linked list to maintain all the entries in the insertion order and a singly-linked list to support hash-collisions in each bucket, I got your point regarding the doubly-linked list but my doubt is regarding the insertion order of the singly-linked list like how does it maintain the insertion order in the case of hash-collisions since there could be a scenario where I have half-filled it and suddenly hash-collision arrises and the insertion order is interrupted. So how would it resolve this scenario? – Sumant Dange Aug 23 '20 at 14:47
  • 1
    `I got your point regarding the doubly-linked list but my doubt is regarding the insertion order of the singly-linked list...` There should be no doubt if you've understood my answer clearly. Irrespective of how the bucket has been implemented, it is the doubly-linked list running through all of the entries which is responsible to keep track of insertion order. – Arvind Kumar Avinash Aug 23 '20 at 15:48
  • Could you elaborate on the working of both linked lists on how they work together to maintain the insertion order with the help of 'before', 'after', and the 'next' fields? – Sumant Dange Aug 24 '20 at 03:32
  • @SumantDange - A [singly-linked list or a `TreeMap`](https://stackoverflow.com/questions/37959941/what-exactly-is-bucket-in-hashmap) instance is created in a bucket only when a bucket already has an entry and it has to accommodate more entries. On the other hand, the doubly-linked list has no relation with this singly-linked list or a `TreeMap` and is created in case of `LinkedHashmap` to keep track of the entry before and after each entry. I hope, you already know the concept of a doubly-linked list. – Arvind Kumar Avinash Aug 24 '20 at 09:01
0

Each entry is made of before and after Entry object. Even in the case of hash collision, Collided Entry will have its previous Entry. JVM does not need to travers by index of linkedList or the particular bucket. It will directly jump using the after or before Entry.

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);
    }
}
manoj more
  • 1
  • 1