Sparse Array vs HashMap

This is the answer I gave for a StackOverflow question.
I’d like to report it here for the records.

Sparse arrays can be used to replace hash maps when the key is a primitive type. There are some variants for different key/value type even though not all them are publicly available.

Benefits are:

• Allocation-free
• No boxing

Drawbacks:

• Generally slower, not indicated for large collections
• They won’t work in non-android project

HashMap can be replaced by the followings:

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

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

Extra info are available from official Oracle documentation

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