SparseArray против HashMap

177

Я могу придумать несколько причин, почему HashMaps с целочисленными ключами намного лучше, чем SparseArrays:

  1. Документация Android для a SparseArrayгласит: «Обычно она медленнее традиционной HashMap».
  2. Если вы пишете код, используя HashMaps, а не SparseArrays, ваш код будет работать с другими реализациями Map, и вы сможете использовать все API-интерфейсы Java, разработанные для Maps.
  3. Если вы пишете код, используя HashMaps, а не SparseArrays, ваш код будет работать в не-Android проектах.
  4. Карта переопределяет, equals()а в hashCode()то время как SparseArrayнет.

Тем не менее, всякий раз, когда я пытаюсь использовать HashMapцелочисленные клавиши в проекте Android, IntelliJ говорит мне, что я должен использовать SparseArrayвместо этого. Мне действительно трудно это понять. Кто-нибудь знает какие-либо веские причины для использования SparseArrays?

Пол Боддингтон
источник

Ответы:

235

SparseArrayможет использоваться для замены, HashMapкогда ключ является примитивным типом. Есть несколько вариантов для различных типов ключ / значение, хотя не все они являются общедоступными.

Преимущества:

  • Выделение свободных
  • Нет бокса

Недостатки:

  • Как правило, медленнее, не указывается для больших коллекций
  • Они не будут работать в не Android-проекте

HashMap может быть заменено следующим:

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 

С точки зрения памяти, вот пример SparseIntArrayпротив HashMap<Integer, Integer>1000 элементов:

SparseIntArray:

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

Класс = 12 + 3 * 4 = 24 байта
Массив = 20 + 1000 * 4 = 4024 байта
Всего = 8,072 байта

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

Класс = 12 + 8 * 4 = 48 байтов.
Запись = 32 + 16 + 16 = 64 байта.
Массив = 20 + 1000 * 64 = 64024 байта.
Всего = 64 136 байтов.

Источник: Android-воспоминания Ромена Гая со слайда 90.

Числа выше - это объем памяти (в байтах), выделенной в куче JVM. Они могут варьироваться в зависимости от конкретной используемой JVM.

java.lang.instrumentПакет содержит некоторые полезные методы для сложных операций , таких как проверка размеров объекта с getObjectSize(Object objectToSize).

Дополнительная информация доступна из официальной документации Oracle .

Класс = 12 байтов + (n переменных экземпляра) * 4 байта
Массив = 20 байтов + (n элементов) * (размер элемента)
Запись = 32 байта + (размер 1-го элемента) + (размер 2-го элемента)

Sarpe
источник
15
Кто-нибудь может подсказать мне, откуда взялись эти "12 + 3 * 4" и "20 + 1000 * 4"?
Мариан Паджиох,
5
@ MarianPaździoch, он показал презентацию ( speakerdeck.com/romainguy/android-memories ), где класс занимает 12 байтов + 3 переменные по 4 байта, массив (ссылка) занимает 20 байтов (dlmalloc - 4, служебные данные - 8, ширина и заполнение) - 8).
CoolMind
1
Напомним, что еще одним ключевым недостатком SparseArray является то, что в качестве объекта Android он должен быть смоделирован для модульного тестирования. По возможности теперь я использую собственные объекты Java для упрощения тестирования.
Дэвид Г
@DavidG Вы можете просто использовать плагин unmock для насмешки над зависимостями Android.
метель
1
Даже если вы не используете Android, скопировать класс в свой проект несложно, это зависит только от 3 других классов. Лицензия APL означает, что это нормально, независимо от лицензии, с которой вы работаете.
Янн ТМ
35

Я пришел сюда просто, чтобы получить пример использования SparseArray. Это дополнительный ответ для этого.

Создать SparseArray

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

A SparseArrayотображает целые числа на некоторые Object, так что вы можете заменить Stringв приведенном выше примере на любой другой Object. Если вы отображаете целые числа в целые числа, используйте SparseIntArray.

Добавить или обновить элементы

Используйте put(или append) для добавления элементов в массив.

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

Обратите внимание, что intключи не должны быть в порядке. Это также может быть использовано для изменения значения в конкретном intключе.

Удалить предметы

Используйте remove(или delete) для удаления элементов из массива.

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

intПараметр является ключевым целым числом.

Поиск значений для ключа int

Используйте, getчтобы получить значение для некоторого целочисленного ключа.

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

Вы можете использовать, get(int key, E valueIfKeyNotFound)если хотите избежать nullпропавших ключей.

Перебирать предметы

Вы можете использовать keyAtи valueAtнекоторый индекс для циклического перемещения по коллекции, потому что он SparseArrayподдерживает отдельный индекс, отличный от 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

Обратите внимание, что ключи упорядочены по возрастанию, а не в том порядке, в котором они были добавлены.

Suragch
источник
18

Тем не менее, всякий раз, когда я пытаюсь использовать HashMap с целочисленными ключами в проекте Android, intelliJ говорит мне, что вместо этого я должен использовать SparseArray.

Это только предупреждение из этой документации об этом редком массиве:

Он предназначен для более эффективного использования памяти, чем использование HashMap для отображения целых чисел на объекты

Это SparseArrayсделано для более эффективного использования памяти, чем при использовании обычного HashMap, то есть не допускает множественных пробелов в массиве, как в HashMap. Вам не о чем беспокоиться, вы можете использовать традиционную HashMap, если вы не хотите беспокоиться о распределении памяти для устройства.

