App optimization with ArrayMap and SparseArray in Android

Collections are the most common thing used in the software development. In general whenever we required to store data in key value pairs, the very first data structure that comes to our mind is HashMap. It is quite flexible hence it is the most preferred data structure choice to store key value pairs.

To improve the performance of Android application, Android system provides set of collections build especially for mobile development.

So ArrayMap and SparseArray are intended to be more memory efficient than using a HashMap.

How HashMap works?

HashMap is basically an Array of HashMap.Entry objects. Entry is inner class of HashMap which holds the key and values.

When a key-value pair is inserted into a HashMap, a hashCode of the key is calculated, and that value is assigned to the hashCode variable of EntryClass. Now using hashCode, we can get the index of the bucket where it will be stored. In case 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.

It has a constant time, or O(1) time requirement for retrieving an element from the array. This means that it takes the same time to pull any element from the array, regardless of the size. This is possible by using a hashing function, which generates the array indices, given the input key.

A Hashmap is used (in this case) to map Integer keys to an object.

Below are the example code to create HashMap and fetch keys and values:

HashMap< String, String> map = new HashMap< String, String>();

map.put(“Key1”, "Value1");

map.put(“Key2”, " Value2");

map.put(“Key3”, " Value3");

Set set = hmap.entrySet();

Iterator iterator = set.iterator();

// Iterate over HashMap

while(iterator.hasNext()) {

    Map.Entry mEntry = (Map.Entry)iterator.next();

    String key = mEntry.getKey();

    String value = mEntry.getValue();

}

How ArrayMap works?

ArrayMap contains two small array instead of one in a HashMap. The first array (Hash-Array) contains the specified hash keys in sorted order. The second array (Key Value Array) stores the keys and values of the objects according to the first array.

When we fetch an item, a binary-search is done on the Hash-Array to find a matching hash the index and then directly return the key-value pair from the second array (Key Value Array). If the key in the second array (Key Value Array), doesn't match then a linearly walk is done over the second array (Key Value Array) to resolve the collision.

Below are the example code to create ArrayMap and fetch keys and values:

ArrayMap<String, String> arrayMap = new ArrayMap<>();

arrayMap.put("Key1", "Value1");

arrayMap.put("Key2", " Value2");

arrayMap.put("Key3", " Value3");

for (int i = 0; i < arrayMap.size(); i++) {

    String key = arrayMap.keyAt(i);

    String value = arrayMap.valueAt(i);

}

How SparseArray works?

The main difference from ArrayMap is that, in SparseArray key is always primitive types. In other respects the principle of operation is similar. Sparse arrays can be used to replace hash maps when the key is a primitive type. SparseArray is designed to remove the auto-boxing problem (ArrayMap does not avoid the auto-boxing problem). This approach affects the memory consumption.

Below are the example code to create SparseArray:

SparseArray sparseArray = new SparseArray();

sparseArray.put(1, "Value1");

SparseLongArray sparseLongArray = new SparseLongArray();

sparseLongArray.put(1, 1L);

SparseBooleanArray sparseBooleanArray = new SparseBooleanArray();

sparseBooleanArray.put(1, true);

SparseIntArray sparseIntArray = new SparseIntArray();

sparseIntArray.put(1, 2);

Class appear even in the API 1, but has been redesigned in the API 11. The updated version SparseArrayCompat also available for older devices in the compatibility library.

There are several other types of SparseArray:

LongSparseArray, SparseIntArray, SparseBooleanArray etc.

HashMap can be replaced by the followings Array Class:

HashMap	Array class
HashMap <K, V>	ArrayMap <K, V>
HashMap <Integer, Object>	SparseArray <Object>
HashMap <Integer, Boolean>	SparseBooleanArray
HashMap <Integer, Integer>	SparseIntArray
HashMap <Integer, Long>	SparseLongArray
HashMap <Long, Object>	LongSparseArray <Object>

                                   

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

This video from Android developers will provide you further details.

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.

To find more interesting topics on Software development follow me at https://medium.com/@ankit.sinhal.

Twitter: https://twitter.com/ankitsinhal

GitHub: https://github.com/AnkitSinhal