Worse case time complexity put/get HashMap

Question

What is the worst case time complexity of an Hashmap when the hashcode of it's keys are always equal.

In my understanding: As every key has the same hashcode it will always go to the same bucket and loop through it to check for equals method so for both get and put the time complexity should be O(n), Am I right?

I was looking at this HashMap get/put complexity but it doesn't answer my question.

Also here Wiki Hash Table they state the worse case time complexity for insert is O(1) and for get O(n) why is it so?

Answer 1

Yes, in the worst case your hash map will degenerate into a linked list and you will suffer an O(N) penalty for lookups, as well as inserts and deletions, both of which require a lookup operation (thanks to the comments for pointing out the mistake in my earlier answer).

There are some ways of mitigating the worst-case behavior, such as by using a self-balancing tree instead of a linked list for the bucket overflow - this reduces the worst-case behavior to O(logn) instead of O(n).

Answer 2

In Java 8's HashMap implementation (for when the key type implements Comparable):

Handle Frequent HashMap Collisions with Balanced Trees: In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).

From here.

Answer 3

in open hashing, you will have a linked list to store objects which have the same hashcode. so: for example, you have a hashed table with size 4. 1) assume you want to store an object with hashcode = 0. the object then will be mapped into index (0 mod 4 = ) 0. 2) then you again want to put another object with hashcode = 8. this object will be mapped into index (8 mod 4 = ) 0, as we remember that the index 0 has already filled with our first object, so we have to put the second next to the first.

[0]=>linkedList{object1, object2}
[1]=>null
[2]=>null
[3]=>null

3) what are the steps for searching? 1st, you have to hash the key object and assume that it hashcode is 8, so you will be redirected to index (8 mod 4 = ) 0, then because there is more than one object stored in the same index, we have to search one-by-one all stored objects in the list until you find the matched one or until the end of the list. as the example has 2 objects which stored in the same hashtable index 0, and the searched object lies right in the end of the linkedlist, so you need to walk through all the stored objects. that's why it is O(n) as the worst case. worst case occured when all the stored object are in the same index in the hashtable. so they will be stored in a linkedlist in which we (may) need to walk through all of them to find our searched object.

hope this help,.