# Map, Set і масиви: вибір структури даних на співбесіді

> Коли Map кращий за об’єкт, навіщо Set, яка складність базових операцій і дві задачі, де правильна структура даних перетворює O(n²) на O(n). З кодом до і після.

- Автор: Юра Скиба (https://cookiesoftware.io)
- Опубліковано: 2026-09-24
- Категорія: JavaScript і TypeScript
- Canonical: https://cookiesoftware.io/blog/javascript-struktury-danykh

---

**Коротка відповідь.** У 90% задач на співбесіді достатньо чотирьох структур: масив, об'єкт, `Map` і `Set`. Вибір між ними – це не смак, а складність операцій: пошук у масиві коштує O(n), у Set і Map – у середньому O(1). Якщо твоє рішення містить `includes` або `find` усередині циклу – майже напевно його можна прискорити з O(n²) до O(n), просто замінивши структуру. Нижче – коли що брати і дві задачі з кодом «до/після».

## Шпаргалка складності

| Операція | Масив | Об'єкт | Map | Set |
|---|---|---|---|---|
| Пошук за ключем/значенням | O(n) (`includes`, `find`) | O(1) за ключем | O(1) (`get`, `has`) | O(1) (`has`) |
| Додавання | O(1) у кінець (`push`) | O(1) | O(1) (`set`) | O(1) (`add`) |
| Видалення | O(n) (`splice`, пошук індексу) | O(1) (`delete`) | O(1) (`delete`) | O(1) (`delete`) |
| Збереження порядку вставки | так | практично так, з нюансами | так | так |
| Розмір | `length` | `Object.keys(obj).length` – O(n) | `size` – O(1) | `size` – O(1) |

Оцінки для Map/Set – середньостатистичні (у специфікації «sublinear on average»); на співбесіді достатньо казати «в середньому O(1)».

## Коли Map замість об'єкта

Об'єкт – теж «ключ → значення», але Map варто обирати, коли:

- **ключі не рядки**: у Map ключем може бути число, об'єкт, будь-що; об'єкт мовчки перетворить ключ на рядок (`obj[1]` і `obj['1']` – одне й те саме поле);
- **колекція динамічна**: часто додаєш і видаляєш записи – Map для цього створений, має `size` і зручну ітерацію `for (const [key, value] of map)`;
- **потрібна чистота**: в об'єкта є прототип, і ключ на кшталт `'toString'` може здивувати; `new Map()` порожній по-справжньому.

Об'єкт лишається кращим для **фіксованої структури** – конфіг, DTO, параметри функції: там працює деструктуризація і типізація полів. Довідково: [Map на MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map).

## Навіщо Set

Set – це «колекція унікальних значень із миттєвим has». Два типові застосування:

```js
// 1. Унікалізація
const tags = ['js', 'react', 'js', 'ts', 'react'];
const unique = [...new Set(tags)]; // ['js', 'react', 'ts']

// 2. Швидка перевірка членства
const blockedIds = new Set(blockedUsers.map((user) => user.id));
const visible = posts.filter((post) => !blockedIds.has(post.authorId));
```

У другому прикладі важлива деталь для співбесіди: Set будується **один раз** (O(n)), а потім кожна перевірка – O(1). Якби замість цього був `blockedUsers.some(...)` усередині `filter`, вийшло б O(n·m).

## Задача 1: перший дубль у масиві

**Наївно, O(n²):**

```js
function firstDuplicate(items) {
  for (let i = 0; i < items.length; i++) {
    // indexOf сам пробігає масив – цикл у циклі
    if (items.indexOf(items[i]) !== i) return items[i];
  }
  return null;
}
```

**Із Set, O(n):**

```js
function firstDuplicate(items) {
  const seen = new Set();
  for (const item of items) {
    if (seen.has(item)) return item;
    seen.add(item);
  }
  return null;
}
```

На масиві з 10 000 елементів різниця – мільйони зайвих порівнянь проти одного проходу. Саме вміння **побачити прихований цикл** (`indexOf`, `includes`, `find` всередині ітерації) і назвати складність вголос відрізняє підготовленого кандидата.

## Задача 2: злиття двох списків за id

Треба доповнити список користувачів даними з іншого списку.

**Наївно, O(n·m):**

```js
function mergeUsers(users, profiles) {
  return users.map((user) => ({
    ...user,
    profile: profiles.find((profile) => profile.userId === user.id) ?? null,
  }));
}
```

**Із Map-індексом, O(n + m):**

```js
function mergeUsers(users, profiles) {
  const profileByUserId = new Map(
    profiles.map((profile) => [profile.userId, profile])
  );
  return users.map((user) => ({
    ...user,
    profile: profileByUserId.get(user.id) ?? null,
  }));
}
```

Патерн «спочатку побудуй індекс, потім звіряйся з ним» покриває величезний клас задач: групування, join двох API-відповідей, підрахунок частот. Він же з'являється в [React-задачах з дедуплікацією стану](/blog/react-functional-state-update).

## Задача 3: підрахунок частот через Map

Третій наскрізний патерн – частотний словник. Класика: перевірити, чи два слова є анаграмами.

```js
function charCount(word) {
  const counts = new Map();
  for (const char of word) {
    counts.set(char, (counts.get(char) ?? 0) + 1);
  }
  return counts;
}

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const counts = charCount(a);
  for (const char of b) {
    const left = counts.get(char);
    if (!left) return false;        // символа немає або вже вичерпано
    counts.set(char, left - 1);
  }
  return true;
}

console.assert(isAnagram('кіт', 'тік') === true, 'анаграма');
console.assert(isAnagram('кіт', 'кit') === false, 'різні алфавіти');
```

Рядок `counts.get(char) ?? 0` – маленький, але показовий: оператор `??` замість `||` не сплутає збережений `0` з «немає значення». Той самий частотний патерн розв'язує «найпопулярніший елемент», «перший неповторюваний символ» і половину задач про рядки.

Окремо згадай `Object.groupBy` / `Map.groupBy` – відносно нові вбудовані методи групування. Якщо середовище співбесіди їх підтримує, можна використати; якщо ні – написати групування через Map руками, як вище, і це навіть виграшніше: видно, що ти розумієш механіку, а не лише API.

## А що з сортуванням?

Сортування – найдорожча з «побутових» операцій: `Array.prototype.sort` працює за O(n·log n). Тому відповідь «відсортую і порівняю сусідів» для пошуку дублів формально правильна, але гірша за Set: O(n·log n) проти O(n), плюс `sort` без копії мутує вхідний масив. Якщо все ж сортуєш – кажи явно: «зроблю копію через toSorted або spread, щоб не мутувати вхід». Такі деталі й складають враження від відповіді.

## WeakMap за 30 секунд

`WeakMap` тримає ключі-об'єкти «слабко»: якщо на об'єкт більше немає посилань, збирач сміття забере і його, і зв'язане значення. Типове застосування – прив'язати метадані до чужих об'єктів (наприклад, DOM-вузлів), не заважаючи їх звільненню. На співбесіді достатньо знати це і те, що WeakMap не ітерується.

## Що тренувати далі

Візьми три свої розв'язані задачі й перевір кожну питанням: «чи є тут пошук усередині циклу?» Якщо є – перепиши через Set або Map і сформулюй уголос стару та нову складність. Більше задач цього типу – у добірці [JavaScript live coding](/blog/javascript-live-coding-zadachi), а загальна структура підготовки – у [гайді з JavaScript-співбесіди](/blog/javascript-interview-guide).