Amit Shekhar

Optimization Using ArrayMap and SparseArray

Authors
  • Amit Shekhar
    Name
    Amit Shekhar
    Published on
Optimization Using ArrayMap and SparseArray

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.

Join my program and get high paying tech job: amitshekhar.me

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 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.

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

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).

Drawbacks:

  • 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

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:

  • The key -> value pair is autoboxed.
  • The key object is inserted at the next available position in array[].
  • The value object is also inserted in the position next to the key’s position in array[].
  • The hashCode of the key is calculated and placed in hashes[] 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 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*index position in array 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>

Show your love by sharing this blog with your fellow developers.

Prepare yourself for Android Interview: Android Interview Questions

That's it for now.

Thanks

Amit Shekhar

You can connect with me on:

Read all of my high-quality blogs here.