tirtha_raj_1's blog

Unordered map with Worst case O(LogN) !?
By tirtha_raj_1, history, 6 months ago, In English

So, recently in my college placement interview, my interviewer asked me about the internal working of an unordered map. I explained him all I knew. In a follow up he then asked me how can we reduce the worst-case search or insert time complexity from O(N) to O(LogN). I did not have a convincing answer for him.

At the end of the interview, he asked what if we used a balanced BST in place of a linked list for chaining in a bucket with the same index. Thinking about it I don't find any flaws in this idea. Then why don't we use this idea to implement an unordered map or am I missing something guys?

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this is a normal map wich average case is log n instead 1 of unordered_map or maybe i am wrong

→ Reply
»
6 months ago, # |
  Vote: I like it +25 Vote: I do not like it

I think this is actually the way that HashMap has been implemented in Java since Java 8. However, a possible drawback to this approach is that the constant factor of operations would be increased. When the number of hash collisions is few, this approach would decrease the worst-case complexity of operations but might increase the average-case time cost.

The above problem can be partially counteracted by conditionally turning the linked list into a BST when the number of nodes occupying the same bucket exceeds a certain threshold, however (like Java does).

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cool so basically it is a tradeoff between average and worst-case complexity.

    → Reply