Przychodzi mi do głowy kilka powodów, dla których HashMaps z kluczami całkowitymi są znacznie lepsze niż SparseArrays:

1. Dokumentacja systemu Android dla a SparseArraymówi: „Generalnie jest wolniejsza niż tradycyjna HashMap”.
2. Jeśli napiszesz kod przy użyciu HashMaps zamiast SparseArrays, twój kod będzie działał z innymi implementacjami Map i będziesz mógł używać wszystkich API Java zaprojektowanych dla Map.
3. Jeśli piszesz kod przy użyciu HashMaps zamiast SparseArrays, kod będzie działał w projektach innych niż Android.
4. Map przesłonięcia equals()i hashCode()podczas gdy SparseArraynie robi.

Jednak za każdym razem, gdy próbuję użyć a HashMapz kluczami całkowitymi w projekcie Androida, IntelliJ mówi mi, że powinienem użyć SparseArrayzamiast tego. Naprawdę trudno mi to zrozumieć. Czy ktoś zna jakieś istotne powody, dla których warto używać SparseArrays?

SparseArraymoże służyć do zamiany, HashMapgdy klucz jest typem pierwotnym. Istnieje kilka wariantów dla różnych typów klucza / wartości, mimo że nie wszystkie z nich są publicznie dostępne.

Korzyści to:

• Bez przydziału
• Żadnego boksu

Wady:

• Generalnie wolniejszy, niewskazany dla dużych kolekcji
• Nie będą działać w projektach innych niż Android

HashMap można zastąpić następującym:

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 

Jeśli chodzi o pamięć, oto przykład SparseIntArrayvs HashMap<Integer, Integer>dla 1000 elementów:

SparseIntArray:

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

Klasa = 12 + 3 * 4 = 24 bajty
Tablica = 20 + 1000 * 4 = 4024 bajty
Razem = 8072 bajty

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;
}

Klasa = 12 + 8 * 4 = 48 bajtów
Wpis = 32 + 16 + 16 = 64 bajty
Tablica = 20 + 1000 * 64 = 64024 bajtów
Razem = 64,136 bajtów

Źródło: Android Memories by Romain Guy ze slajdu 90.

Powyższe liczby to ilość pamięci (w bajtach) przydzielona na stercie przez JVM. Mogą się różnić w zależności od używanej maszyny JVM.

java.lang.instrumentPakiet zawiera kilka przydatnych metod zaawansowanych operacji, takich jak sprawdzenie rozmiaru obiektu z getObjectSize(Object objectToSize).

Dodatkowe informacje są dostępne w oficjalnej dokumentacji Oracle .

Klasa = 12 bajtów + (n zmiennych instancji) * 4 bajty
Tablica = 20 bajtów + (n elementów) * (rozmiar elementu)
Entry = 32 bajty + (rozmiar pierwszego elementu) + (rozmiar drugiego elementu)

Przyszedłem tutaj tylko po to, żeby zobaczyć przykład użycia SparseArray. To jest dodatkowa odpowiedź.

Utwórz SparseArray

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

A SparseArrayodwzorowuje liczby całkowite na niektóre Object, więc Stringw powyższym przykładzie można zamienić je na dowolne inne Object. Jeśli odwzorowujesz liczby całkowite na liczby całkowite, użyj SparseIntArray.

Dodaj lub zaktualizuj elementy

Użyj put(lub append), aby dodać elementy do tablicy.

sparseArray.put(10, "horse");
sparseArray.put(3, "cow");
sparseArray.put(1, "camel");
sparseArray.put(99, "sheep");
sparseArray.put(30, "goat");
sparseArray.put(17, "pig");

Pamiętaj, że intklucze nie muszą być w porządku. Można to również użyć do zmiany wartości w określonym intkluczu.

Usuń przedmioty

Użyj remove(lub delete), aby usunąć elementy z tablicy.

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

intParametr jest kluczem całkowitą.

Wyszukaj wartości dla klucza int

Użyj, getaby uzyskać wartość dla jakiegoś klucza całkowitego.

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

Możesz użyć, get(int key, E valueIfKeyNotFound)jeśli chcesz uniknąć nullbraku kluczy.

Powtarzaj elementy

Możesz użyć keyAti valueAtjakiegoś indeksu do zapętlenia kolekcji, ponieważ SparseArrayutrzymuje oddzielny indeks różniący się od intkluczy.

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

Zauważ, że klucze są uporządkowane rosnąco, a nie w kolejności, w jakiej zostały dodane.

Jednak za każdym razem, gdy próbuję użyć HashMap z kluczami całkowitymi w projekcie Androida, intelliJ mówi mi, że powinienem zamiast tego użyć SparseArray.

To jest tylko ostrzeżenie z tej dokumentacji o jego rzadkiej tablicy:

Ma to być bardziej wydajne w pamięci niż użycie HashMap do mapowania liczb całkowitych na obiekty

Ma SparseArraybyć wydajna pod względem pamięci niż użycie zwykłego HashMap, co oznacza, że ​​nie pozwala na wiele luk w tablicy, w przeciwieństwie do HashMap. Nie ma się czym martwić, możesz skorzystać z tradycyjnej mapy HashMap, jeśli nie chcesz martwić się o alokację pamięci do urządzenia.

