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, которые в качестве значений принимают соответствующие примитивы.