Rod_Algonquin
источник
5
Пункты о сохранении памяти, очевидно, верны, но я никогда не понимал, почему Android не мог заставить SparseArray <T> реализовать Map <Integer, T>, чтобы вы получили эффективную реализацию памяти Map - лучшее из обоих миров.
Пол Боддингтон
3
@PaulBoddington также помнит, SparseArrayчто ключевым целым числом не может быть поле Auto, что является еще одной операцией и экономически выгодным. вместо Map он будет автоматически вставлять примитивное целое числоInteger
Rod_Algonquin
Также верно, но если бы они перегрузили метод put, включив метод с подписью put (int a, T t), вы все равно сможете поместить пары ключ-значение в карту без автоматической упаковки ключей. Я просто думаю, что Collections Framework является настолько мощным (одна из лучших причин для использования Java), что безумием не пользоваться этим.
Пол Боддингтон
6
Коллекции @PaulBoddington основаны на объектах, а не на примитиве, поэтому он не будет работать в API коллекций
Rod_Algonquin
10

Разреженный массив в Java - это структура данных, которая сопоставляет ключи со значениями. Та же идея, что и у карты, но другая реализация:

  1. Карта представлена ​​в виде массива списков, где каждый элемент в этих списках является парой ключ-значение. И ключ, и значение являются экземплярами объекта.

  2. Разреженный массив состоит просто из двух массивов: массивов ключей (примитивов) и массива значений (объектов). В этих индексах массивов могут быть пробелы, отсюда и термин «разреженный» массив.

Основной интерес SparseArray заключается в том, что он экономит память, используя примитивы вместо объектов в качестве ключа.

Ганеш Катикар
источник
10

После некоторого поиска в Google я пытаюсь добавить информацию к уже опубликованным ответам:

Айзек Тейлор провел сравнение производительности для SparseArrays и Hashmaps. Он утверждает, что

Hashmap и SparseArray очень похожи для структур данных размером до 1000

и

когда размер был увеличен до отметки 10000 [...], Hashmap обладает большей производительностью при добавлении объектов, тогда как SparseArray имеет более высокую производительность при извлечении объектов. [...] При размере 100 000 [...] Hashmap очень быстро теряет производительность

Сравнение Edgblog показывает, что SparseArray требуется гораздо меньше памяти, чем HashMap, из-за меньшего ключа (int против Integer) и того факта, что

экземпляр HashMap.Entry должен отслеживать ссылки на ключ, значение и следующую запись. Кроме того, он также должен хранить хэш записи как int.

В заключение я бы сказал, что разница может иметь значение, если вы собираетесь хранить много данных на своей карте. В противном случае просто проигнорируйте предупреждение.

Себастьян
источник
4

Документация Android для SparseArray гласит: «Обычно он медленнее, чем традиционный HashMap».

Да, правильно. Но когда у вас есть только 10 или 20 предметов, разница в производительности должна быть незначительной.

Если вы пишете код с использованием HashMaps, а не SparseArrays, ваш код будет работать с другими реализациями Map, и вы сможете использовать все API-интерфейсы Java, предназначенные для карт.

Я думаю, что чаще всего мы используем только HashMapдля поиска значения, связанного с ключом, в то время как SparseArrayэто действительно хорошо.

Если вы пишете код, используя HashMaps, а не SparseArrays, ваш код будет работать в не-Android проектах.

Исходный код SparseArray довольно прост и понятен, так что вам не нужно тратить много времени на его перенос на другие платформы (с помощью простого COPY & Paste).

Карта переопределяет equals () и hashCode (), тогда как SparseArray не

Все, что я могу сказать, - (большинству разработчиков) кого это волнует?

Другим важным аспектом SparseArrayявляется то , что он использует только массив для хранения всех элементов , в то время как HashMapиспользование Entry, так SparseArrayстоит значительно меньше памяти , чем HashMapсм это

suitianshi
источник
1

К сожалению, компилятор выдает предупреждение. Я предполагаю, что HashMap слишком часто использовался для хранения предметов.

SparseArrays имеют свое место. Учитывая, что они используют алгоритм двоичного поиска, чтобы найти значение в массиве, вы должны учитывать, что вы делаете. Двоичный поиск - O (log n), а поиск по хешу - O (1). Это не обязательно означает, что бинарный поиск медленнее для данного набора данных. Тем не менее, по мере увеличения количества записей, власть хеш-таблицы вступает во владение. Отсюда комментарии, где небольшое количество записей может быть равным и, возможно, лучше, чем использование HashMap.

Хэш-карта хороша только как хеш-код, и на нее также может влиять коэффициент загрузки (я думаю, что в более поздних версиях они игнорируют коэффициент загрузки, поэтому его можно лучше оптимизировать). Они также добавили вторичный хеш, чтобы убедиться, что он хорош. Также причина, по которой SparseArray работает очень хорошо для относительно небольшого количества записей (<100).

Я бы посоветовал вам, если вам нужна хеш-таблица и вы хотите лучше использовать память для примитивного целого числа (без автобокса) и т. Д., Попробуйте trove. ( http://trove.starlight-systems.com - лицензия LGPL). (Нет связи с trove, как и их библиотека)

Благодаря упрощенному мульти-декс-билдингу у вас нет необходимости переупаковывать набор для того, что вам нужно. (У Троу много классов)

Брюс
источник