advantage of treemap datastructure in java besides sorting and ordering

Question

What is the advantage of treemap datastructure in java besides sorting and ordering ? How does treemap data structure internally work ?

Answer 1

Treemap main advantage is that it allows to store the key-value mappings in a sorted order. Treemap internally uses red black tree.

From the javadocs:

A Red-Black tree based NavigableMap implementation. The map 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.

Red-black tree from Wiki:

A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science. The self-balancing is provided by painting each node with one of two colors (these are typically called 'red' and 'black', hence the name of the trees) in such a way that the resulting painted tree satisfies certain properties that don't allow it to become significantly unbalanced. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently. The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion, and deletion operations, along with the tree rearrangement and recoloring are also performed in O(log n) time.[1]

To learn more about Reb Black tree, check this: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

To read more about treemap check : http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html

Answer 2

If you mean advantage of TreeMap over HashMap, there's none. In fact HashMap has an advantage over TreeMap - it's faster. As for internal impl, you can download standard lib src from Oracle site, or from here http://sourceforge.net/projects/jdk7src/