16 липня 2023 р.

Map та Set

Зараз ми знаємо про наступні складні структури даних:

  • Об’єкти для зберігання іменованих колекцій.
  • Масиви для зберігання впорядкованих колекцій.

Але цього не завжди достатньо в реальному житті. Ось чому існують Map та Set.

Map

Map – це колекція ключ/значення, як і Object. Але основна відмінність полягає в тому, що Map дозволяє мати ключі будь-якого типу.

Методи та властивості:

  • new Map() – створює колекцію.
  • map.set(key, value) – зберігає значення value за ключем key.
  • map.get(key) – повертає значення за ключем; повертає undefined якщо key немає в колекції.
  • map.has(key) – повертає true якщо key існує, інакше false.
  • map.delete(key) – видаляє елемент (пару ключ/значення) за ключем.
  • map.clear() – видаляє всі елементи колекції.
  • map.size – повертає поточну кількість елементів.

Наприклад:

let map = new Map();

map.set('1', 'str1');   // рядок як ключ
map.set(1, 'num1');     // цифра як ключ
map.set(true, 'bool1'); // булеве значення як ключ

// пам’ятаєте звичайний об’єкт `Object`? Він перетворює всі ключі в рядок
// Map зберігає тип ключів, так що в цьому випадку ми отримаємо 2 різних значення:
alert( map.get(1) );   // 'num1'
alert( map.get('1') ); // 'str1'

alert( map.size ); // 3

Як ми бачимо, на відміну від об’єктів, ключі не були приведені до рядків. Можна використовувати будь-які типи даних для ключів.

map[key] не є правильним методом використання Map

Хоча map[key] також працює, але такий спосіб присвоєння map[key] = 2 використовує колекцію як звичайний JavaScript об’єкт, тобто накладає відповідні обмеження (тільки типи рядки/символи як ключі та інше).

Таким чином ми повинні користуватись map методами: set, get і так далі.

Map також може використовувати об’єкти як ключі.

Наприклад:

let ivan = { name: "Іван" };

// збережімо кількість відвідувань для кожного користувача
let visitsCountMap = new Map();

// об’єкт ivan -- це ключ для значення в колекції Map
visitsCountMap.set(ivan, 123);

alert( visitsCountMap.get(ivan) ); // 123

Об’єкти в якості ключів – це одна з відомих можливостей колекції Map, яку часто використовують. У звичайному об’єкті Object, ми можемо використати ключі-рядки, проте ключі-об’єкти – вже ні.

Розгляньмо такий приклад:

let ivan = { name: "Іван" };
let bohdan = { name: "Богдан" };

let visitsCountObj = {}; // оголосимо звичайний об’єкт

visitsCountObj[bohdan] = 234; // використаємо об’єкт `bohdan` як ключ
visitsCountObj[ivan] = 123; // використаємо `ivan` об’єкт як ключ, `bohdan` об’єкт буде перезаписаний

// Ось як це було записано!
alert( visitsCountObj["[object Object]"] ); // 123

Оскільки visitsCountObj – це об’єкт, він конвертує всі ключі типу Object (такі як ivan і bohdan) до рядка "[object Object]". Це однозначно не той результат, який ми очікуємо.

Як Map порівнює ключі

Порівнюючи ключі, об’єкт Map використовує алгоритм SameValueZero. Це майже таке ж порівняння, що і ===, з тією лише різницею, що NaN вважається рівним NaN. Таким чином NaN може також бути використаний як ключ.

Цей алгоритм не може бути замінений або модифікований.

Послідовні виклики

Кожен виклик map.set повертає об’єкт map, таким чином ми можемо об’єднати виклики в ланцюжок:

map.set('1', 'str1')
  .set(1, 'num1')
  .set(true, 'bool1');

Перебір Map

Для перебору колекції Map є 3 метода:

  • map.keys() – повертає об’єкт-ітератор для ключів,
  • map.values() – повертає об’єкт-ітератор для значень,
  • map.entries() – повертає об’єкт-ітератор зі значеннями виду [ключ, значення], цей варіант типово використовується з for..of.

Наприклад:

