Is it O(1) retreival in hashmap?

Question

I have a hashmap like this:

Map<TestBean,String>

where TestBean is a POJO class containing a few strings, say str1,str2. Two TestBean objects obj1 and obj2 are said to be equal if either

obj1.str1=obj2.str1 || obj1.str2==obj2.str1

So, when I retrieve a value from this map, is it still a O(1) retrieval?

This has been asked sooooo many times here.... :s – janos Dec 09 '13 at 12:17 — janos, Dec 09 '13 at 12:17
Flag it for closure then. – Adam Arold Dec 09 '13 at 12:21 — Adam Arold, Dec 09 '13 at 12:21

Ian Roberts · Answer 1 · 2013-12-09T13:13:49.337

It should be O(1) provided the hashcode implementation is reasonably uniform - in the worst case (if everything is hashed to the same bucket) it could be O(N).

The trouble is that for this specific example you have precisely that worst possible case - given your either-or equality condition, I can't see a sensible way to implement the hashCode contract that equal objects must have equal hash codes other than to simply return the same code for every object.

In fact, I don't think you can even have a well-defined equals() in this case, as your condition is neither symmetric nor transitive

a1(str1 = "A", str2 = "B")
a2(str1 = "B", str2 = "C")
a3(str1 = "C", str2 = "D")

not symmetric: a1.equals(a2) but !a2.equals(a1)
not transitive: a1.equals(a2) and a2.equals(a3), but !a1.equals(a3).

score 1 · Answer 2 · answered Dec 09 '13 at 12:16

The amortized time complexity is O(1). This depends on the implementation of the hashcode function. If you have a lot of collisions you will have increased complexity.

So basically it is O(1) in the optimal case and it will close O(n) as your hashcode produces more collisions. If your hashcode function returns the same number in all cases you reach O(n) since your map becomes a linked list.

Is it O(1) retreival in hashmap?

2 Answers2