SparseArray vs HashMap

Question

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)

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.

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.

After some googling I try to add some information to the already posted anwers:

Isaac Taylor made a performance comparision for SparseArrays and Hashmaps. He states that

the Hashmap and the SparseArray are very similar for data structure sizes under 1,000

and

when the size has been increased to the 10,000 mark [...] the Hashmap has greater performance with adding objects, while the SparseArray has greater performance when retrieving objects. [...] At a size of 100,000 [...] the Hashmap loses performance very quickly

An comparision on Edgblog shows that a SparseArray need much less memory than a HashMap because of the smaller key (int vs Integer) and the fact that

a HashMap.Entry instance must keep track of the references for the key, the value and the next entry. Plus it also needs to store the hash of the entry as an int.

As a conclusion I would say that the difference could matter if you are going to store a lot of data in your Map. Otherwise, just ignore the warning.

A sparse array in Java is a data structure which maps keys to values. Same idea as a Map, but different implementation:

1. A Map is represented internally as an array of lists, where each element in these lists is a key,value pair. Both the key and value are object instances.

2. A sparse array is simply made of two arrays: an arrays of (primitives) keys and an array of (objects) values. There can be gaps in these arrays indices, hence the term “sparse” array.

The main interest of the SparseArray is that it saves memory by using primitives instead of objects as the key.

The android documentation for a SparseArray says "It is generally slower than a traditional HashMap".

Yes,it's right. But when you have only 10 or 20 items , the performance difference should be insignificant.

If you write code using HashMaps rather than SparseArrays your code will work with other implementations of Map and you will be able to use all of the java APIs designed for Maps

I think most often we only use HashMap to search a value associated with a key while SparseArray is really good at this.

If you write code using HashMaps rather than SparseArrays your code will work in non-android projects.

The source code of SparseArray is fairly simple and easy to understand so that you only pay little effort moving it to other platforms(through a simple COPY&Paste).

Map overrides equals() and hashCode() whereas SparseArray doesn't

All I can say is, (to most developers)who care?

Another important aspect of SparseArray is that it only uses an array to store all elements while HashMap uses Entry, so SparseArray costs significant less memory than a HashMap, see this