CODEWITHSUNDEEP
javacollectionshashmaplinkedhashmap
Dipesh Gupta
Dipesh Gupta

Reputation: 799

What is the time complexity of retrieving an element from LinkedHashMap in case of collision?

Suppose that I have a LinkedHashMap object with only 8 buckets numbered from 0 to 7. Now I want to add elements. I added 7 elements and the result is as follows:

1) Element_1: Bucket number 2. This becomes the starting of the linked list which LinkedHashMap maintains to maintain the insertion order.
1) Element_2: Bucket number 3. This is linked to Element_1
2) Element_3: Bucket Number 1. This is linked to Element_2
3) Element_4: Bucket Number 4. This is linked to Elemetn_3
4) Element_5: Bucket Number 5. This is linked to Element_4
5) Element_6: Bucket Number 3. This is linked to Element_5 (Collision has occurred)
6) Element_7: Bucket Number 3. This is linked to Element_6(Again a collision)

Now suppose I want to retrieve Element_7. The hashing of this element gives me bucket number 3. Now the elements in bucket number 3 are Element_2, Element_6, Element_7.
So what is the order of traversal of the following two:
a) Element_2-> Element_3->Element_4->Element_5->Element_6->Element_7.
OR
b) Element_2->Element_6->Element_7.

I thought that the answer would be (a) because LinkedHashMap maintains a linked list to maintain the insertion order. So if the order is (b) it means a particular element is storing two references, one for the next element in order of insertion, and one for the next element in the same bucket.

If the answer is (b), how does the particular element decides, which one to visit,i.e. out of the two references, which one to pick.

The use case scenario is hypothetical, and it may not be in correlation with the fact that with number of elements less than number of buckets, the chances of collision is less. Please answer keeping in mind the above scenario.
Thanks in advance.

Upvotes: 2

Views: 3636

Answers (2)

assylias
assylias

Reputation: 328568

LinkedHashMap extends HashMap and its get method calls HashMap's getEntry method. HashMap's implementation stores each bucket in a separate array, so it would not need to loop over the whole dataset, only on the data within that bucket. Taken form Oracle JDK 7:

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

EDIT

e.next is defined in HashMap.Entry and is within the same bucket, as opposed to e.after and e.before defined in LinkedHasMap.Entry which can be in different buckets.

Upvotes: 1

Joop Eggen
Joop Eggen

Reputation: 109547

LinkedHashMap extends HashMap and hence linking is irrelevant for get, so on adding linkage they should not have made LinkedHashMap less efficient on get - as get does not need that linkage.

Upvotes: 2

Related Questions