All you need to know about ArrayMap & SparseArray - статья об ArrayMap и SparseArray, двух фирменных, но не так хорошо известных коллекциях Android. Обе коллекции по сути аналоги HashMap из Java с тем исключением, что они созданы специально для минимизации потребления оперативной памяти.
В отличие HashMap, который для хранения каждого объекта создает новый объект и сохраняет его в массиве, ArrayMap не создает дополнительных объектов, но использует два массива: mHashes для последовательного хранения хешей ключей, и mArray - для хранения ключей и их значений (друг за другом). Начальный размер первого - 4, второго - 8.
При добавлении элемента ArrayMap сначала добавляет его хэш в первый массив, а затем добавляет ключ и значение во второй массив, где индекс ключа высчитывается как индекс хэша в массиве mHashes, умноженный на два, а индекс значения как индекс ключа плюс 1. В случае коллизии (когда два разных ключа имеют одинаковый хэш) ArrayMap производит линейный поиск ключа в mArray и, если он не найден, добавляет новый хэш в mHashes и новые ключ:значение в mArray. При достижении предельного размера массивов ArrayMap копирует их в новый массив, размер которого высчитывается так: oldSize+(oldSize>>1) (4 -> 8 -> 12 -> 18 -> 27 -> ...).
SparseArray представляет собой тот же ArrayMap, но предназначенный для работы с типами данных, где ключ - это int, а значение может быть либо объектом, либо простым типом данных: int, long, boolean (SparseIntArray, SparseLongArray, SparseBooleanArray). В итоге SparseArray нет необходимости хранить обертки над простыми типами данных.
Благодаря избавлению от необходимости хранить дополнительный объект для каждого элемента, ArrayMap оказывается примерно на 25% экономнее HashMap, а SparseArray почти в два раза экономнее. В то же время ArrayMap и SparseArray в целом в два раза медленнее HashMap.
Выводы:
- По возможности используй ArrayMap;
- Используй SparseArray если ключи имеют тип int;
- Если размер коллекции известен - указывай его в конструкторе.
В отличие HashMap, который для хранения каждого объекта создает новый объект и сохраняет его в массиве, ArrayMap не создает дополнительных объектов, но использует два массива: mHashes для последовательного хранения хешей ключей, и mArray - для хранения ключей и их значений (друг за другом). Начальный размер первого - 4, второго - 8.
При добавлении элемента ArrayMap сначала добавляет его хэш в первый массив, а затем добавляет ключ и значение во второй массив, где индекс ключа высчитывается как индекс хэша в массиве mHashes, умноженный на два, а индекс значения как индекс ключа плюс 1. В случае коллизии (когда два разных ключа имеют одинаковый хэш) ArrayMap производит линейный поиск ключа в mArray и, если он не найден, добавляет новый хэш в mHashes и новые ключ:значение в mArray. При достижении предельного размера массивов ArrayMap копирует их в новый массив, размер которого высчитывается так: oldSize+(oldSize>>1) (4 -> 8 -> 12 -> 18 -> 27 -> ...).
SparseArray представляет собой тот же ArrayMap, но предназначенный для работы с типами данных, где ключ - это int, а значение может быть либо объектом, либо простым типом данных: int, long, boolean (SparseIntArray, SparseLongArray, SparseBooleanArray). В итоге SparseArray нет необходимости хранить обертки над простыми типами данных.
Благодаря избавлению от необходимости хранить дополнительный объект для каждого элемента, ArrayMap оказывается примерно на 25% экономнее HashMap, а SparseArray почти в два раза экономнее. В то же время ArrayMap и SparseArray в целом в два раза медленнее HashMap.
Выводы:
- По возможности используй ArrayMap;
- Используй SparseArray если ключи имеют тип int;
- Если размер коллекции известен - указывай его в конструкторе.