SparseArray in Android

SparseArray is an Android specific data structure that maps integer keys to object values, designed as a memory efficient alternative to HashMap<Integer, Object>. It avoids the autoboxing overhead of converting primitive int keys to Integer wrapper objects and uses two parallel arrays internally instead of a hash table with entry objects. Understanding when and why to use SparseArray over standard map implementations is a common Android interview topic. By the end of this lesson, you will be able to:

• Explain the internal data structure of SparseArray and how it differs from HashMap.
• Describe the performance tradeoffs between SparseArray and HashMap at different dataset sizes.
• Use SparseArray and its typed variants (SparseBooleanArray, SparseIntArray, SparseLongArray) correctly.
• Identify when SparseArray provides meaningful benefits over standard collections.

Internal Structure

SparseArray stores keys and values in two separate arrays: an int[] for keys and an Object[] for values. The keys array is kept sorted, and lookups use binary search to find the index of a given key. The same index is then used to retrieve the corresponding value from the values array:

val sparseArray = SparseArray<String>()
sparseArray.put(10, "ten")
sparseArray.put(3, "three")
sparseArray.put(7, "seven")

// Internally: keys = [3, 7, 10]
//             values = ["three", "seven", "ten"]
val result = sparseArray[7] // binary search on keys -> "seven"

By contrast, HashMap allocates an Entry object for each key value pair, boxes primitive int keys into Integer objects, and uses a hash table with linked lists or trees for collision resolution. Each Entry holds references to the key, value, hash code, and next entry.

Memory Efficiency

The memory savings from SparseArray come from three sources. First, it stores keys as primitive int values rather than boxed Integer objects, saving 16 bytes per entry on a 64 bit runtime. Second, it does not create Entry wrapper objects, each of which adds roughly 32 bytes of overhead. Third, the two backing arrays are compact and contiguous in memory, which improves cache locality.

For a dataset of 100 entries, a HashMap<Integer, String> allocates approximately 100 Integer objects and 100 Entry objects beyond the values themselves. SparseArray allocates only the two backing arrays. On memory constrained devices, this difference adds up when multiple sparse maps are in use.

Performance Tradeoffs

The tradeoff for memory efficiency is lookup speed. SparseArray uses binary search with O(log n) time complexity for lookups, insertions, and deletions. HashMap provides O(1) amortized time for the same operations through hashing. For small to moderate datasets (a few hundred entries), the difference is negligible. For thousands of entries or more, HashMap is measurably faster: