3 ms·
>If they believe it's O(1), argue it's worst case O(n) In the case that all your keys have the same hash, right?
by benwaffle 11y ago
>If they believe it's O(1), argue it's worst case O(n)
In the case that all your keys have the same hash, right?
- mintplant 11y agoRight!
- Rapzid 11y agoIt seems to me this would entirely depend on the implementation and how collisions are handled.
- thaumasiotes 11y agoBuckets. :)
- sorokod 11y agoIn Java 8, collisions in Maps are stored in a tree structure so worst case is O(log n)
- logicchains 11y agoIs it a balanced tree? If not, worst case could still be O(n).
- Rapzid 11y agoHaha, 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.