Към съдържанието
wannacode

Map и Set

Проблем

Кой е този потребител?

Потребителите на сайта са в масив. При всяко влизане търсиш имейла по потребителското име:

function findEmail(users, username) {
  for (const u of users) {
    if (u.username === username) {
      return u.email;
    }
  }
  return null;
}

С три потребителя това е мигновено. С 2 000 000 всяко влизане сравнява до 2 000 000 имена, а влизанията са хиляди в минута. Телефонен указател не се чете от първата страница. Отиваш направо на буквата.

Идеята

Речник: ключ → стойност

Искаш да питаш „кой е имейлът на georgiev?“ и да получиш отговор веднага. Колекцията за това се казва речник (map). Тя пази двойки: ключ и стойност. В JavaScript речникът е Map:

const emails = new Map();
emails.set("ivanov", "ivanov@example.com");
emails.set("mpetrova", "mpetrova@example.com");
emails.set("georgiev", "georgiev@example.com");


console.log(emails.get("georgiev"));
console.log(emails.get("nobody"));
console.log(`Потребители: ${emails.size}`);
Изход
georgiev@example.com
undefined
Потребители: 3
  • new Map() е празен речник. set(ключ, стойност) слага двойка, а get(ключ) връща стойността.
  • Ключ, който го няма, дава undefined.
  • size е броят двойки. Пише се без скоби: това е свойство, не метод.

В JavaScript и обикновеният обект {} прилича на речник: stock[ключ] = стойност. Много код го ползва така, но има капани:

const stock = {};
stock[1] = "лаптоп";
stock["1"] = "мишка";
console.log(stock);
console.log("toString" in stock);


const map = new Map();
map.set(1, "лаптоп");
map.set("1", "мишка");
console.log(map);
console.log(map.has("toString"));
Изход
{ '1': 'мишка' }
true
Map(2) { 1 => 'лаптоп', '1' => 'мишка' }
false
  • Ключовете на обект винаги стават текст: 1 и "1" са един ключ и „мишка“ замени „лаптоп“.
  • В обекта има и ключове, които не си слагал: toString идва от общия прототип на всички обекти.
  • Map пази типа на ключа, а вътре има само това, което си сложил. За речник ползвай Map.

get не обхожда всички двойки, а намира мястото на ключа почти веднага, без значение колко са. Как го прави, е следващият урок.

Идеята

Складът: промени и проверки

Наличностите в склада: продукт → брой.

const stock = new Map();
stock.set("лаптоп", 4);
stock.set("мишка", 25);
stock.set("лаптоп", 3);


console.log(stock.get("лаптоп"));
console.log(stock.has("монитор"));
console.log(stock.get("монитор") ?? 0);
stock.delete("мишка");
console.log(stock.size);
Изход
3
false
0
1
  • Ключовете са уникални. Второто set("лаптоп", 3) не добавя нов ред, а заменя 4 с 3.
  • has пита дали ключът е вътре.
  • get(ключ) ?? 0 дава стойността или 0, ако ключа го няма. a ?? b е a, освен ако a е undefined или null: тогава е b. Това пази от undefined.
  • delete(ключ) маха двойката.
По-точно, за любопитните
  • Стойностите могат да се повтарят: лаптоп и мишка може да са по 3. Ключовете не могат.
  • Метод „има ли тази стойност“ Map няма. Трябва да обходиш values(), защото речникът е бърз само по ключ.

Пробвай

Колко са в менюто?

Какво ще отпечата програмата?

const menu = new Map();
menu.set("кафе", 2);
menu.set("чай", 2);
menu.set("кафе", 3);
console.log(menu.size, menu.get("кафе"));
Отговор

Идеята

Обхождане и редът

Цената на доставката по градове. for...of по Map дава двойки [ключ, стойност], а const [city, price] ги разделя на две имена:

const delivery = new Map();
delivery.set("София", 4.5);
delivery.set("Пловдив", 5.2);
delivery.set("Варна", 6.0);
delivery.set("Бургас", 6.0);
delivery.set("Русе", 5.8);


for (const [city, price] of delivery) {
  console.log(`${city}: ${price.toFixed(2)} €`);
}
Изход
София: 4.50 €
Пловдив: 5.20 €
Варна: 6.00 €
Бургас: 6.00 €
Русе: 5.80 €

Градовете излизат в реда, в който са добавени. Map пази реда на добавяне и това е обещано. toFixed(2) печата цената с два знака: иначе 6.0 излиза като 6.

Когато ти трябва азбучен ред, вземи ключовете в масив и го подреди. Map не се променя:

const delivery = new Map();
delivery.set("София", 4.5);
delivery.set("Пловдив", 5.2);
delivery.set("Варна", 6.0);
delivery.set("Бургас", 6.0);
delivery.set("Русе", 5.8);


for (const city of Array.from(delivery.keys()).sort()) {
  console.log(`${city}: ${delivery.get(city).toFixed(2)} €`);
}
Изход
Бургас: 6.00 €
Варна: 6.00 €
Пловдив: 5.20 €
Русе: 5.80 €
София: 4.50 €
По-точно, за любопитните
  • Ако ти трябват само ключовете, обхождай keys(). Ако ти трябват само стойностите, обхождай values():
console.log(Array.from(delivery.keys()).join(" "));


let sum = 0;
for (const price of delivery.values()) {
  sum += price;
}
console.log(`Средно: ${(sum / delivery.size).toFixed(2)} €`);
Изход
София Пловдив Варна Бургас Русе
Средно: 5.50 €
  • Array.from(...) прави масив от ключовете, за да има join и sort.
  • Обикновеният обект също пази реда на добавяне, но не винаги: ключове, които приличат на цели числа, излизат първи и подредени като числа.
const rooms = {};
rooms["Зала"] = "свободна";
rooms["12"] = "заета";
rooms["3"] = "свободна";
console.log(Object.keys(rooms));
Изход
[ '3', '12', 'Зала' ]

Идеята

Броене

Колко пъти е поръчан всеки продукт? Ключът е продуктът, стойността е броят. При всяка поръчка вземаш стария брой (или 0) и добавяш 1:

const orders = "кафе чай кафе вода кафе чай";
const counts = new Map();
for (const item of orders.split(" ")) {
  counts.set(item, (counts.get(item) ?? 0) + 1);
}
console.log(counts);
Изход
Map(3) { 'кафе' => 3, 'чай' => 2, 'вода' => 1 }

Това е най-честата употреба на речник: броене на думи, гласове, грешки по вид, продажби по град. Продуктите излизат в реда, в който са видени за първи път. Скобите около counts.get(item) ?? 0 са нужни: без тях + 1 се смята преди ?? и броят на вече видян продукт не расте.

const orders = "кафе чай кафе вода кафе чай";
const counts = new Map();
for (const item of orders.split(" ")) {
  counts.set(item, (counts.get(item) ?? 0) + 1);
}
console.log(counts);
Стъпка по стъпка, с думи
  1. 6 поръчки и празен Map.
  2. „кафе“ го няма: get дава undefined, ?? го прави 0, а set добавя ключа с 1.
  3. „чай“ го няма: get дава undefined, ?? го прави 0, а set добавя ключа с 1. Map пази реда на добавяне: новият ключ е последен.
  4. „кафе“ вече е вътре: get дава 1, а set заменя стойността с 2.
  5. „вода“ го няма: get дава undefined, ?? го прави 0, а set добавя ключа с 1. Map пази реда на добавяне: новият ключ е последен.
  6. „кафе“ вече е вътре: get дава 2, а set заменя стойността с 3.
  7. „чай“ вече е вътре: get дава 1, а set заменя стойността с 2.
  8. Всеки продукт е ключ веднъж, а стойността е колко пъти е поръчан.
По-точно, за любопитните
  • split(" ") от урока за текста разделя реда на думи.
  • Готов брояч в JavaScript няма. Записът с get, ?? 0 и set е обичайният начин.

Пробвай

Намери грешката

Програмата трябва да преброи поръчките. Не спира и не показва грешка, но вместо броеве печата това:
Изход
Map(2) { 'кафе' => NaN, 'чай' => NaN }

На кой ред е грешката?

Избери реда с грешката.

Идеята

Set: всяко по веднъж

Колко различни хора са влезли в сайта днес? Ако някой влезе пет пъти, трябва да се брои веднъж. Колекция, която пази всяка стойност само по веднъж, се казва множество (set):

const visits = ["ana@example.com", "boris@example.com", "ana@example.com", "vera@example.com", "boris@example.com"];
const visitors = new Set();
for (const email of visits) {
  visitors.add(email);
}
console.log(`Посещения: ${visits.length}`);
console.log(`Различни посетители: ${visitors.size}`);
console.log(visitors.has("vera@example.com"));
Изход
Посещения: 5
Различни посетители: 3
true
  • add на стойност, която вече е вътре, не прави нищо. И в двата случая връща самото множество, затова не казва дали е добавил:
const seen = new Set();
console.log(seen.add("F-101") === seen);
Изход
true
  • has е бърз като has на Map. size е броят стойности.
  • Индекси няма. Множеството отговаря само на въпроса „вътре ли е?“.
