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

Как работят Map и Set

Проблем

Мястото е продадено два пъти

Касата на театъра пази продадените места в речник: място → име на зрителя. Мястото е клас с ред и номер:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }
}
const bookings = new Map();
bookings.set(new Seat(5, 12), "Мария");


console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Иван");
console.log(bookings.size);
Изход
undefined
1
2

Мария е купила място 5/12, но get със същото място връща undefined. А Иван купува същото място и речникът вече има два ключа 5/12. Защо?

Идеята

Хеш: число от ключа

Map не сравнява ключа с всички останали. Той смята от ключа едно цяло число и по него разбира къде да търси. Това число се казва хеш (hash code). JavaScript не го показва: смята го двигателят и няма функция, която да го върне. За да видиш как работи, ето една хеш функция за текст. Формулата е същата като в Java:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}


console.log(hashOf("Мария"));
console.log(hashOf("Мария"));
console.log(hashOf("Мариа"));
console.log(hashOf("мария"));
Изход
1004560195
1004560195
1004560164
1034112867
  • Един и същ текст дава едно и също число, всеки път.
  • Малка промяна дава друго число: „Мария“, „Мариа“ и „мария“ са три различни хеша.
  • Хешът се смята бързо, без значение колко ключа има в речника.
  • charCodeAt(i) е кодът на символа. | 0 държи резултата цяло число от 32 бита, както int в Java. Ако стане твърде голямо, то се превърта и може да стане отрицателно.

Map ползва своя хеш функция, не тази. Но идеята е същата.

Методът, който прави числото, се казва хеш функция.

По-точно, за любопитните
  • Формулата е s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], като s[i] е кодът на всеки символ. Цикълът я смята, като на всяка стъпка умножава по 31 и добавя следващия код.
  • Криптографските хеш функции като SHA-256 са друго нещо. Те дават дълъг резултат и е практически невъзможно да намериш два текста с един и същ хеш. Затова с тях се проверява дали файл не е подменен и се пазят пароли. hashOf() е за бързо търсене и не дава такава защита.

Виж го

Кофите

Отвътре Map е масив от кофи (buckets). Номерът на кофата за ключа е остатъкът от хеша при деление на броя на кофите. Хешът тук е от hashOf, защото този на Map не се вижда:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}


const keys = ["Иван", "Мария", "Петър", "Ана"];
const buckets = 8;
for (const key of keys) {
  const hash = hashOf(key);
  const index = ((hash % buckets) + buckets) % buckets;
  console.log(`${key} -> ${hash} -> кофа ${index}`);
}
Стъпка по стъпка, с думи
  1. Четири ключа и осем празни кофи с номера от 0 до 7.
  2. hashOf("Иван") е 32287399. Остатъкът при деление на 8 е 7: това е кофата.
  3. „Мария“ дава 1004560195, кофа 3.
  4. „Петър“ дава 1007482178, кофа 2.
  5. „Ана“ също е в кофа 3: колизия. Двата ключа са в една кофа: „Ана“ се закача след „Мария“ като верига.
  6. Търсене на „Ана“: същото число, същата кофа 3. === с „Мария“: не. С „Ана“: да.
  • set смята кофата и слага двойката там. get смята същата кофа и гледа само в нея. Затова е бърз и при милион ключа.
  • % в JavaScript, както в Java, може да даде отрицателно число: -7 % 8 е -7. Затова ((hash % buckets) + buckets) % buckets: така остатъкът никога не е отрицателен. Номер на кофа не може да е отрицателен.
  • „Мария“ и „Ана“ попаднаха в кофа 3. Това се казва колизия. За нея е следващата карта.
По-точно, за любопитните
  • Как точно Map смята кофата, зависи от двигателя (V8 в Chrome и Node, друг във Firefox). Стандартът на езика казва само, че търсенето трябва да е средно по-бързо от обхождане на всичко.
console.log(-7 % 8, ((-7 % 8) + 8) % 8);
Изход
-7 1

Пробвай

В коя кофа?

В своя хеш таблица хешът на цяло число обикновено е самото число. Номерата на поръчките отиват в речник с 4 кофи.

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

