В чем преимущество хэш-таблицы по сравнению с массивом

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

Понимаете ли вы, за счёт чего хэш-таблица быстрая и чем за это платит. На Android следом часто спрашивают про SparseArray и ArrayMap: зачем они нужны, если есть HashMap.

Как отвечать

Сравнивать стоит по операциям, а не по принципу «что лучше»:

• доступ: массив отдаёт элемент по индексу за O(1), хэш-таблица по ключу за O(1) в среднем. Если ключ не индекс, а строка или id, массиву остаётся перебор за O(n) или бинарный поиск за O(log n) по отсортированным данным;
• ключи: в хэш-таблице ключом может быть любой объект с согласованными equals() и hashCode();
• худший случай: при множестве коллизий операции деградируют. В HashMap начиная с Java 8 длинная корзина превращается в дерево, и худший случай становится O(log n) вместо O(n);
• память: HashMap держит массив корзин с коэффициентом загрузки 0,75 и отдельный объект Node на каждую запись, плюс упаковку Int в Integer. Массив примитивов лежит в памяти подряд, он компактнее и дружелюбнее к кэшу процессора;
• порядок: массив сохраняет порядок, HashMap нет. В Kotlin mutableMapOf() возвращает LinkedHashMap, который помнит порядок вставки, а hashMapOf() даёт обычный HashMap.

Для Android добавьте альтернативы: SparseArray из android.util (и SparseArrayCompat из androidx.collection) хранит ключи int в отсортированном массиве без упаковки, ArrayMap держит пары в двух массивах. Поиск там O(log n), зато меньше памяти и работы сборщику мусора. По документации на сотнях элементов разница в скорости несущественна, а на больших объёмах лучше HashMap.

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

Говорят, что хэш-таблица всегда работает за O(1). Это средняя оценка, она держится на хорошей хэш-функции, а при расширении таблицы все элементы перераспределяются.

Кладут в HashMap изменяемый объект как ключ и потом меняют его поля. hashCode() становится другим, и запись оказывается недостижимой.

Утверждают, что хэш-таблица экономит память, потому что растёт динамически. Наоборот, она всегда держит запас пустых корзин и накладные объекты, а растущий массив есть и так: ArrayList.