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, т.е. в качестве ключей выступают добавляемые элементы.