-
Notifications
You must be signed in to change notification settings - Fork 1
TreeMap
TreeMap is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
TreeMap is a Red-Black tree based NavigableMap implementation.In other words , it sorts the TreeMap object keys using Red-Black tree algorithm.
- Apart from implementing Map interface, Java TreeMap also implements NavigableMap and indirectly implements SortedMap interface. TreeMap also extends AbstractMap class. T* reeMap entries are sorted in the natural ordering of it’s keys. It also provides a constructor to provide Comparator to be used for ordering. So if you are using any class as key, make sure it provides implementation of equals and hashcode methods and Comparable interface for natural ordering. Check out java collections interview questions to understand the importance of these methods.
- Java TreeMap implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
- TreeMap is not synchronized and hence not thread-safe. For multithreaded environments, you can get a wrapped synchronized using Collections.synchronizedSortedMap method.
- TreeMap methods to get keyset and values return Iterator that are fail-fast in nature, so any concurrent modification will throw ConcurrentModificationException.
- TreeMap in java doesn’t allow null keys, however you can have multiple null values associated with different keys.
Red Black tree has the following properties :
- Every node is either red or black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes. Complete Reference
- https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/
- https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html
HashMap reallocates its internals as the new one gets inserted while TreeMap does not reallocate nodes on adding new ones. Thus , the size of the TreeMap dynamically increases if needed , without shuffling the internals. So it is meaningless to set the initial size of the TreeMap .
Refrences https://www.journaldev.com/14512/java-treemap-treemap-in-java http://javahungry.blogspot.com/2014/06/how-treemap-works-ten-treemap-java-interview-questions.html