It seems to me this would entirely depend on the implementation and how collisions are handled.

In Java 8, collisions in Maps are stored in a tree structure so worst case is O(log n)

Is it a balanced tree? If not, worst case could still be O(n).

Haha, that would be an odd set of data indeed. I have no idea how they implement it but I hope I have made a point(I feel I have). I wouldn't be too impressed with an interviewer or interviewee arguing one side or the other about the complexity of "unspecified hashmap implementation".

Too clever by half.

Buckets. :)

Right!