ArrayMap<K, V> – это хранилище общего назначения пар ключ-значение.
ArrayMap реализует интерфейс
Map<K, V> и добавлен в Android SDK как более эффективная по памяти замена
HashMap.
Реализация
ArrayMap похожа на
SparseArray.
ArrayMap хранит отсортированный массив хэш-кодов ключей и массив объектов ключ-значение.
При добавлении элемента в
ArrayMap, бинарным поиском ищется место (index) в массиве, куда будет добавлен хэш-код ключа. После этого ключ добавляется в массив объектов на место
index * 2, а значение на место
index * 2 + 1.
Для разрешения
коллизий используется метод открытой адресации. В случае коллизии, для места вставки хэш-кода используется соседнее место
index + 1. В
HashMap для разрешения коллизий используется метод цепочек.
Как и
SparseArray,
ArrayMap медленнее, чем
HashMap, потому что ищет позицию ключа бинарным поиском, а вставка и удаление элементов требуют выполнения вставки и удаления на массивах.
В отличие от большинства стандартных Java-коллекций,
ArrayMap при удалении элементов сокращает массивы, используемые для хранения данных.
ArraySet<E> реализует интерфейсы
Collection<E> и
Set<E>. Соотносится с
ArrayMap также как
HashSet с
HashMap, т.е. в качестве ключей выступают добавляемые элементы.