let recipeMap = new Map([
  ['огірок',   500],
  ['помідори', 350],
  ['цибуля',   50]
]);

// перебираємо ключі (овочі)
for (let vegetable of recipeMap.keys()) {
  alert(vegetable); // огірок, помідори, цибуля
}

// перебираємо значення (кількість)
for (let amount of recipeMap.values()) {
  alert(amount); // 500, 350, 50
}

// перебір елементів у форматі [ключ, значення]
for (let entry of recipeMap) { // те ж саме, що recipeMap.entries()
  alert(entry); // огірок,500 (і так далі)
}
Використовується порядок вставки

На відміну від звичайних об’єктів Object, в Map перебір відбувається в тому ж порядку, в якому відбувалося додавання елементів.

Крім цього, Map має вбудований метод forEach, схожий з вбудованим методом масивів Array:

// виконуємо функцію для кожної пари (ключ, значення)
recipeMap.forEach( (value, key, map) => {
  alert(`${key}: ${value}`); // огірок: 500 і так далі
});

Object.entries: Map з Object

При створенні Map ми можемо вказати масив (або інший об’єкт-ітератор) з парами ключ-значення для ініціалізації, як тут:

// масив пар [ключ, значення]
let map = new Map([
  ['1',  'str1'],
  [1,    'num1'],
  [true, 'bool1']
]);

alert( map.get('1') ); // str1

Якщо у нас вже є звичайний об’єкт, і ми б хотіли створити з нього Map, то допоможе вбудований метод Object.entries(obj), котрий отримує об’єкт і повертає масив пар ключ-значення для нього, як раз в цьому форматі.

Таким чином ми можемо створити Map з об’єкта наступним чином:

let obj = {
  name: "Іван",
  age: 30
};

let map = new Map(Object.entries(obj));

alert( map.get('name') ); // Іван

В цьому випадку Object.entries повертає масив пар ключ-значення: [ ["name", "Іван"], ["age", 30] ]. Це саме те, що потрібно для створення Map.

Object.fromEntries: Object з Map

Ми щойно створювали Map з простого об’єкта за допомогою Object.entries(obj).

Ми можемо використати Object.fromEntries метод, який виконає зворотну дію: трансформує отриманий масив пар [ключ, значення] в об’єкт. Наприклад:

let prices = Object.fromEntries([
  ['банан', 1],
  ['апельсин', 2],
  ['яблуко', 4]
]);

// тепер prices = { банан: 1, апельсин: 2, яблуко: 4 }

alert(prices.апельсин); // 2

Ми можемо використати Object.fromEntries, щоб отримати звичайний об’єкт з Map.

Наприклад, ми маємо дані в Map, але потрібно їх передати в сторонній код, який чекає простий об’єкт.

Ось як це зробити:

let map = new Map();
map.set('банан', 1);
map.set('апельсин', 2);
map.set('яблуко', 4);

let obj = Object.fromEntries(map.entries()); // робимо простий об’єкт (*)

// Готово!
// obj = { банан: 1, апельсин: 2, яблуко: 4 }

alert(obj.апельсин); // 2

Виклик map.entries() повертає масив пар ключ/значення, як раз в потрібному форматі для Object.fromEntries.

Ми могли б написати рядок (*) ще коротше:

let obj = Object.fromEntries(map); // прибрати .entries()

Це те ж саме, оскільки Object.fromEntries чекає аргументом об’єкт-ітератор, не обов’язково масив. А перебір map якраз повертає пари ключ/значення, як і map.entries(). Так що в підсумку ми матимемо звичайний об’єкт з тими ж ключами/значеннями, що і в map.

Set

Об’єкт Set – це особливий тип колекції: “множина” значень (без ключів), де кожне значення може з’являтися тільки раз.

Основні методи:

  • new Set([iterable]) – створює Set, якщо аргументом виступає об’єкт-ітератор, тоді значення копіюються в Set.
  • set.add(value) – додає нове значення до Set, повертає Set.
  • set.delete(value) – видаляє значення з Set, повертає true, якщо value наявне в множині значень на момент виклику методу, інакше false.
  • set.has(value) – повертає true, якщо value присутнє в множині Set, інакше false.
  • set.clear() – видаляє всі значення множини Set.
  • set.size – повертає кількість елементів в множині.

Родзинкою Set є виклики set.add(value), що повторюються з однаковими значеннями value. Повторні виклики цього методу не змінюють Set. Це причина того, що кожне значення з’являється тільки один раз.

Наприклад, ми очікуємо гостей, і нам необхідно скласти їх список. Але повторні записи не повинні призводити до дублікатів. Кожен гість повинен з’явитися в списку лише один раз.

Множина Set – це саме те, що потрібно для цього:

let set = new Set();

let ivan = { name: "Іван" };
let petro = { name: "Петро" };
let maria = { name: "Марія" };

// підраховуємо гостей, деякі приходять кілька разів
set.add(ivan);
set.add(petro);
set.add(maria);
set.add(ivan);
set.add(maria);

// set зберігає тільки 3 унікальних значення
alert( set.size ); // 3

for (let user of set) {
  alert(user.name); // "Іван" (тоді "Петро" і "Марія")
}

Альтернативою множини Set може виступати масив для зберігання гостей і додатковий код для перевірки вже наявного елемента за допомогою arr.find. Але в цьому випадку буде гірша продуктивність, тому що arr.find проходить весь масив для перевірки наявності елемента. Множина Set краще оптимізована для перевірки унікальності.

Перебір об’єкта Set

Ми можемо перебрати вміст об’єкта set як за допомогою методу for..of, так і використовуючи forEach:

let set = new Set(["апельсини", "яблука", "банани"]);

for (let value of set) alert(value);

// те ж саме з forEach:
set.forEach((value, valueAgain, set) => {
  alert(value);
});

Зауважимо цікаву річ. Функція в forEach у Set має 3 аргументи: значення ‘value’, потім знову те саме значення ‘valueAgain’, і тільки потім цільовий об’єкт. Це дійсно так, значення з’являється в списку аргументів двічі.

Це зроблено для сумісності з об’єктом Map, в якому колбек forEach має 3 аргумента. Виглядає трохи дивно, але в деяких випадках може допомогти легко замінити Map на Set і навпаки.

Set має ті ж вбудовані методи, що і Map:

  • set.keys() – повертає об’єкт-ітератор для значень,
  • set.values() – те ж саме, що set.keys(), для сумісності з Map,
  • set.entries() – повертає об’єкт-ітератор для пар виду [значення, значення], присутній для сумісності з Map.

Підсумки

Map – це колекція ключ/значення.

Методи та властивості:

  • new Map([iterable]) – створює колекцію, можна вказати об’єкт-ітератор (зазвичай масив) з пар [ключ, значення] для ініціалізації.
  • map.set(key, value) – записує по ключу key значення value.
  • map.get(key) – повертає значення по key або undefined, якщо ключ key відсутній.
  • map.has(key) – повертає true, якщо ключ key присутній в колекції, інакше false.
  • map.delete(key) – видаляє елемент по ключу key. Повертає true, якщо key існує на момент виклику функції, інакше false.
  • map.clear() – очищає колекцію від всіх елементів.
  • map.size – повертає поточну кількість елементів.

Відмінності від звичайного об’єкта Object:

  • Що завгодно може бути ключем, в тому числі і об’єкти.
  • Є додаткові методи, властивість size.

Set – колекція унікальних значень, так звана “множина”.

Методи та властивості:

  • new Set([iterable]) – створює Set, можна вказати об’єкт-ітератор (зазвичай масив).
  • set.add(value) – додає значення (якщо воно вже є, то нічого не робить), повертає той же об’єкт set.
  • set.delete(value) – видаляє значення, повертає true якщо value було в множині на момент виклику, інакше false.
  • set.has(value) – повертає true, якщо значення присутній в множині, інакше false.
  • set.clear() – видаляє всі наявні значення.
  • set.size – повертає кількість елементів у множині.

Перебір Map і Set завжди здійснюється в порядку додавання елементів, так що не можна сказати, що це невпорядковані колекції, але поміняти порядок елементів або отримати елемент безпосередньо по його номеру не можна.

