Unordered map with Worst case O(LogN) !?

Revision en1, by tirtha_raj_1, 2023-12-06 07:24:13

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?


  Rev. Lang. By When Δ Comment
en1 English tirtha_raj_1 2023-12-06 07:24:13 645 Initial revision (published)