По-точно, за любопитните
  • Set пази реда на добавяне, както Map. Може да се направи и наведнъж от масив, а Array.from го връща в масив, например за sort():
const tags = new Set(["java", "sql", "git", "java"]);
console.log(tags);
console.log(Array.from(tags).sort());


const backend = new Set(["java", "sql", "docker"]);
console.log(tags.intersection(backend));
console.log(tags.union(backend));
Изход
Set(3) { 'java', 'sql', 'git' }
[ 'git', 'java', 'sql' ]
Set(2) { 'java', 'sql' }
Set(4) { 'java', 'sql', 'git', 'docker' }
  • intersection оставя само общите елементи на две множества, а union ги обединява. Ще ти трябват в упражнението. Те са нови: има ги от Node 22 и в браузърите от 2024 г.

Пробвай

Повторена фактура

Счетоводителката иска да види номерата на фактури, въведени два пъти. Кой метод пита дали номерът вече е в множеството?
const invoices = ["F-101", "F-102", "F-101", "F-103"];
const seen = new Set();
for (const number of invoices) {
  if (seen.(number)) {
    console.log(`Повторена фактура: ${number}`);
  }
  seen.add(number);
}

Упражнение

Речници в работа

Реши задачите в редактора си.

1. Таблица с потребители. Клас UserTable с методи add(username, email), get(username) и size(). Отвътре е Map. Добави ivanov, mpetrova и georgiev с имейли във вида ivanov@example.com и потърси mpetrova и nobody. В следващия урок ще направиш и своя хеш таблица, без Map.

Изход
mpetrova: mpetrova@example.com
nobody: няма такъв потребител
Потребители: 3

2. Честота на думите. Прочети ред текст, направи го с малки букви и преброй всяка дума. Отпечатай думите по азбучен ред.

Вход
Кафе с мляко и кафе без захар и кафе
Изход
без: 1
захар: 1
и: 2
кафе: 3
мляко: 1
с: 1

3. Документи по ключова дума. Клас DocumentIndex с методи addDocument(id, ...keywords) и search(keyword), който връща масив с номерата на документите с тази дума. Отвътре е Map от масиви: за всяка дума масив от документи. Добави документ 1 с „ООП“ и „Java“, документ 2 със „SQL“ и „бази данни“, документ 3 с „Java“ и „колекции“. Потърси „Java“, „SQL“ и „Python“ и отпечатай номерата в [], разделени със запетая.

Изход
Java: [1, 3]
SQL: [2]
Python: []

4. Мрежа от контакти. Клас Contact с име и имейл и клас ContactNetwork с методи addContact(name, email), addConnection(a, b) (връзката е в двете посоки), friendsOf(name), common(a, b) (общите познати) и emailOf(name). Пази контактите в Map име → Contact, а връзките в Map име → Set от имена. friendsOf и common връщат подреден масив. Свържи Иван с Мария и Иван с Петър.

Изход
Иван: [Мария, Петър]
Мария: [Иван]
Общи познати на Мария и Петър: [Иван]
Имейл на Петър: petar@example.com

Още задачи

  • Уникален идентификатор. Функция generateUserId(email) дава на всеки нов имейл номер U001, U002 и т.н., а за вече видян имейл връща същия номер. Големи и малки букви в имейла не се различават. Вариант с хеш функция има в следващия урок.
  • Каталог на книги. Ключът е ISBN, например 978-954-28-0001-2, а стойността е заглавието. Добави, потърси и отпечатай всички книги, подредени по ISBN.
  • Организатор на пътуване. За всяка дестинация пази масив от дейности: „Париж“ → „Айфеловата кула“, „Лувъра“. Отпечатай програмата в реда, в който са добавени дестинациите. Трябва ли нещо повече от обикновен Map?
  • Електронен речник. Дума → определение. Чети думи, докато не дойде „край“. За непозната дума отпечатай „Няма такава дума.“
  • Оценки по предмет. Чети редове „Математика 6“, „Физика 5“, „Математика 4“ и отпечатай средния успех по всеки предмет, подредени по име.

Тест

Провери се

1. Кога Map е по-добър избор от масив?
2. В Map menu вече има ключ "кафе" със стойност 2. Какво прави menu.set("кафе", 3)?
3. Какво връща get за ключ, който го няма?
4. Отпечатваш Map. В какъв ред излизат ключовете?
5. В обикновен обект stock пишеш stock[1] = "лаптоп" и после stock["1"] = "мишка". Колко ключа има stock?
6. Какво връща add на Set, ако стойността вече е вътре?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·