Завдання

важливість: 5

Нехай arr – це масив.

Потрібно створити функцію unique(arr), яка повинна повертати масив унікальних елементів arr.

Наприклад:

function unique(arr) {
  /* Твій код */
}

let values = ["Hare", "Krishna", "Hare", "Krishna",
  "Krishna", "Krishna", "Hare", "Hare", ":-O"
];

alert( unique(values) ); // Hare, Krishna, :-O

P.S. В прикладі ми використали рядки, але можуть бути значення будь-якого типу.

P.P.S. Використайте Set для формування множини унікальних значень.

Відкрити пісочницю з тестами.

function unique(arr) {
  return Array.from(new Set(arr));
}

Відкрити рішення із тестами в пісочниці.

важливість: 4

Анаграми – це слова, у яких ті ж букви в тій же кількості, але вони розташовуються в іншому порядку.

Наприклад:

nap - pan
ear - are - era
cheaters - hectares - teachers

Напишіть функцію aclean(arr), яка повертає масив без анаграм.

Наприклад:

let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];

alert( aclean(arr) ); // "nap,teachers,ear" or "PAN,cheaters,era"

З кожної групи анаграм має залишитися тільки одне слово, не має значення яке.

Відкрити пісочницю з тестами.

Щоб знайти всі анаграми, давайте розіб’ємо кожне слово на літери і відсортуємо їх, а потім об’єднаємо масив знову в рядок. Після цього всі анаграми будуть однакові.

Наприклад:

nap, pan -> anp
ear, era, are -> aer
cheaters, hectares, teachers -> aceehrst
...

Ми будемо використовувати відсортовані рядки як ключі в колекції Map, для того щоб зіставити кожному ключу тільки одне значення:

function aclean(arr) {
  let map = new Map();

  for (let word of arr) {
    // розділіть слово на літери, відсортуйте їх та знову з'єднайте
    let sorted = word.toLowerCase().split('').sort().join(''); // (*)
    map.set(sorted, word);
  }

  return Array.from(map.values());
}

let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];

alert( aclean(arr) );

Сортування літер здійснюється ланцюжком викликів одним рядком (*).

Для зручності давайте розіб’ємо на декілька рядків:

let sorted = word // PAN
  .toLowerCase() // pan
  .split('') // ['p','a','n']
  .sort() // ['a','n','p']
  .join(''); // anp

Два різних слова 'PAN' і 'nap' приймають ту ж саму форму після сортування букв – 'anp'.

Наступна лінія поміщає слово в об’єкт Map:

map.set(sorted, word);

Якщо ми коли-небудь ще зустрінемо слово в тій же відсортованої формі, тоді це слово перезапише значення з тим же ключем в об’єкті. Таким чином, декільком словами у нас буде завжди відповідати одна відсортована форма.

Врешті-решт Array.from(map.values()) приймає значення об’єкта-ітератора ‘Map’ (в цьому випадку нам не потрібні ключі) і повертає їх у вигляді масиву.

Тут ми також можемо використовувати звичайний об’єкт замість Map, тому що ключі – це рядки.

Ось один з варіантів рішень задачі:

function aclean(arr) {
  let obj = {};

  for (let i = 0; i < arr.length; i++) {
    let sorted = arr[i].toLowerCase().split("").sort().join("");
    obj[sorted] = arr[i];
  }

  return Object.values(obj);
}

let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];

alert( aclean(arr) );

Відкрити рішення із тестами в пісочниці.

важливість: 5

Ми хотіли б отримати масив ключів map.keys() в змінну і далі працювати з ними, наприклад, застосувати метод .push.

Але так не спрацює:

let map = new Map();

map.set("name", "John");

let keys = map.keys();

// Помилка: keys.push -- це не функція
keys.push("more");

Чому? Що потрібно виправити в коді, щоб keys.push працював?

Ми отримали помилку тому, що map.keys() повертає об’єкт-ітератор, а не масив.

Ми можемо конвертувати його використовуючи Array.from:

let map = new Map();

map.set("name", "John");

let keys = Array.from(map.keys());

keys.push("more");

alert(keys); // name, more
Навчальна карта