This article will show why and when to use ArrayMap and SparseArray to optimize your Android Applications.
Whenever you need to store key -> value pairs, the first data structure that probably comes to mind for accomplishing this is HashMap. HashMap is quite flexible, so it may be tempting to use it all over the place, without really thinking about their possible side effects.
This is such a common problem that if you attempt to use a HashMap in Android Development IDE (Android Studio), it will warn you that you should instead use an ArrayMap instead.
So let’s explore when you should consider using ArrayMap, and dive into how it works internally.
HashMap vs ArrayMap
HashMap comes in the package java.util.HashMap
ArrayMap comes in the package android.util.ArrayMap and android.support.v4.util.ArrayMap. It comes with support.v4 to provide support for the lower android versions.
This YouTube video from Android Developers Channel has further details.
ArrayMap is a generic key -> value mapping data structure that is designed to be more memory efficient than a traditional HashMap.
ArrayMap 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 needing to create an extra object for every entry added to the map. It also controls the size of these arrays more aggressively, since growing them only requires copying the entries in the array — not rebuilding a hash map.
Note that this implementation is not intended for data structures that contain large numbers of items. It’s generally slower than a traditional HashMap, since lookups require a binary search. Adds and Removes require it to insert and delete entries array entries.
For containers holding up to hundreds of items, the performance difference is less than 50%, which is in my opinion not significant.
HashMap is basically an Array of HashMap.Entry objects. (Entry is an inner class of HashMap.)
At a high level, the instance variables in Entry class are:
- a non-primitive key
- a non-primitive value
- the hashCode of the object
- a pointer to next Entry
What happens when a key -> value pair is inserted into a HashMap?
- The hashCode of the key is calculated, and that value is assigned to the hashCode variable of EntryClass.
- Then, using hashCode, we get the index of the bucket where it will be stored.
- If the bucket has a pre-existing element, the new element is inserted with the last element pointing to new one — essentially making the bucket a linked list.
Now when you query the HashMap for the value for a key, it comes in O(1) time.
But the most important thing is that it comes at the cost of more space (memory).
- Autoboxing means extra objects are created with each insertion. This will impact memory usage, as well as garbage collection.
- The HashMap.Entry objects themselves are an extra layer of objects to be created and garbage collected.
- Buckets are rearranged each time HashMap is compacted or expanded. This is an expensive operation that grows with the number of objects.
In Android, memory matters a lot when it comes to responsive applications. Continuous allocation and de-allocation of memory — along with garbage collection — will cause lag in your Android application.
Remember — garbage collection is a tax on the performance of an application.
When garbage collection is taking place, your application can’t run. Instead, it lags.
ArrayMap uses 2 arrays. The instance variables used internally are Object[ ] mArray to store the objects and the int mHashes to store hashCodes. When a key -> value pair is inserted:
- The key -> value pair is autoboxed.
- The key object is inserted at the next available position in mArray[ ].
- The 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.
When you search for a key:
- The key’s hashCode is calculated.
- Binary search is done for this hashCode in the mHashes array. The implied time complexity increases to O(logN).
- Once we get the index of a hash, we know that key is at 2*index position in mArray and value is at 2*index+1 position.
- Here, the time complexity increases from O(1) to O(logN), but it’s memory efficient. Whenever we play with a dataset of around 100 records, you shouldn’t perceive any lag. But you’ll be taking advantage of a more memory efficient application.
- ArrayMap<K,V> in place of HashMap<K,V>
- ArraySet<K,V> in place of HashSet<K,V>
- SparseArray<V> in place of HashMap<Integer,V>
- SparseBooleanArray in place of HashMap<Integer,Boolean>
- SparseIntArray in place of HashMap<Integer,Integer>
- SparseLongArray in place of HashMap<Integer,Long>
- LongSparseArray<V> in place of HashMap<Long,V>
When you have a moment, check out my previous article on Android development best practices.