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