Menu
In one of the posts I saw that TreeMap takes O(log(n)) time for get/put.
Can someone please answer why it takes O(log(n)), even when it can search directly through get/put using key?
859
TreeMap has complexity of O(logN) for insertion and lookup.
Hashmap put and get operation time complexity is O(1) with assumption that key-value pairs are well distributed across the buckets.
HashMap is a general purpose Map implementation. It provides a performance of O(1) , while TreeMap provides a performance of O(log(n)) to add, search, and remove items. Hence, HashMap is usually faster.
Key Points For operations like add, remove, containsKey, time complexity is O(log n where n is number of elements present in TreeMap. TreeMap always keeps the elements in a sorted(increasing) order, while the elements in a HashMap have no order.
Performance wise TreeMap is slow if you will compare with HashMap and LinkedHashMap. The TreeMap provides guaranteed log (n) time complexity for the methods such as containsKey (), get (), put () and remove ().
Internal Working of TreeMap in Java. TreeMap class is like HashMap. TreeMap stores key-value pairs. The main difference is that TreeMap sorts the key in ascending order. TreeMap is sorted as the ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
The TreeMap provides guaranteed log (n) time complexity for the methods such as containsKey (), get (), put () and remove (). Also, a TreeMap is fail-fast in nature that means it is not synchronized and that is why is not thread-safe.
The TreeMap itself is implemented using a red-black tree which is a self-balancing binary search tree. Since it uses a binary tree, the put (), contains () and remove () operations have a time complexity of O (log n). Furthermore, since the tree is balanced, the worst-case time complexity is also O (log n).
In a TreeMap, the key/value entries are stored in a Red-Black tree, and in order to find if a key is contained in the tree, you have to traverse it from the root, down some path, until reaching the required key or reaching a leaf.
A tree containing n elements has an O(log n) height, and therefore that's the time it would take to search for a key.
193
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
