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?