SparseArray vs HashMap

Main purpose of SparseArray in Android development is to have a memory efficient integer to object mapping.

It is not solely about to gain a performance tweak, however, you will save much more memory by using SparseArray.

Benefits of SparseArray

  • Saves you memory (Less memory usage thanks to the primitive keys and no Entry objects)
  • No auto-boxing (Because the keys are primitives e.g. int vs Integer, it will not convert your key to a new Integer(key))
  • Less time spend in GC-Garbage Collection- (With auto boxing there will be redundant Integer and Entry objects in the memory which needs to be collected by GC after their usage end)

Drawbacks of SparseArray

  • SparseArray uses binary search to find a value which has O(log n) however HashMaps is O(1) to run which implies that it will find your value almost instantly. For a larger collections the better performance of HashMap should be noticeable.
  • Implementation of SparseArray is only for Android. It can not be used in Java SE applications. However, the implementation can be considered trivial. Therefore you can add the sources to your Java SE project manually with the proper licensing of course.

Other variants of SparseArray

You can also use other variants of sparsearray for mapping to booleans, to integers, and to longs.

SparseArray          <Integer,Object>
SparseBooleanArray   <Integer, Boolean>
SparseIntArray       <Integer, Integer>
SparseLongArray      <Integer, Long>
LongSparseArray      <Long, Object>

LongSparseArray is different than the rest. If you need to map long to Objects than LongSparseArray is your best alternative than HashMap in android development. Basically it is the same as SparseArray except it maps primitive longs to Objects.

How much memory can SparseArray save?

To find out how much memory can SparseArray save lets consider this scenario:

SparseIntArray vs HashMap<Integer, Integer> for 1000 elements.

class HashMap<K, V>{ //  Class = 12 + 8 * 4 = 48 bytes
    Entry<K, V>[] table; // Entry = 32 + 16 + 16 = 64 bytes
    Entry<K, V>[] forNull; //  Array = 20 + 1000 * 64 = 64024 bytes
    int size;
    int modCount;
    int threshold;
    Set<K> keys;
    Set<Entry<K,V>> entries; // Total = 64,136 bytes
    Collection<V> values;
}

class SparseIntArray { //  Class = 12 + 3 * 4 = 24 bytes
    int[] keys;  //  Array = 20 + 1000 * 4 = 4024 bytes
    int[] values;
    int size; //  Total = 8.072 bytes
}

In summary, HashMap used 64kb whereas SparseIntArray used 8kb for the same collection of 1000 items.

Source: Android Memories by Romain Guy

Where can be SparseArray used?

In android development, every resource file has an integer id (auto generated). For instance, your strings will get keys like ‘R.string.mystring’ or your drawables get id of ‘R.drawable.myimage’.

Therefore, you have a lot of opportunity to use the SparseArray in your project. For instance, you need to cache some Drawables in your project, instead of using hashmap you can use SparseArray.

public HashMap<Integer, Bitmap> hashMap = new HashMap<>();
public SparseArray<Bitmap> sparseArray = new SparseArray<>();

public void initHashMap() {
    Resources resources = getResources();
    hashMap.put(R.drawable.ic_home, BitmapFactory.decodeResource(resources, R.drawable.ic_home));
    hashMap.put(R.drawable.ic_settings, BitmapFactory.decodeResource(resources, R.drawable.ic_settings));
    hashMap.put(R.drawable.ic_profile, BitmapFactory.decodeResource(resources, R.drawable.ic_profile));
    }

public void initSparseArray() {
    Resources resources = getResources();
    sparseArray.append(R.drawable.ic_home, BitmapFactory.decodeResource(resources, R.drawable.ic_home));
    sparseArray.append(R.drawable.ic_settings, BitmapFactory.decodeResource(resources, R.drawable.ic_settings));
    sparseArray.append(R.drawable.ic_profile, BitmapFactory.decodeResource(resources, R.drawable.ic_profile));
}

public Bitmap getBitmap(Integer key) {
    return hashMap.get(key);
}

public Bitmap getBitmapSparse(Integer key) {
    return sparseArray.get(key);
}

As you can see, the usage of HashMap and SparseArray almost identical in your code.

Related posts


Posted

in

by

Comments

2 responses to “SparseArray vs HashMap”

  1. MAD'u CrY Avatar
    MAD’u CrY

    Hi,
    Thanks for the nice article.
    I have small doubt regarding to retreive keys and values alone.
    How can i get all the values() or key() alone suing Sparse like HashMap.

    1. Gunhan Avatar

      Hi @maducry:disqus,

      What is your use-case for iterating over a SparseArray because it is alternative for HashMap so if you need some kind of list functionality i recommend you to use ArrayList.

      Still if it is required you may iterate over SparseArray like the following:
      for (int i = 0; i < sparseArray.size(); i++){
      int key = sparseArray.keyAt(i);
      String value = sparseArray.valueAt(i);
      }

Leave a Reply

Your email address will not be published. Required fields are marked *