title: When to use TreeMap instead of HashMap
body: <p>I require a map that supports 3 operations: "insert", "remove" and "iterate in sorted order". This is exactly the interface of <code>TreeMap</code> in Java. That being said it can also be implemented by using a <code>HashMap</code> and sorting it every time before iteration. To analyze the different approaches, lets say I perform <code>n</code> inserts and <code>m</code> removes, 'r' reads and then iterate.
  <p>With <code>TreeMap</code> we have the following implementation:</p>
  
  <pre><code>TreeMap&lt;Integer, Integer&gt; tm = Maps.newTreeMap();
  for (int i=0;i&lt;n;++i) {tm.put(i, 2*i);} // O(n*log(n))
  for (int i=0;i&lt;m;++i) {tm.remove(i);} // O(m*log(m))
  for (int i=0;i&lt;r;++i) {tm.get(i);} // O(r*log(n-m))
  for (Integer i : tm) {print(i);} // O(n-m)
  </code></pre>
  
  <p>All told we have a total run time of <code>O(n*log(n) + m*log(m) + r*log(n-m))</code>
  <p>With <code>HashMap</code> we have the following implementation:</p>
  
  <pre><code>HashMap&lt;Integer, Integer&gt; hm = Maps.newHashMap();
  for (int i=0;i&lt;n;++i) {hm.put(i, 2*i);} // O(n)
  for (int i=0;i&lt;m;++i) {hm.remove(i);} // O(m)
  for (int i=0;i&lt;r;++i) {hm.get(i);} // O(r)
  List&lt;Integer&gt; sortedList = Lists.newArrayList(hm.keySet()); // O(n-m)
  Collections.sort(sortedList); // O((n-m)*log(n-m))
  for (Integer i : sortedList) {print(i);} // O(n-m)
  </code></pre>
  
  <p>All told we have a total run time of <code>O((n-m)*log(n-m))</code>.
  <p>For all <code>n,m O(n*log(n) + m*log(m) + r*log(n-m)) &gt; O((n-m)*log(n-m))</code>.
  <p>My question therefore is, what is the use case where a <code>TreeMap</code> is better than a <code>HashMap</code>? Is it only better if you need to iterate over the map many (let's say <code>k</code>) times (in which case, if <code>k</code> is >> <code>log(n)</code> the run time for <code>TreeMap</code> will be <code>O(k*(n-m))</code> whereas for <code>HashMap</code> will be <code>O(k*(n-m)*log(n-m)))</code>? Regardless, if you are only performing <code>O(log(n))</code> iterations (this does sound like such a sane use case), <code>HashMap</code> will outperform <code>TreeMap</code>. Am I missing something? </p>