Thanks for the detailed explanation. I had a small doubt - if the hashmap’s capacity does not exceed threshold, then it uses linkedlist for storing and fetching the values. Then how come it guarantees constant time put and get operations
If the hashmap's capacity does not exceed threshold, then it simply means collisions have "rarely" happened. That's why even if there is 1 (or few number of nodes) in the linkedList, the time complexity of put and get operations won't get affected and thus it will remain constant.
Yes, you're right! "The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n)."
I had small query - suppose, at time of Put(K, V), N = x and during Get(K), N = y(y >> x), so in this case the worst case time complexity of Get operation can reach upto O(n) even when there is no collisions at any index ?
Hi,
Thanks for the detailed explanation. I had a small doubt - if the hashmap’s capacity does not exceed threshold, then it uses linkedlist for storing and fetching the values. Then how come it guarantees constant time put and get operations
Hi Abhishek,
If the hashmap's capacity does not exceed threshold, then it simply means collisions have "rarely" happened. That's why even if there is 1 (or few number of nodes) in the linkedList, the time complexity of put and get operations won't get affected and thus it will remain constant.
Thank you
I think after java 8 they have changes the internal implementation from linked list to binary tree for better complexity in get calls
Yes, you're right! "The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n)."
Thanks for highlighting.
Hi,
I had small query - suppose, at time of Put(K, V), N = x and during Get(K), N = y(y >> x), so in this case the worst case time complexity of Get operation can reach upto O(n) even when there is no collisions at any index ?
Hey Abhishek
Since there are no collisions at any index, this means at each bucket of hashmap, there is a linkedlist with atmost one size.
In that case, we can perform following steps for Get(K) operation:
1. Calculate Hash(K) for incoming key K.
2. Check the bucket which is stored at Hash(K) value.
3. Get the first and only element (if present) from the LinkedList.
Thus, the time complexity for performing all above steps i.e. Get(K) operation remains O(1).
Thanks