SparseArray<E> – это
ассоциативный массив, в котором ключами выступают целые числа. Другими словами это специфичная андроидная замена
HashMap<Integer, E>.
SparseArray эффективнее чем
HashMap по памяти, т.к. работает с примитивом
int в качестве ключа и не выполняет операции
боксинга / анбоксинга.
SparseArray упрощенно устроен следующим образом:
• Хранится целочисленный массив ключей:
int[] mKeys. Массив ключей отсортирован по возрастанию;
• Хранится массив значений:
Object[] mValues;
• Когда происходит вставка пары ключ-значение, сначала алгоритмом бинарного поиска ищется место-индекс в массиве ключей, с сохранением порядка. После этого ключ вставляется по найденному индексу в массив
mKeys, а значение вставляется по тому же индексу в массив
mValues;
• При получении значения из
SparseArray по ключу, бинарным поиском ищется индекс ключа в массиве
mKeys, и возвращается значение из
mValues по найденному индексу.
SparseArray медленнее, чем
HashMap, потому что ищет позицию ключа бинарным поиском, а вставка и удаление элементов требует выполнение вставки и удаления на массивах.
Для оптимизации удаления
SparseArray не удаляет элемент из массива сразу, а записывает вместо него специальный объект
DELETED. Это синглтон, который хранится в приватном статическом поле класса
SparseArray.
Такое решение позволяет переиспользовать места в массиве. Реальное удаление выполняется позже, при вызове других методов
SparseArray.
Помимо параметризованного
SparseArray<E> Android SDK предоставляет классы
SparseLongArray,
SparseIntArray,
SparseBooleanArray, которые в качестве значений принимают соответствующие примитивы.