The price you pay for sorting is lower performance. HashMap has amortized constant-time performance for put and get operations, while TreeMap has ln(N) performance (i.e., the performance is proportional to the logarithm of the size.
All this is actually discussed in some detail on the Javadoc pages for these, and other, java.util classes -- it's worth taking the time to read the introductions at the top of a page when you are using a class you're new to.