re:re:actable
Урок 024 минуты чтения

Как использовать Map и чем Map отличается от Object

На этой странице
Кратко

Map - структура ключ-значение. В алгоритмах ее используют для частот, индексов, кеша, adjacency list, memoization и быстрого поиска по ключу.

Object - обычный JS-объект со строковыми/symbol ключами и prototype-наследованием, а Map - специализированная коллекция ключ-значение, где ключом может быть любое значение. Для алгоритмов чаще удобнее Map.

Вопрос

Как использовать Map в алгоритмах и почему для словаря Map часто удобнее Object?

Базовый API

const count = new Map<string, number>()
 
count.set('a', 1)
count.set('a', (count.get('a') ?? 0) + 1)
 
console.log(count.has('a'))
console.log(count.get('a'))
console.log(count.delete('a'))
console.log(count.size)

Частотный словарь

function frequency(words: string[]): Map<string, number> {
  const map = new Map<string, number>()
 
  for (const word of words) {
    map.set(word, (map.get(word) ?? 0) + 1)
  }
 
  return map
}

Two Sum

function twoSum(nums: number[], target: number): [number, number] | null {
  const indexByValue = new Map<number, number>()
 
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
 
    if (indexByValue.has(need)) {
      return [indexByValue.get(need)!, i]
    }
 
    indexByValue.set(nums[i], i)
  }
 
  return null
}

Time O(n), space O(n).

Как это работает на nums = [2, 7, 11, 15], target = 9:

inums[i]needindexByValue до проверкиДействие
027пусто7 не встречалось, запоминаем 2 -> 0
1722 -> 02 уже было на индексе 0, ответ [0, 1]

Вместо второго вложенного цикла мы спрашиваем Map: "встречалось ли нужное число раньше?". Это O(1) в среднем, поэтому весь алгоритм линейный.

Object как словарь

const count: Record<string, number> = {}
 
count.apple = 1
count.apple = (count.apple ?? 0) + 1

Работает хорошо для простых строковых ключей. Но у обычного объекта есть прототип, и это ловушка:

const count: Record<string, number> = {}
 
console.log('toString' in count) // true - ключа нет, но он найден в прототипе
console.log(count['constructor']) // [Function: Object]

Если ключи приходят из данных (например, слова из текста), слово constructor сломает подсчет. Обойти можно через Object.create(null) или Object.hasOwn, но проще взять Map.

Сравнение Object и Map

КритерийObjectMap
Ключиstring/symbol, остальное приводится к строкелюбые значения
РазмерObject.keys(obj).length - O(n)map.size - O(1)
Prototype keysесть рискнет такого риска
Порядок итерациисложные правила (числовые ключи идут первыми)порядок вставки
Итерациячерез Object.entriesfor...of map
Алгоритмыможночасто удобнее

Объектные ключи

const a = { id: 1 }
const b = { id: 1 }
 
const map = new Map<object, string>()
map.set(a, 'first')
 
console.log(map.get(a)) // first
console.log(map.get(b)) // undefined

Объекты сравниваются по ссылке, не по содержимому. Если нужен ключ "по содержимому", например для координат, превращают его в строку: `${row}:${col}`.

В обычном объекте ключ-объект вообще приводится к строке "[object Object]", поэтому все объекты попадут в одну ячейку:

const obj: Record<string, string> = {}
obj[a as any] = 'first'
obj[b as any] = 'second'
 
console.log(Object.keys(obj)) // ['[object Object]']

Что отвечать на собеседовании?

Map хранит пары ключ-значение и подходит для быстрого доступа по ключу. В алгоритмах я использую Map для frequency counter, хранения индексов, memoization, adjacency list и кешей. В отличие от object, Map поддерживает ключи любых типов и имеет удобные методы set, get, has, delete, size.

Для частот по строкам можно использовать object или Map, но Map лучше выражает намерение "словарь" и поддерживает ключи любых типов. Object хорош для простых records, особенно когда структура заранее известна. В алгоритмах я обычно выбираю Map, чтобы избежать проблем с prototype keys и удобно работать с size, has, get, set.

Что важно помнить: частые ошибки

  • Использовать map.get(key) || 0, если значение может быть 0, false или пустой строкой.
  • Забывать, что объектные ключи сравниваются по ссылке.
  • Использовать object там, где ключ не строка.
  • Не обновлять значение через set.
  • Искать у Map методы массива: map.map, map.filter не существуют - сначала [...map.entries()].
  • Проверять наличие через truthy-value вместо has.
  • Не учитывать prototype keys у обычного объекта.
  • Путать Record<string, T> и Map<K, V>.

Мини-шпаргалка

  • set - записать.
  • get - получить.
  • has - проверить.
  • delete - удалить.
  • size - размер.
  • Частоты: (map.get(x) ?? 0) + 1.
  • Object - для записей с заранее известными полями.
  • Map - для словаря, который наполняется по ходу алгоритма.
  • Ключи Map любые, объекты сравниваются по ссылке.

Документация

MDN: Map, MDN: Objects vs. Maps.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам