HashMaps, ArrayMaps and SparseArrays in Android

This article will show why and when to use ArrayMap and SparseArray to optimize your Android Applications.

Android developers must be observing Lint warnings recently to replace some of their HashMaps with SparseArrays with a promise of memory optimization. Good for us! There are few classes we should learn to use, like ArrayMap and SimpleArrayMap. There are also multiple variants of SparseArrays. This post will describe these classes along with their internals.

Let’s start with some code showing how to use these classes

1. java.util.HashMap<String, String> hashMap = new java.util.HashMap<String, String>(16);
2. hashMap.put("key", "value");
3. hashMap.get("key");
4. hashMap.entrySet().iterator();
6. android.util.ArrayMap<String, String> arrayMap = new android.util.ArrayMap<String, String>(16);
7. arrayMap.put("key", "value");
8. arrayMap.get("key");
9. arrayMap.entrySet().iterator();
11. android.support.v4.util.ArrayMap<String, String> supportArrayMap =
12. new android.support.v4.util.ArrayMap<String, String>(16);
13. supportArrayMap.put("key", "value");
14. supportArrayMap.get("key");
15. supportArrayMap.entrySet().iterator();
17. android.support.v4.util.SimpleArrayMap<String, String> simpleArrayMap =
18. new android.support.v4.util.SimpleArrayMap<String, String>(16);
19. simpleArrayMap.put("key", "value");
20. simpleArrayMap.get("key");
21. //simpleArrayMap.entrySet().iterator(); <- will not compile
23. android.util.SparseArray<String> sparseArray = new android.util.SparseArray<String>(16);
24. sparseArray.put(10, "value");
25. sparseArray.get(10);
27. android.util.LongSparseArray<String> longSparseArray = new android.util.LongSparseArray<String>(16);
28. longSparseArray.put(10L, "value");
29. longSparseArray.get(10L);
31. android.util.SparseLongArray sparseLongArray = new android.util.SparseLongArray(16);
32. sparseLongArray.put(10, 100L);
33. sparseLongArray.get(10);

Let’s discuss these classes one by one. All Java collections are primarily based on Arrays. We need to understand how HashMaps work before we look into alternatives.

java.util.HashMap

HashMap is basically an Array of HashMap.Entry objects (Entry is an inner class of HashMap). On a high-level, the instance variables in Entry class are :

1. A non-primitive key
2. A non-primitive value
3. Hashcode of the object
4. A pointer to next Entry

Note that keys and values are all non-primitives. This is a design decision made by Java engineers, and we have to live with it. Inserting a primitive comes at a cost of autoboxing.

When an object is inserted in the HashMap :

• Hashcode of the key is calculated and Entry class’ hashCode variable is populated.
• Another method, java.util.HashMap.indexFor() is applied on the hashCode which you can think of as a modulo function using the size of Entry[ ], and determines the index of this Entry in the Entry[ ]. This index is called ‘bucket’.
• If there is a pre-existing element in this bucket, the new element is inserted with the last element pointing to new one – essentially making the bucket a LinkedList.

Queries can now be done with O(1) complexity :

• Input key’s hashCode is calculated
• java.util.HashMap.indexFor() is applied on this hashCode and we get the bucket/index of the Entry object like querying an array.

O(1) time is a magic all developers want. But space is another constraint. Especially on mobile. Drawbacks of HashMaps are :

1. Autoboxing means extra objects created with each insertion. This will impact memory usage as well as Garbage Collection.
2. The HashMap.Entry objects themselves are an extra layer of objects to be created and garbage collected.
3. Buckets are rearranged each time HashMap is compacted or expanded. This is an expensive operation which grows with a number of objects.
4. Hashing is cool, but if implemented poorly will take us back to O(N).
5. A related disadvantage of hashing which most people ignore is that we still need to store both the key and the hashcode. This redundancy helps with tackling collision. Non-hash solutions can help in this regard too.

android.util.ArrayMap

