java - SparseArray vs HashMap




android sparse-matrix (5)

Posso pensar em várias razões pelas quais os HashMap s com chaves inteiras são muito melhores que os SparseArray s:

  1. A documentação do Android para um SparseArray diz "Geralmente é mais lento que um HashMap tradicional".
  2. Se você escrever código usando o HashMap s em vez do SparseArray s, seu código funcionará com outras implementações do Map e você poderá usar todas as APIs Java projetadas para o Maps.
  3. Se você escrever código usando o HashMap vez do SparseArray seu código funcionará em projetos não-android.
  4. Mapa substitui equals() e hashCode() enquanto SparseArray não.

No entanto, sempre que tento usar um HashMap com chaves inteiras em um projeto Android, o IntelliJ me diz que eu deveria usar um SparseArray . Acho isso muito difícil de entender. Alguém conhece alguma razão convincente para usar o SparseArray ?


A documentação do android para um SparseArray diz "Geralmente é mais lento que um HashMap tradicional".

Sim está certo. Mas quando você tem apenas 10 ou 20 itens, a diferença de desempenho deve ser insignificante.

Se você escrever código usando HashMaps em vez de SparseArrays, seu código funcionará com outras implementações do Map e você poderá usar todas as APIs Java projetadas para o Google Maps.

Acho que na maioria das vezes usamos apenas o HashMap para pesquisar um valor associado a uma chave enquanto o SparseArray é realmente bom nisso.

Se você escrever código usando HashMaps em vez de SparseArrays, seu código funcionará em projetos não-android.

O código-fonte do SparseArray é bastante simples e fácil de entender, de modo que você só paga pouco esforço para movê-lo para outras plataformas (através de um simples COPY & Paste).

Mapa substitui equals () e hashCode () enquanto SparseArray não

Tudo o que posso dizer é (para a maioria dos desenvolvedores) quem se importa?

Outro aspecto importante do SparseArray é que ele usa apenas uma matriz para armazenar todos os elementos enquanto o HashMap usa Entry , então o SparseArray custa menos memória do que um HashMap , veja documentation


No entanto, sempre que tento usar um HashMap com chaves inteiras em um projeto android, intelliJ me diz que eu deveria usar um SparseArray.

É apenas um aviso desta documentation do array esparso:

Pretende ser mais eficiente em termos de memória do que usar um HashMap para mapear Inteiros para Objetos

O SparseArray é feito para ser eficiente em termos de memória do que usar o HashMap regular, ou seja, não permite várias lacunas dentro do array, não como o HashMap. Não há nada com que se preocupar, pois você pode usar o HashMap tradicional se não desejar se preocupar com a alocação de memória para o dispositivo.


Depois de alguns googling eu tento adicionar algumas informações para os anwers já postados:

Isaac Taylor fez uma comparação de desempenho para SparseArrays e Hashmaps. Ele afirma que

o Hashmap e o SparseArray são muito semelhantes para tamanhos de estrutura de dados abaixo de 1.000

e

quando o tamanho foi aumentado para a marca de [...] 10.000, o Hashmap tem maior desempenho com a adição de objetos, enquanto o SparseArray tem maior desempenho ao recuperar objetos. [...] Em um tamanho de 100.000 [...] o Hashmap perde desempenho muito rapidamente

Uma comparação no Edgblog mostra que um SparseArray precisa de muito menos memória do que um HashMap devido à menor chave (int vs Integer) e ao fato de que

uma instância de HashMap.Entry deve manter o controle das referências para a chave, o valor e a próxima entrada. Além disso, também precisa armazenar o hash da entrada como um int.

Como conclusão, eu diria que a diferença pode ser importante se você for armazenar muitos dados em seu mapa. Caso contrário, apenas ignore o aviso.


Eu vim aqui apenas querendo um exemplo de como usar o SparseArray . Esta é uma resposta suplementar para isso.

Crie um SparseArray

SparseArray<String> sparseArray = new SparseArray<>();

Um SparseArray mapeia inteiros para algum Object , então você poderia substituir String no exemplo acima por qualquer outro Object . Se você estiver mapeando inteiros para números inteiros, use SparseIntArray .

Adicionar ou atualizar itens

Use put (ou append ) para adicionar elementos ao 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 que as chaves int não precisam estar em ordem. Isso também pode ser usado para alterar o valor em uma determinada chave int .

Remover itens

Use remove (ou delete ) para remover elementos da matriz.

sparseArray.remove(17); // "pig" removed

O parâmetro int é a chave inteira.

Valores de pesquisa para uma chave int

Use get para obter o valor de uma chave inteira.

String someAnimal = sparseArray.get(99);  // "sheep"
String anotherAnimal = sparseArray.get(200); // null

Você pode usar get(int key, E valueIfKeyNotFound) se quiser evitar ficar null por chaves perdidas.

Iterar sobre os itens

Você pode usar keyAt e valueAt algum índice para percorrer a coleção porque o SparseArray mantém um índice separado distinto das chaves int .

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

Observe que as chaves são ordenadas em valor crescente, não na ordem em que foram adicionadas.


SparseArray pode ser usado para substituir o HashMap quando a chave é um tipo primitivo. Existem algumas variantes para diferentes tipos de chave / valor, embora nem todas estejam disponíveis publicamente.

Benefícios são:

  • Livre de alocação
  • Sem boxe

Desvantagens:

  • Geralmente mais lento, não indicado para grandes coleções
  • Eles não vão funcionar em um projeto não-Android

HashMap pode ser substituído pelo seguinte:

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 

Em termos de memória, aqui está um exemplo de SparseIntArray vs HashMap<Integer, Integer> para 1000 elementos:

SparseIntArray :

class SparseIntArray {
    int[] keys;
    int[] values;
    int size;
}

Classe = 12 + 3 * 4 = 24 bytes
Matriz = 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;
}

Classe = 12 + 8 * 4 = 48 bytes
Entrada = 32 + 16 + 16 = 64 bytes
Matriz = 20 + 1000 * 64 = 64024 bytes
Total = 64,136 bytes

Fonte: Android Memories de Romain Guy do slide 90.

Os números acima são a quantidade de memória (em bytes) alocada no heap pela JVM. Eles podem variar dependendo da JVM específica usada.

O pacote java.lang.instrument contém alguns métodos úteis para operações avançadas, como a verificação do tamanho de um objeto com getObjectSize(Object objectToSize) .

Informações extras estão disponíveis na documentação oficial da Oracle .

Classe = 12 bytes + (n variáveis ​​da instância) * 4 bytes
Matriz = 20 bytes + (n elementos) * (tamanho do elemento)
Entrada = 32 bytes + (tamanho do primeiro elemento) + (tamanho do segundo elemento)







sparse-matrix