Optimization Using ArrayMap and SparseArray
- Amit Shekhar
- Published on
I am Amit Shekhar, I have taught and mentored many developers, and their efforts landed them high-paying tech jobs, helped many tech companies in solving their unique problems, and created many open-source libraries being used by top companies. I am passionate about sharing knowledge through open-source, blogs, and videos.
Before we start, I would like to mention that, I have released a video playlist to help you crack the Android Interview: Check out Android Interview Questions and Answers.
In this blog, we will learn why and when to use ArrayMap and SparseArray to optimize our 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
ArrayMap comes in the package
android.support.v4.util.ArrayMap. It comes with
support.v4 to provide support for the lower android versions.
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 the 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.
HashMap.Entryobjects 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 array to store the objects and the
int hashes to store hashCodes. When a
key -> value pair is inserted:
key -> valuepair is autoboxed.
- The key object is inserted at the next available position in
- The value object is also inserted in the position next to the key’s position in
- The hashCode of the key is calculated and placed in
hashesat 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 hashes array. The implied time complexity increases to O(logN).
- Once we get the index of a hash, we know that the key is at
2*indexposition in array and value is at
- Here, the time complexity increases from
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
ArraySet<K,V>in place of
SparseArray<V>in place of
SparseBooleanArrayin place of
SparseIntArrayin place of
SparseLongArrayin place of
LongSparseArray<V>in place of
Show your love by sharing this blog with your fellow developers.
Master Kotlin Coroutines from here: Mastering Kotlin Coroutines
That's it for now.
You can connect with me on: