SparseArray and its friends in Android

One most important factor affecting Android app performance is memory. Android framework provides some speical classes to help developers optimizating memory usage. SparseArray and its friends are some of them.

How to use

SparseArray and its friends are designed to replace HashMap in Android when there isn’t large number of elements in the map. Below we list outs the Java usage and its corresponding Android replacement.

SparseArray          <Integer, Object>
SparseBooleanArray   <Integer, Boolean>
SparseIntArray       <Integer, Integer>
SparseLongArray      <Integer, Long>
LongSparseArray      <Long, Object>
LongSparseLongArray  <Long, Long>

Note that Android support library have two classes named SparseArrayCompat and LongSparseArray for backward compatibility. SparseArrayCompat supports methods like removeAtRange, which is only available at SparseArray from API 19.

When to use

In a word, we should use SparseArray and its friends when both of the following are met,
1. The key of the map is integer or long.
2. The number of elements is less than several hundreds.

This is because of the following advantages offered by SparseArray.
1. The key is primitive type, so putting an element doesn’t require creating an aditional Entry object, while HashMap does.
2. Also because key is primitive, there’s no auto-boxing of keys.

According to Android Memories presentation, for holding 1000 elements, SparseArray uses 8k while HashMap uses 64k.

class HashMap<k, v="">{ //  Class = 12 + 8 * 4 = 48 bytes
    Entry<k, v="">[] table; // Entry = 32 + 16 + 16 = 64 bytes
    Entry<k, v="">[] forNull; //  Array = 20 + 1000 * 64 = 64024 bytes
    int size;
    int modCount;
    int threshold;
    Set keys;
    Set<entry<K,V>> entries; // Total = 64,136 bytes
    Collection values;
}

class SparseIntArray { //  Class = 12 + 3 * 4 = 24 bytes
    int[] keys;  //  Array = 20 + 1000 * 4 = 4024 bytes
    int[] values;
    int size; //  Total = 8.072 bytes
}

But the memory efficiency doesn’t come for free.
1. HashMap computes the hash code to find the index to insert a new element in O(1). SparseArray uses binary search to find the index to insert in O(logn), which is less time efficient. According to Android official documentation, this difference is less than 50% for up to hundreds of items.
2. SparseArray is Android special, meaning less portable.

In addition, SparseArray offers some additional features.
1. The keys put into SparseArray are sorted ascendingly.
2. We can get an individual key or value given an index.

In contrast, HashMap doesn’t guarantee any order of the map. In fact, the order can change over time.

Internals

The pros and cons of SparseArray vs HashMap is due to their implementation.

For SparseArray, keys and values are kept in separate arrays.

1. Adding an element will use a binary search to find the insertion position.
a. If there’s already an element for key, replace it.
b. If there’s not and insertion space is available because the element there is marked as DELETED, insert it there.
c. Otherwise, we need to move array elements and grow the array capacity if necessary, and then insert the element.

2. Remove an element is optimized. The class simply mark it as DELETED. And when we query the size, the array needs to grow size, or do anything required to have a correct index, the array is then actually compacted.

Note that the method to compact the array is called gc, though it doesn’t necessarily will cause Java runtime GC to happen.

3. Because keys and values are kept in separate arrays and inserted using binary search position, the keys are guaranteed to be sorted.

HashMap is implemented using an array of linked list.

1. Adding an element will cause the class to compute the hash value of the key object (another hash is done on top of the hash code to further avoid collision). Based on the hash code, an array index is found to insert the value.

At each array index, there’s a linked list of Entry object, with key, value, hash and a pointer to next Entry object. When the same key (same reference or equals) is used, the old value is updated. Otherwise, a new Entry object is created, and added to the linked list.

2. Remove an element is similar. Finding the index based on hash in the array and traversal the linked list to find the correct Entry object to remove.

For a class with good hashcode implementation, the number of collisions will be small and the linked list at each array index will be short.

Leave a Reply

Your email address will not be published. Required fields are marked *