const orderIds = [6, 10, 13, 21];
for (const id of orderIds) {
  console.log(`${id} -> кофа ${id % 4}`);
}
Отговор

Идеята

Колизия: хешът намира кофата, сравнението намира ключа

Различните ключове може да имат един и същ хеш. При hashOf, както при hashCode в Java, най-известният пример е:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}


console.log(hashOf("Aa"), hashOf("BB"));


const codes = new Map();
codes.set("Aa", 1);
codes.set("BB", 2);
console.log(codes.get("Aa"), codes.get("BB"));
Изход
2112 2112
1 2

Map пази и двата ключа и не ги бърка. Той има своя хеш функция и при нея колизиите са с други ключове, но е готов за тях. Кофата пази няколко двойки и get сравнява ключа с всяка от тях, докато не намери търсения.

Така работят и двете стъпки:

  1. Хешът казва в коя кофа да търси.
  2. Сравнението казва кой от ключовете в кофата е търсеният.

Сега е ясно какво стана с мястото в театъра. Map сравнява ключовете почти като ===: текстът и числата по стойност, а обектите по референция. Двата new Seat(5, 12) са два различни обекта, затова са и два различни ключа. Ключ, който е същият обект, се намира:

const seat = new Seat(5, 12);
const bookings = new Map();
bookings.set(seat, "Мария");
console.log(bookings.get(seat));
Изход
Мария

Идеята

Без equals и hashCode: ключ от текст

В Java и Python класът казва кога два обекта са равни (equals, __eq__) и какъв е хешът им (hashCode, __hash__). В JavaScript това няма как да стане. Map и Set сравняват обектите по референция и не викат твои методи. Дори да напишеш equals, Map не го поглежда:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }


  equals(other) {
    return other instanceof Seat && this.row === other.row && this.number === other.number;
  }
}
const bookings = new Map();
bookings.set(new Seat(5, 12), "Мария");


console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Иван");
console.log(bookings.size);
Изход
undefined
1
2

Обичайното решение е ключът да е текст, направен от полетата, които казват кое е мястото. Текстът се сравнява по стойност:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }


  key() {
    return `${this.row}/${this.number}`;
  }
}
const bookings = new Map();
bookings.set(new Seat(5, 12).key(), "Мария");


console.log(bookings.get(new Seat(5, 12).key()));
console.log(bookings.size);
bookings.set(new Seat(5, 12).key(), "Иван");
console.log(bookings.size);
Изход
Мария
1
1

Правилата за ключа от текст са същите като договора в Java:

  • Два обекта, които са едно и също място, дават един и същ ключ. Винаги.
  • Два различни обекта дават различни ключове. Затова е наклонената черта между полетата.
  • В ключа влизат само полетата, по които два обекта са един и същ.
По-точно, за любопитните
  • Без разделител ключовете се бъркат: мястото 51/2 и мястото 5/12 и двете дават „512“.
console.log(`${51}${2}`, `${5}${12}`, `${51}/${2}` === `${5}/${12}`);
Изход
512 512 false
  • Ако ти трябва и самият обект, сложи го като стойност: bookings.set(seat.key(), { seat, name: "Мария" }).

Пробвай

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

Каталогът пази продуктите в Map с ключ от текст. Два продукта с един и същ код са един и същ продукт, дори цената да се е сменила. Но has с новата цена връща false:
const catalog = new Map();
const old = new Product("A-100", 25.0);
catalog.set(old.key(), old);
// Цената е намалена, но продуктът е същият.
console.log(catalog.has(new Product("A-100", 19.9).key()));
Изход
false

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

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

Идеята

Кофите се пълнят

Когато двойките станат много, кофите стават дълги и търсенето се забавя. Затова Map расте:

  • Отвътре и Map трябва да прави повече кофи, когато се напълни, и да преразпределя ключовете, за да остане бърз.
  • Кога точно и колко, зависи от двигателя и програмата не може да го види.
  • Затова средно set и get са бързи, а понякога един set отнема повече време.

Има и капан. Ключът не бива да се променя, докато е в речника или в множеството:

const seat = new Seat(5, 12);
const sold = new Set();
sold.add(seat.key());