Rzadka tablica w Javie to struktura danych, która odwzorowuje klucze na wartości. Ten sam pomysł co mapa, ale inna implementacja:

1. Mapa jest reprezentowana wewnętrznie jako tablica list, gdzie każdy element na tych listach jest parą klucz, wartość. Zarówno klucz, jak i wartość są instancjami obiektu.

2. Tablica rzadka składa się po prostu z dwóch tablic: tablic (prymitywów) kluczy i tablicy wartości (obiektów). W indeksach tych tablic mogą występować luki, stąd termin „rzadka” tablica.

Główną zaletą SparseArray jest to, że oszczędza pamięć przy użyciu prymitywów zamiast obiektów jako klucza.

Po pewnym googlowaniu staram się dodać trochę informacji do już opublikowanych odpowiedzi:

Isaac Taylor dokonał porównania wydajności dla SparseArrays i Hashmaps. On uważa, iż

Hashmap i SparseArray są bardzo podobne dla struktur danych o rozmiarach poniżej 1000

i

gdy rozmiar zostanie zwiększony do 10 000 znaków, [...] Hashmap ma większą wydajność przy dodawaniu obiektów, podczas gdy SparseArray ma większą wydajność podczas pobierania obiektów. [...] Przy rozmiarze 100 000 [...] Hashmap bardzo szybko traci wydajność

Porównanie na Edgblog pokazuje, że SparseArray wymaga znacznie mniej pamięci niż HashMap ze względu na mniejszy klucz (int vs Integer) i fakt, że

instancja HashMap.Entry musi śledzić odwołania do klucza, wartość i następny wpis. Dodatkowo musi również przechowywać hash wpisu jako int.

Podsumowując, powiedziałbym, że różnica może mieć znaczenie, jeśli zamierzasz przechowywać dużo danych w swojej mapie. W przeciwnym razie po prostu zignoruj ​​ostrzeżenie.

Dokumentacja systemu Android dla SparseArray mówi: „Generalnie jest wolniejsza niż tradycyjna mapa HashMap”.

Tak, to prawda. Ale jeśli masz tylko 10 lub 20 elementów, różnica w wydajności powinna być nieznaczna.

Jeśli piszesz kod za pomocą HashMaps zamiast SparseArrays, Twój kod będzie działał z innymi implementacjami Map i będziesz mógł używać wszystkich interfejsów API Java zaprojektowanych dla Map

Myślę, że najczęściej używamy tylko HashMapdo wyszukiwania wartości związanej z kluczem, podczas gdy SparseArrayjest w tym naprawdę dobry.

Jeśli piszesz kod przy użyciu HashMaps zamiast SparseArrays, kod będzie działał w projektach innych niż Android.

Kod źródłowy SparseArray jest dość prosty i łatwy do zrozumienia, dzięki czemu wystarczy niewielki wysiłek, aby przenieść go na inne platformy (za pomocą prostego KOPIUJ i Wklej).

Map przesłania equals () i hashCode (), podczas gdy SparseArray nie

Mogę tylko powiedzieć (większości programistów) kogo to obchodzi?

Innym ważnym aspektem SparseArrayjest to, że używa on tylko tablicy do przechowywania wszystkich elementów podczas HashMapużywania Entry, więc SparseArraykosztuje znacznie mniej pamięci niż a HashMap, zobacz to

Szkoda, że ​​kompilator wyświetla ostrzeżenie. Wydaje mi się, że HashMap był nadużywany do przechowywania przedmiotów.

SparseArrays mają swoje miejsce. Biorąc pod uwagę, że używają binarnego algorytmu wyszukiwania, aby znaleźć wartość w tablicy, musisz rozważyć, co robisz. Wyszukiwanie binarne to O (log n), podczas gdy wyszukiwanie skrótu to O (1). Nie musi to oznaczać, że wyszukiwanie binarne jest wolniejsze dla danego zestawu danych. Jednak wraz ze wzrostem liczby wpisów moc tabeli skrótów przejmuje kontrolę. Stąd komentarze, w których mała liczba wpisów może być równa i prawdopodobnie lepsza niż przy użyciu HashMap.

HashMap jest tak dobry, jak hash, a także może mieć na niego wpływ współczynnik obciążenia (myślę, że w późniejszych wersjach ignorują współczynnik obciążenia, więc można go lepiej zoptymalizować). Dodali również dodatkowy hash, aby upewnić się, że hash jest dobry. Również powód, dla którego SparseArray działa naprawdę dobrze dla stosunkowo niewielu wpisów (<100).

Sugerowałbym, że jeśli potrzebujesz tablicy haszującej i chcesz lepszego wykorzystania pamięci dla prymitywnych liczb całkowitych (bez automatycznego pudełkowania) itp., Wypróbuj trove. ( http://trove.starlight-systems.com - licencja LGPL). (Brak powiązań z skarbnicą, podobnie jak ich biblioteka)

Dzięki uproszczonemu budynkowi multi-dex, który mamy, nie musisz nawet przepakowywać skarbca do tego, czego potrzebujesz. (trove ma wiele klas)