SparseArray & ArrayMap

arpit0303Leave a comment

whenever we want to store the key-value pair, the very first data structure come in our mind is HashMap. But in case of mobile development, we want more memory efficient structures. That is why Android introduce ArrayMap and SparseArray.

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

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.

A Hashmap is used to map Integer keys to an object.

HashMap< String, String> map = new HashMap< String, String>();
map.put(“Key1”, "Value1");
map.put(“Key2”, " Value2");
map.put(“Key3”, " Value3");

Set set = map.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 hashes of the given 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 linear walk is done over the second array (Key Value Array) to resolve the collision.

In other word, When the value for a key needs to be fetched, the key is first hashed and that hash is binary searched to find the index of that hash. This index is then used to find the location of the key and value in the interwoven array.
If the key does not match the key we were searching the value for, a linear search is performed in both the directions as it is assumed this was a case of collision.

Another advantage of using an ArrayMap over a HashMap is that it allows iteration over the collection using indexing which is not possible when using a HashMap.

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. Other operations are 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.

HashMap’s enforce you to use objects instead of primitives. Autoboxing also happens when you fetch a primitive object from a primitive container. 

HashMap<String, Integer> map = new HashMap<String, Integer>();
int value = map.get("key");

In addition, generic objects are much larger in size than their primitive counterparts. For example an Integer takes 16 bytes of space whereas its primitive counterpart takes just 4 bytes. Hence it would be much more efficient if you could use primitives as either keys or values in collections. SparseArray family is the one, which will provide this things:

SparseBooleanArray(int, boolean)
SparseArray(int, obj)
SparseLongArray(int, long)
LongSparseArray(long, obj)
SparseIntArray(int, int)

SparseArray maps integers to Objects and, unlike a normal array of Objects, its indices can contain gaps. SparseArray is intended to be more memory-efficient than a HashMap, because it avoids auto-boxing keys and its data structure doesn’t rely on an extra entry object for each mapping.

SparseArray sparseArray = new SparseArray();
sparseArray.put(1,"Android");

SparseLongArray sparseLongArray = new SparseLongArray();
sparseLongArray.put(1, 1L);

SparseBooleanArray sparseBooleanArray = new SparseBooleanArray();
sparseBooleanArray.put(1, true);

SparseIntArray sparseIntArray = new SparseIntArray();
sparseIntArray.put(1, 2);

LongSparseArray longSparseArray = new LongSparseArray();
longSparseArray.put(1L, "Android");

Similar to ArrayMaps, SparseArray’s help in reducing the memory footprint. The internal of them are very similar as well and both of them contain two tightly packed arrays rather than one. It also makes use of binary search like in the case of ArrayMaps.

Difference b/w SparseArray and ArrayMap:

Having said that, the main difference between SparseArray and ArrayMap is that the key object is always of primitive type in case of a SparseArray. This has two folds benefits as you save on memory and also avoid autoboxing.

HashMap can be replaced by the followings Array Class:

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.

References:
https://android.jlelse.eu/app-optimization-with-arraymap-sparsearray-in-android-c0b7de22541a
https://developer.android.com/reference/android/util/SparseArray
http://blog.vinaygaba.com/post/android-data-structures-101/
https://stackoverflow.com/questions/25560629/sparsearray-vs-hashmap

Leave a comment