ArrayMap and its friends in Android

Previous post we discussed about SparseArray and its friends in Android. While they can replace HashMap when integer and long are used as key. It doesn’t work when the key is an arbitrary object.

Actually similar ideas can be applied to create more memory efficient generic map data structure. This post will go through ArrayMap, ArraySet and their friends, which replaces HashMap and HashSet in a more memory efficient way.

Usage

ArrayMap implements Map<K, V> interface, and it’s fully compatible with HashMap. There’a simplified version of ArrayMap: SimpleArrayMap, which doesn’t have the burden of maintaining compatibility with Java Map inteface, but still provides most of the commonly needed methods.

Correspondingly there’s ArraySet implements the Set<V> interface.

We should consider using ArrayMap and ArraySet at the following cases.

1. The number items is less than 1000.
2. Frequent reading, insertion and removal are less frequent.

And if we don’t need to maintain compatibility with Java interface, we can use SimpleArrayMap where ArrayMap is used.

Internals

We have described how HashMap works internally at SparseArray and its friends in Android. Basically it uses an array of linked list, and lots of unused space is allocated in the array.

For ArrayMap, two arrays are used. One is used to store the hash code of all keys, and the other is used to store the key value pairs. Key is stored at the even index, and value is saved at odd index.

Figure 1. Internal arrays in ArrayMap [image from ref 1]

Binary search is applied on the hash code array to locate the index, and the same index is used in the second array to store and retrieve key and value. Specifically,

1. For get, the hash code of key is computed and used in binary search to find the index. Then two searches are performed to find the equal key in the second array. One is searching forward, and the other is search backward. If no equal key is found, null is returned.

2. For put, if an equal key is found, the value is updated; otherwise a new key, value pair is inserted at the end of the equal hash code range. Array resizing might be applied in the process.

3. ArrayMap internally caches the arrays of size 4 and 8, to avoid spamming garbage. This further improves the memory efficiency when number of items in the map is small.

Advantages and Disadvantages

The internals of ArrayMap offers the following advantages compared with HashMap.

1. It’s more memory efficient. There’s no unused space allocated.

2. When there’s no element, ArrayMap doesn’t allocate memory, whereas HashMap allocates unused space.

3. Iteration with keyAt and valueAt is just like iterating an array. It’s very efficient. HashMap uses Iterator, which is slower and takes more memory.

But these advantages are not free,

1. Accessing a value from ArrayMap is O(logn), whereas in HashMap is O(1). This makes not much difference when number of elements in the Map is less than 1000.

2. Insertion and Deletion are relatively expensive, since we need to shift array elements, or allocate new array and copy elements over.

References

1. Android Fun with ArrayMaps performance video.

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.