☰

SparseArray vs HashMap Ask Question

tag-icon • tag-icon java android hashmap sparse-matrix
SparseArray vs HashMap Ask 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?

ベストアンサー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.

このjava.lang.instrumentパッケージには、オブジェクトのサイズを確認するなどの高度な操作に役立つメソッドがいくつか含まれていますgetObjectSize(Object objectToSize)。

追加情報は公式から入手できますOracle ドキュメント。

クラス = 12 バイト + (n インスタンス変数) * 4 バイト
配列 = 20 バイト + (n 要素) * (要素サイズ)
エントリ = 32 バイト + (1 番目の要素サイズ) + (2 番目の要素サイズ)

おすすめ記事