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?
I think this is a normal map wich average case is log n instead 1 of unordered_map or maybe i am wrong
I think this is actually the way that
HashMaphas 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).
Cool so basically it is a tradeoff between average and worst-case complexity.