I have been wondering about TreeMaps and HashMaps for a while. Here is what I have understood from the javadocs.
TreeMap is based on a a form of binary tree (red-back tree?). TreeMap is also sorted, and has an usage time, or whatever the proper term is, of log(n) for get, out, remove and containsKey. After testing a bit it appears to permit null values, but not null keys.
HashMap is more like an array where elements are found/added/removed based on hashes (basically a hash table). It has a more or less constant performance for basic operations, get and put. Permits both null keys and values.
None of are thread safe, and both of them are fail fast, meaning that if you use and iterator and then modify the collection then the iterator will throw an exception (unless you modified it with the iterators remove method).
So my question is, how do they compare to each other? How do their performance compare to each other? When is which one appropriate to use? When should they not be used? I know it is a theoretical question, but it is something I want to understand, and any answers would be appriciated.