Jak stworzyć dwukierunkową mapę w JavaScript

Mapa dwukierunkowa to model z informatyki, w którym pary klucz-wartość mają relację bijective 1-1 między kluczami a wartościami. Pozwala nam to nie tylko na zapytanie według klucza i uzyskanie wartości, ale także na zapytanie według wartości i uzyskanie klucza. Zobaczmy, jak zaimplementować mapę dwukierunkową w JavaScript i zróbmy ją później bezpieczną w TypeScript

Informatyka i matematyka za

Chwyćmy podstawową definicję mapy dwukierunkowej:

W informatyce mapa dwukierunkowa to asocjacyjna struktura danych, w której pary klucz-wartość tworzą korespondencję jeden do jednego. Zatem relacja binarna działa w każdym kierunku: każda wartość może być również odwzorowana na unikalny klucz.

Źródło: Mapa dwukierunkowa

Dwukierunkowa mapa z informatyki ma swoje korzenie w funkcji matematycznej zwanej bijekcją. Relacja między składnikami pary z każdym z jej składników w różnych zestawach jest funkcją bijektywną, zwaną także funkcją odwracalną, która jest funkcją działającą w obie strony, parującą dokładnie jeden element z jednego zestawu z dokładnie jednym elementem drugi zestaw:

Źródło: Bijection

Mając to na uwadze, możemy wiedzieć, że funkcja bijektywna dla powyższych zbiorów wytworzy coś takiego:

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

Inną rzeczą, która wynika z funkcji bijektywnej, jest to, że zbiory będą miały dokładnie taką samą długość, w przeciwnym razie bijekcja się nie powiedzie.

Zainicjuj mapę dwukierunkową

Zamodelujemy to za pomocą klasy JavaScript, która zostanie zainicjowana obiektem par klucz-wartość:

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

Wewnętrznie utworzymy dwie listy. Jedna lista będzie przechowywać listę par tego, co nazwiemy mapą do przodu, gdzie klucz mapuje wartość i będzie kopią obiektu, którego użyliśmy do zainicjowania mapy dwukierunkowej. Druga lista będzie tym, co nazwiemy mapą odwrotną i będzie przechowywać wersję obiektu użytego do zainicjowania mapy dwukierunkowej, w której pary klucz-wartość zostały odwrócone, a „wartość" jest teraz mapowana na „klucz”:

Zwróć uwagę, że ze względu na naturę obiektu, który inicjuje mapę dwukierunkową, nie możesz użyć liczby jako klucza, ale nadal możesz użyć jej jako wartości, a później będziesz mógł wykonywać zapytania według niej:

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

Bardziej niezawodną, ​​choć również bardziej złożoną wersję można napisać z typem danych Map JavaScript i zezwalać na klucze, które są liczbami, funkcjami, a nawet NaN.

Pobierz element z mapy dwukierunkowej

Do tego momentu mamy strukturę danych, która obsługuje dwa obiekty, z których jeden jest odzwierciedleniem drugiego pod względem klucza – wartości. Potrzebujemy teraz metody, aby coś z tego wyciągnąć. Zaimplementujmy get()funkcję:

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

To bardzo proste: jeśli istnieje w mapie do przodu, zwracamy go, w przeciwnym razie zwracamy go z mapy odwróconej. Jeśli nie istnieje, undefinedzostanie zwrócony.

Możemy teraz uzyskać kilka elementów takich jak:

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

Dodaj element do mapy dwukierunkowej

Nasza mapa nie ma obecnie możliwości dodawania kolejnych elementów, więc dodajmy funkcję dodawania nowych elementów do mapy:

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

Spowoduje to otrzymanie tablicy dwóch elementów, które później wpiszemy jako krotkę za pomocą TypeScript i przypiszemy je jako klucz – wartości w obu kierunkach do odpowiednich obiektów.

A teraz możemy dodać parę i zapytać o tę nową parę

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

Bezpieczna dwukierunkowa mapa typu w TypeScript

Aby było lepiej i bezpieczniej pisać, możemy przepisać to w TypeScript i dodać koncepcje typowania, takie jak obiekt generyczny podczas inicjowania mapy i krotkę podczas dodawania nowego elementu.

To pisanie sprawia, że ​​nasza mapa jest teraz całkowicie bezpieczna i zapewnia, że ​​w tym przypadku zawsze będziemy używać ciągów zarówno dla kluczy, jak i wartości.