ArrayMap uses 2 arrays. The instance variables used internally are Object[ ] mArray to store the objects and the int[] mHashes to store hashCodes. When an key/value is inserted :

• Key/Value is autoboxed.
• Key object is inserted at the next available position in mArray[ ].
• Value object is also inserted in the position next to key’s position in mArray[ ].
• The hashCode of key is calculated and placed in mHashes[ ] at the next available position.

For searching a key :

• Key’s hashCode is calculated
• Binary search is done for this hashCode in the mHashes array. This implies time complexity increases  to O(logN).
• Once we get the index of hash, we know that key is at 2*index position in mArray and value is at keyIndex+1 position.

This still does not solve the problem of autoboxing, as put() still takes an Object as input. But it does create one less object (HashMap.Entry). Is it worth trading off O(1) search complexity ? Metrics say yes for most apps.

android.support.v4.util.ArrayMap

android.util.ArrayMap works only on API level 19 (Kitkat) onwards. Support library brings the same functionality to older platforms.

android.support.v4.util.SimpleArrayMap

As you would have noticed in the code snippet posted earlier (line#21), this class does not offer entrySet() method to iterate. If you go through it’s documentation, it trims off many other methods from standard Java Collections API. So why use SimpleArrayMap ? Use it to trim down your APK size at the cost of losing interoperability with other Java containers. This way, Proguard (code optimization and obfuscation tool, which is likely to be a part of your build generation) can trim off most of those unused Collections API code – and hence making your APK size smaller. The internal working of this class is same as android.util.ArrayMap.

android.util.SparseArray

Like ArrayMaps, SparseArrays also use 2 arrays at their core. One is int[ ] called mKeys and the second is Object[ ] called mValues. As the names suggest, one is for keys and another for values 

When a key/value is inserted :

• The int key (and not it’s hash) is stored in the next available position in mKeys[ ]. So no autoboxing of the key anymore.
• The value Object is stored in the next available position in mValues[ ]. Value is still autoboxed.

For a query :

• The key is searched using binary search (refer to android.util.ContainerHelpers.binarySearch() method) in the mKeys array. This means search complexity is still O(log N).
• The key index is used to retrieve the value from the mValues array.

Compared to HashMap, we got rid of Entry object and the key object. We have given up hashing, and are relying on binary search. On compaction/expansion, there is a lighter overhead now.

Pre-KitKat (API level >= 19) use android.support.v4.util.SparseArrayCompat

android.util.LongSparseArray

SparseArray accepts only int primitives as keys. With LongSparseArray, we can use long as keys too. Implementation is same as SparseArray.

Pre-Kitkat (API level >= 19) use android.support.v4.util.LongSparseArray

android.util.SparseIntArray, android.util.SparseLongArray and android.util.SparseBooleanArray

For cases where keys are integer primitives and values are either an integer, long or boolean primitives; use SparseIntArray, SparseLongArray and SparseBooleanArray respectively. Their implementation is same as SparseArrays, the advantage being the mValues array is a primitive array. Which means neither key, nor value is boxed, and we save 3 objects (Entry, Key and Value) compared to HashMap implementation while losing search complexity from O(1) to O(log N).

Comparison

Continuous allocation and de-allocation of memory along with garbage collection will cause lag in Android application and it reduces the application performance. Other than this ArrayMap & SparseArray avoid memory problem by using 2 small arrays rather than one big one.

Benefits of using SparseArray over HashMap is:

• More memory efficient by using primitives
• No auto-boxing
• Allocation-free

Drawbacks:

• For large collections, it is slower
• It only available for Android

In general, if inserts or deletes are fairly infrequent, and the number of items is < 1000 then ArrayMap / SparseArray classes are really good replacement classes.

HashMap can be replaced by the followings Array Class:

Conclusion

As we can conclude that the SparseArray is a more efficient solution than using a Hashmap to map Integers to objects. The theory is that the SparseArray can add and retrieve elements quicker than a HashMap (<1000), in this case, by removing the hashing function processing time.

Thanks for reading. To help others please click ❤ to recommend this article if you found it helpful.