Какая сложность получения данных из Map по ключу?

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

Реализация может использовать хеш-таблицу или другую подходящую структуру; строгое O(1) для каждого вызова get спецификацией не обещано. Коллизии, размер ключей и детали движка влияют на практическую стоимость. На собеседовании различайте обычную оценку конкретной структуры и минимальное требование стандарта к Map.

Источник: developer.mozilla.org.