TreeMap is a Red-Black tree based NavigableMap implementation.

Important properties of TreeMap

1. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time.

2. 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.

3. Ordering maintained by a tree map must be consistent with equals if this sorted map is to correctly implement the Map interface.

   • The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

4. Is not synchronized.

   • Could synchronize on some object that naturally encapsulates the map or use the Collections.synchronizedSortedMap method.

     • This is best done at creation time.

5. The iterators returned by the iterator method of the collections returned by all of this class's "collection view methods" are fail-fast.

   • However the fail-fast behavior of an iterator cannot be guaranteed.

6. All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced.

   • They do not support the Entry.setValue method.

Important methods of TreeMap

Please refer to the API summary for SortedMap and NavigableMap, as most methods are implemented from thos interfaces.