title: practical differences TreeMap and ArrayMap
body: <p>In java a <a href="https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html" rel="nofollow noreferrer">TreeMap</a> is used for dictionaries where keys are kept sorted.
  On android, an <a href="https://developer.android.com/reference/android/util/ArrayMap" rel="nofollow noreferrer">ArrayMap</a> is used as a &quot;memory-efficient&quot; HashMap where (I infer) keys are kept sorted because</p>
  <blockquote>
  <p>lookups require a binary search and adds and removes require inserting and deleting entries in the array</p>
  </blockquote>
  <p>Memory Usage:</p>
  <blockquote>
  <p>...this container is intended to better balance memory use...</p>
  <p>It keeps its mappings in an array data structure -- an integer array of hash codes for each item, and an Object array of the key/value pairs. This allows it to avoid having to create an extra object for every entry put in to the map.</p>
  <p>...it will shrink its array as items are removed from it...</p>
  </blockquote>
  <p>We can reasonably conclude that <code>ArrayMap</code> is inappropriate for holding ~1000+ items:</p>
  <blockquote>
  <p>For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.</p>
  <p>Note that this implementation is not intended to be appropriate for data structures that may contain large numbers of items.</p>
  </blockquote>
  <p>What are additional costs/benefits of using one over the other generally?</p>
  <ol>
  <li>is android's <code>ArrayMap</code> implementation thread-safe (thus slower)?</li>
  <li>is there a way to affect the sorting in an <code>ArrayMap</code>?</li>
  <li>are there similar data structures in Guava?</li>
  <li>etc..</li>
  </ol>