CODEWITHSUNDEEP
androiddictionarydata-structures
xst
xst

Reputation: 3036

practical differences TreeMap and ArrayMap

In java a TreeMap is used for dictionaries where keys are kept sorted. On android, an ArrayMap is used as a "memory-efficient" HashMap where (I infer) keys are kept sorted because

lookups require a binary search and adds and removes require inserting and deleting entries in the array

Memory Usage:

...this container is intended to better balance memory use...

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.

...it will shrink its array as items are removed from it...

We can reasonably conclude that ArrayMap is inappropriate for holding ~1000+ items:

For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.

Note that this implementation is not intended to be appropriate for data structures that may contain large numbers of items.

What are additional costs/benefits of using one over the other generally?

  1. is android's ArrayMap implementation thread-safe (thus slower)?
  2. is there a way to affect the sorting in an ArrayMap?
  3. are there similar data structures in Guava?
  4. etc..

Upvotes: 0

Views: 219

Answers (1)

BladeCoder
BladeCoder

Reputation: 12929

  1. ArrayMap is not thread-safe, as stated in the documentation.
  2. The sorting is always by ascending order of the keys hashcode. You can control the order by overriding hashCode() in the implementation of the key class. Beware of collisions.

ArrayMap allows accessing its keys and values directly by index like an ArrayList and can be iterated on very efficiently. ArrayMap has the smallest memory consumption of the two. Both have a complexity of O(log n) for retrieval. Insertions and deletions are in theory a bit slower for ArrayMap because they are similar to inserting or deleting an element in the middle of an ArrayList: technically it's O(n) but it's using a single call to System.arrayCopy() to move all values at once very quickly. So if you need to modify the map very often, ArrayMap is probably not the best choice but for all other use cases it's very capable.

Upvotes: 1

Related Questions