Як створити двонаправлену карту в JavaScript

Двонаправлена ​​карта — це модель з інформатики, де пари ключів і значень мають однозначний зв’язок 1-1 між ключами та значеннями. Це дозволяє нам не тільки запитувати за ключем і отримувати значення, але також робити запит за значенням і отримувати ключ. Давайте подивимося, як реалізувати двонаправлену карту в JavaScript, і зробимо її безпечною для друку в TypeScript

Інформатика та математика позаду

Давайте візьмемо базове визначення двонаправленої карти:

В інформатиці двонаправлена ​​карта — це асоціативна структура даних, у якій пари ключів і значень утворюють взаємну відповідність. Таким чином, бінарне відношення є функціональним у кожному напрямку: кожне значення також може бути зіставлено з унікальним ключем.

Авторство: двонаправлена ​​карта

Двонаправлена ​​карта з інформатики походить від математичної функції, яка називається бієкція. Відношення між компонентами пари з кожним із її компонентів у різних наборах є біективною функцією, яка також називається оборотною функцією, яка є функцією, яка працює в обох напрямках, поєднуючи рівно один елемент з одного набору з точно одним елементом інший набір:

Авторство: бієкція

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

f (1) = D
f (C) = 3

Інша річ, яка випливає з біективної функції, полягає в тому, що множини матимуть однакову довжину, інакше бієкція буде невдалою.

Ініціалізуйте двонаправлену карту

Ми змоделюємо це за допомогою класу JavaScript, який буде ініціалізовано об’єктом пар ключ-значення:

const bimap = new BidirectionalMap({
  a: 'A',
  b: 'B',
  c: 'C',
})

Внутрішньо ми створимо два списки. Один список зберігатиме список пар того, що ми будемо називати прямою картою, де ключ відповідає значенню та буде копією об’єкта, який ми використовували для ініціалізації двонаправленої карти. Другий список буде тим, що ми назвемо зворотною картою, і зберігатиме версію об’єкта, який використовується для ініціалізації двонаправленої карти, де пари ключ-значення були перевернуті, а «значення» тепер відображається на «ключ»:

Зауважте, що через природу об’єкта, який ініціалізує двонаправлену карту, ви не можете використовувати число для ключа, але ви все одно можете використовувати його як значення, і пізніше ви зможете запитувати за ним:

const bimap = new BidirectionalMap({
  a: 42,
  b: 'B',
  c: 'C',
})

Більш надійну, хоча й складнішу версію можна було б написати за допомогою типу даних Map JavaScript і дозволити ключі, які є числами, функціями або навіть NaN.

Отримати елемент із двонаправленої карти

До цього моменту у нас є структура даних, яка містить два об’єкти, один з яких є дзеркалом іншого з точки зору ключів – значень. Тепер нам потрібен метод, щоб отримати з цього щось. Давайте реалізуємо get()функцію:

  get( key) {
      return this.fwdMap[key] || this.revMap[key]
  }

Це дуже просто: якщо він існує в прямій карті, ми повертаємо його, інакше ми повертаємо його з зворотної карти. Якщо такого немає, undefinedбуде повернено.

Тепер ми можемо отримати такі елементи, як:

console.log( bimap.get('a')) console.log( bimap.get('A')) 

Додайте елемент до двонаправленої карти

Наша карта наразі не має способу додати більше елементів, тому давайте додамо функцію для додавання нових елементів на карту:

  add( pair) {
    this.fwdMap[pair[0]] = pair[1]
    this.revMap[pair[1]] = pair[0]
  }

Це отримає масив з двох елементів, які ми пізніше введемо як кортеж за допомогою TypeScript, і призначимо їх як ключові значення в обох напрямках відповідним об’єктам.

І тепер ми можемо додати пару та запитати цю нову пару

bimap.add(['d', 'D'])
console.log( bimap.get('D')) 

Безпечна двонаправлена ​​карта в TypeScript

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

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