seat.number = 13;
console.log(sold.has(seat.key()));
console.log(sold.has(new Seat(5, 12).key()));
console.log(sold.size);
Изход
false
true
1
Тук капанът е друг. В множеството е текстът „5/12“, а той не се променя заедно с обекта. След seat.number = 13 ключът на seat е „5/13“ и не се намира, а „5/12“ още е вътре, за място, което вече не е продадено на никого. Ключът от текст е снимка на обекта в момента на add. Затова полетата, от които е ключът, е добре да не се променят.
По-точно, за любопитните
  • Ключ, който е самият обект, не губи обекта при промяна: Map го намира по референция. Но тогава new Seat(5, 12) е друг ключ. Изборът е между „същият обект“ и „същите стойности“.

Упражнение

Свои ключове

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

1. Ключ на човек. Клас Person с име, фамилия и възраст и метод key(), който прави ключ от текст по трите полета. Създай Иван Петров на 30 два пъти и веднъж на 31. Отпечатай ключовете и колко различни хора остават в Map с ключ key().

Изход
Иван/Петров/30
Иван/Петров/30
Иван/Петров/31
Различни хора: 2

2. Роботът в склада. Роботът тръгва от клетка (0, 0) и изпълнява ходове NNEESWWN: N е нагоре (y + 1), S надолу, E надясно (x + 1), W наляво. Колко различни клетки е посетил, заедно с началната? Ако в Set слагаш обекти от този клас, програмата казва 9, а трябва да каже 7. Поправи го:

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}
Изход
Ходове: 8
Различни клетки: 7

3. Хеш на файл. Функция hashFileContent(filePath) чете файла и връща хеша на съдържанието му като шестнайсетичен текст. Ползвай SHA-256 от вградения модул node:crypto: createHash("sha256").update(content).digest("hex"). Запиши три отчета: a.txt и b.txt с „Отчет за октомври: 1250 €“, c.txt с „Отчет за октомври: 1260 €“. Сравни хешовете им. Различни хешове значат различни файлове, а еднакви SHA-256 на практика значат еднакви файлове.

Изход
a.txt: 690871a6fdd1b9ecdd0ee92ba8da848997bc137f5712cbe02c9c3bcbc1c63a11
b.txt: 690871a6fdd1b9ecdd0ee92ba8da848997bc137f5712cbe02c9c3bcbc1c63a11
c.txt: 1d9642f8c4031aa37d607ee81164a672c1b3a76b70212a6da967d54fa5339247
a и b: еднакви
a и c: различни

Още задачи

  • Своя хеш таблица. Продължение на таблицата с потребители от миналия урок, този път без Map. Направи масив от 8 кофи, всяка е масив от двойки потребител–имейл. Хеш функцията е сумата от кодовете на символите в името (charCodeAt). Напиши add, get и метод, който печата колко двойки има във всяка кофа.
  • Идентификатор от имейл. generateUserId(email) връща "U" и първите 8 знака от SHA-256 на имейла с малки букви. Еднакъв ли е идентификаторът за Ivan@Example.com и ivan@example.com? Може ли два различни имейла да получат един и същ идентификатор? Как ще го откриеш?
  • Броене на колизии. Сметни кофата на ключовете user1 … user1000 с hashOf от урока при 16, 64 и 1024 кофи и преброй колко ключа попадат в кофа, в която вече има ключ.
  • Кутията за обувки. Клас Box с ширина, височина и дълбочина. Две кутии са еднакви, ако размерите им са еднакви в същия ред. Напиши key() и провери кутиите 30×20×10 и 10×20×30 в Set.

Тест

Провери се

1. Защо get на Map е бърз и при милион ключа?
2. Два различни ключа имат един и същ хеш. Какво става?
3. Ключът е обект: bookings.set(new Seat(5, 12), "Мария"). Какво връща bookings.get(new Seat(5, 12))?
4. Даваш на Seat метод equals(other), който сравнява реда и номера. Ще го ползва ли Map?
5. Ключът на мястото е текстът `${row}/${number}`. Защо е нужна наклонената черта?
6. key() на продукт е `${code}/${price}`, а продуктът е същият при друга цена. Какво не е наред?

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