Где применяется
1. Задача
Set хранит просто значения и отвечает, лежит ли что-то в мешке. Map (по-русски его называют картой или словарём) умеет больше. Он связывает каждый ключ со значением. По ключу можно найти то, что ты под него положил.
Вот задача, где это нужно. У тебя много записей вида { id, type }. Их надо разложить по корзинам: все id с типом "click" вместе, все id с типом "view" вместе и так далее. Можно пройти все записи заново для каждого типа, но это цикл внутри цикла, и он работает медленно. Лучше пройти записи один раз и по ходу класть каждый id в нужную корзину. Map даёт такие корзины и находит каждую по имени примерно за один шаг.
2. Простыми словами
Возьми три записи из урока: a с типом click, b с типом view и c с типом click. Нужно получить click → [a, c] и view → [b].
Map справляется с этим за один проход. Каждый тип это ключ, а под каждым ключом лежит список id. Читаешь a·click: ключа click ещё нет, поэтому заводишь его с пустым списком и кладёшь туда a. Читаешь b·view: заводишь ключ view и кладёшь b в его список. Читаешь c·click: ключ click уже есть, добавляешь c в его список. Каждую запись ты прочитал один раз. Нужный список каждый раз находился за один шаг, без поиска по остальным спискам.
3. Идея
Map это хранилище пар ключ → значение. Положить пару: map.set(ключ, значение). Прочитать значение: map.get(ключ). Проверить, есть ли ключ: map.has(ключ). Удалить: map.delete(ключ). Если запросить ключ, который никогда не задавали, придёт undefined. Это ответ «здесь ничего не лежит».
Для этой задачи Map удобнее обычного объекта по двум причинам. Первая: ключом может быть что угодно (число, строка, даже другой объект), и ключ сохраняет свой тип. Объект превратил бы число 30 в текст "30". Вторая: Map помнит порядок, в котором ты добавлял ключи. Поэтому map.keys() выдаёт ключи в порядке их первого появления. Есть и третья мелочь. Обычный объект не может безопасно хранить ключ "constructor": это имя уже занято у каждого объекта. У Map занятых имён нет.
Группировка использует Map как мультикарту: под каждым ключом лежит список значений, и ты продолжаешь его пополнять. Приём всегда один. Для каждого элемента смотришь на его ключ. Если списка под этим ключом ещё нет, заводишь пустой. Потом добавляешь элемент в список своего ключа.
Проследим группировку на [a·click, b·view, c·click]. Видим a·click: списка click ещё нет, заводим его и кладём a, получаем click → [a]. Видим b·view: списка view ещё нет, заводим и кладём b, получаем view → [b]. Видим c·click: список click уже есть, кладём c, получаем click → [a, c]. Хватило одного прохода. Ключ click стоит раньше view, потому что появился первым.
4. Во что это обходится
Время O(n): один проход по записям, и каждый has, get и set занимает примерно один шаг. Память O(n): каждый id в итоге лежит в одном из списков один раз, и ещё по одной записи на каждый отдельный ключ. Вложенного цикла нет, повторного чтения нет. Разложить n записей по корзинам стоит столько же по порядку величины, сколько просто их прочитать.
Получить ключи через map.keys() стоит O(k), где k это число отдельных ключей. Ключи приходят в том порядке, в котором их впервые добавили. Они не отсортированы.
6. Где это встречается
Группировка по ключу встречается в реальном коде очень часто. Дашборд логов (экран с журналами событий) раскладывает строки по уровню важности, чтобы каждый блок показывал свой уровень. Аналитика сначала собирает события каждого пользователя или каждой сессии в группу, а потом считает что-то по каждой группе. Система заказов группирует товары по складу, чтобы спланировать отгрузки. Любой запрос «сгруппируй это по тому» решается картой списков за один проход: в SQL это GROUP BY, в отчёте это разделы, в интерфейсе это секции. Простой вариант, одно значение на ключ, тоже встречается везде: хранилище настроек, кэш (быстрая копия данных под рукой) вида id → запись, таблица «код → подпись».
На LeetCode
Задачи, где каждому ключу нужно своё значение или свой список, например таблица соответствий, сопоставление букв со словами или группировка по ключу за один проход.
Map из римской буквы в её значение и есть таблица, из которой читает всё решение.
Свяжи каждую букву с её словом, а каждое слово с буквой, и остановись на первом противоречии.
Те же две Map, только теперь из буквы в букву.
Группируй людей по размеру группы через Map со списками и закрывай список, как только он заполнился.
Твоя задача (Tier 1)
Напиши две функции: groupBy(records) и keysInOrder(map).
groupBy раскладывает записи по группам по их type. keysInOrder читает ключи карты в том порядке, в каком их добавляли.
- Вход для
groupBy:records, список записей, у каждой естьtypeиid. Пример:[{id:"a",type:"x"}, {id:"b",type:"x"}]. - Возвращает: карту, где каждому
typeсоответствует список егоid. Ключи идут в порядке первого появления типа. - Вход для
keysInOrder:map, карта. - Возвращает: её ключи списком, в порядке добавления.
Шаги:
- Для
groupBy: заведи пустую картуgroups. Для каждой записи: если еёtypeещё не ключ вgroups, положи под этот ключ пустой список. Затем добавьidзаписи в список для еёtype. Верниgroups. - Для
keysInOrder: верни ключи карты списком, в порядке добавления (не отсортированные).
Готово, когда проходят все тесты:
groupBy:
[{id:"a",type:"click"}, {id:"b",type:"view"}, {id:"c",type:"click"}]->click: ["a","c"],view: ["b"][{id:"a",type:"x"}, {id:"b",type:"x"}]->x: ["a","b"](один тип, одна группа)[{id:"a",type:"x"}, {id:"b",type:"y"}]->x: ["a"],y: ["b"][]-> пустая карта (не должно падать)
keysInOrder:
- ключи добавлены в порядке
z, a, m->["z","a","m"](порядок первой встречи, не сортировка) - ключи добавлены
30, 10, 20->[30, 10, 20] - пустая карта ->
[]
Практика
groupBy / keysInOrder
export function groupBy(records) {
// Your code here. The task is described in the box above the editor.
}
export function keysInOrder(map) {
// Your code here. The task is described in the box above the editor.
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.