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