SparseArray vs HashMap

Question

I can think of several reasons why HashMaps with integer keys are much better than SparseArrays:

1. The Android documentation for a SparseArray says "It is generally slower than a traditional HashMap".
2. 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.
3. If you write code using HashMaps rather than SparseArrays your code will work in non-android projects.
4. Map overrides equals() and hashCode() whereas SparseArray doesn't.

Yet whenever I try to use a HashMap with integer keys in an Android project, IntelliJ tells me I should use a SparseArray instead. I find this really difficult to understand. Does anyone know any compelling reasons for using SparseArrays?

Answer 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)

Answer 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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

It's unfortunate that the compiler issues a warning. I guess HashMap has been way overused for storing items.

SparseArrays have their place. Given they use a binary search algorithm to find a value in an array you have to consider what you are doing. Binary search is O(log n) while hash lookup is O(1). This doesn't necessarily mean that binary search is slower for a given set of data. However, as the number of entries grows, the power of the hash table takes over. Hence the comments where low number of entries can equal and possibly be better than using a HashMap.

A HashMap is only as good as the hash and also can be impacted by load factor (I think in later versions they ignore the load factor so it can be better optimized). They also added a secondary hash to make sure the hash is good. Also the reason SparseArray works really well for relatively few entries (<100).

I would suggest that if you need a hash table and want better memory usage for primitive integer (no auto boxing), etc., try out trove. (http://trove.starlight-systems.com - LGPL license). (No affiliation with trove, just like their library)

With the simplified multi-dex building we have you don't even need to repackage trove for what you need. (trove has a lot of classes)