2016.04.22 16:03

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




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.

저작자 표시
신고
Posted by hoonihoon85 hoonihoon