TreeMap is the implementation of the Red Black Ground Algorithm, which implements the sortedmap interface. It should be noted that it is not using a hash table, the storage method is a special binary tree, and the red black tree: http://blog.9cbs.net/treeroot/ Archive / 2004/10/15 / 138431.aspx This article is a good, I haven't heard of the binary tree before, I just see this article plus the source code of Treemap to understand the red black tree algorithm.
It is not intended to study the source code of TreeMap, because it is completely an algorithm, if you don't understand this algorithm, I don't understand, I have many places not completely understand, here talk about Treemap.
TreeMap statement: public class TreeMap extends AbstractMap implements SortedMap, Cloneable, java.io.Serializable so we need to know SortedMap Interface: http: //blog.9cbs.net/treeroot/archive/2004/10/15/138423.aspx
Since TreeMap is ordered, natural requirements elements can be compared, if the constructor specifies the Compare, use this Comparer, if you do not specify comparator, use natural sort (element to implement the Comparable interface). If this is Both are not available, waiting for an error. About Java sort: http://blog.9cbs.net/treeroot/archive/2004/10/19/142636.aspx
Because it is a binary tree, it is generally found that the time complexity is O (LG (N)), of course, there is no HashMap efficiency. However, TreeMap is powerful than the HashMap function. If you don't need to sort, you will not use treem, if you need to sort Hashmap can't be competent, of course, it is necessary to use treemap, it can ask the child Map. So this is the applicable occasion problem, which is unable to compare them. In addition, we are used to it, there is MAP will follow a set, we can guess Treeset and The implementation of a sortedset implemented by Treemap. But I feel that Treeset seems to be more than Treemap, and it is very common !!
