Какие типы Map существуют кроме HashMap

Что проверяют

Знаете ли вы реализации Map не списком названий, а по поведению: порядок, сложность, потокобезопасность, отношение к null. На Android следом почти всегда спрашивают, чем ArrayMap и SparseArray лучше HashMap и когда они проигрывают.

Как отвечать

Начните с JDK, коротко и с назначением:

• LinkedHashMap: HashMap плюс двусвязный список, хранит порядок вставки. С флагом accessOrder в конструкторе держит порядок доступа, на этом построен LruCache;
• TreeMap: красно-чёрное дерево, ключи отсортированы, операции за O(log n), есть floorKey, headMap и другие навигационные методы. null-ключ при естественном порядке бросит NullPointerException;
• ConcurrentHashMap: потокобезопасная, чтение без блокировок, запись через CAS и блокировку отдельной корзины. null не принимает ни в ключах, ни в значениях;
• WeakHashMap: ключи на слабых ссылках, запись исчезает, когда ключ собран GC;
• IdentityHashMap: сравнивает ключи через ==, а не через equals;
• EnumMap: ключи из одного enum, внутри массив по ordinal, очень компактна.

Затем Android-специфика, ради которой вопрос и задают:

• ArrayMap (есть в android.util и androidx.collection): два массива, хэши отсортированы, поиск бинарный за O(log n). Экономит память на небольших коллекциях, до нескольких сотен элементов;
• SparseArray, SparseIntArray, LongSparseArray: ключ примитивный int или long, нет автоупаковки в Integer и объектов-узлов на каждую запись.

В Kotlin полезно добавить, что mutableMapOf() возвращает LinkedHashMap, а hashMapOf() обычный HashMap.

Где спотыкаются

Называют ConcurrentHashMap полностью безблокировочной. Запись там блокирует корзину, а составная операция вроде get и затем put атомарной не становится, для неё есть compute и merge.

Советуют ArrayMap везде «ради памяти». На тысячах элементов бинарный поиск и сдвиг массивов при вставке проигрывают HashMap.

Предлагают Hashtable или Collections.synchronizedMap как современный выбор. Оба блокируют всю карту на каждую операцию, в новом коде их место занимает ConcurrentHashMap.