SparseArray vs HashMap

Solution 1:

SparseArray can be used to replace HashMap when the key is a primitive type. There are some variants for different key/value types, even though not all of them are publicly available.

Benefits are:

Allocation-free
No boxing

Drawbacks:

Generally slower, not indicated for large collections
They won't work in a non-Android project

HashMap can be replaced by the following:

SparseArray          <Integer, Object>
SparseBooleanArray   <Integer, Boolean>
SparseIntArray       <Integer, Integer>
SparseLongArray      <Integer, Long>
LongSparseArray      <Long, Object>
LongSparseLongArray  <Long, Long>   //this is not a public class                                 
                                    //but can be copied from  Android source code

In terms of memory, here is an example of SparseIntArray vs HashMap<Integer, Integer> for 1000 elements:

SparseIntArray:

class SparseIntArray {
    int[] keys;
    int[] values;
    int size;
}

Class = 12 + 3 * 4 = 24 bytes
Array = 20 + 1000 * 4 = 4024 bytes
Total = 8,072 bytes

HashMap:

class HashMap<K, V> {
    Entry<K, V>[] table;
    Entry<K, V> forNull;
    int size;
    int modCount;
    int threshold;
    Set<K> keys
    Set<Entry<K, V>> entries;
    Collection<V> values;
}

Class = 12 + 8 * 4 = 48 bytes
Entry = 32 + 16 + 16 = 64 bytes
Array = 20 + 1000 * 64 = 64024 bytes
Total = 64,136 bytes

Source: Android Memories by Romain Guy from slide 90.

The numbers above are the amount of memory (in bytes) allocated on heap by JVM. They may vary depending on the specific JVM used.

The java.lang.instrument package contains some helpful methods for advanced operations like checking the size of an object with getObjectSize(Object objectToSize).

Extra info is available from the official Oracle documentation.

Class = 12 bytes + (n instance variables) * 4 bytes
Array = 20 bytes + (n elements) * (element size)
Entry = 32 bytes + (1st element size) + (2nd element size)

Solution 2:

I came here just wanting an example of how to use SparseArray. This is a supplemental answer for that.

Create a SparseArray

SparseArray<String> sparseArray = new SparseArray<>();

A SparseArray maps integers to some Object, so you could replace String in the example above with any other Object. If you are mapping integers to integers then use SparseIntArray.

Add or update items

Use put (or append) to add elements to the array.

sparseArray.put(10, "horse");
sparseArray.put(3, "cow");
sparseArray.put(1, "camel");
sparseArray.put(99, "sheep");
sparseArray.put(30, "goat");
sparseArray.put(17, "pig");

Note that the int keys do not need to be in order. This can also be used to change the value at a particular int key.

Remove items

Use remove (or delete) to remove elements from the array.

sparseArray.remove(17); // "pig" removed

The int parameter is the integer key.

Lookup values for an int key

Use get to get the value for some integer key.

String someAnimal = sparseArray.get(99);  // "sheep"
String anotherAnimal = sparseArray.get(200); // null

You can use get(int key, E valueIfKeyNotFound) if you want to avoid getting null for missing keys.

Iterate over the items

You can use keyAt and valueAt some index to loop through the collection because the SparseArray maintains a separate index distinct from the int keys.

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

    int key = sparseArray.keyAt(i);
    String value = sparseArray.valueAt(i);

    Log.i("TAG", "key: " + key + " value: " + value);
}

// key: 1 value: camel
// key: 3 value: cow
// key: 10 value: horse
// key: 30 value: goat
// key: 99 value: sheep

Note that the keys are ordered in ascending value, not in the order that they were added.