SparseArray vs HashMap

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)

Yet whenever I try to use a HashMap with integer keys in an android project, intelliJ tells me I should use a SparseArray instead.

It is only a warning from this documentation of it sparse array:

It is intended to be more memory efficient than using a HashMap to map Integers to Objects

The SparseArray is made to be memory efficient than using the regular HashMap, that is does not allow multiple gaps within the array not like HashMap. There is nothing to worry about it you can use the traditional HashMap if you desire not worrying about the memory allocation to the device.

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.