Hur man skapar en dubbelriktad karta i JavaScript

En dubbelriktad karta är en modell från datavetenskap där nyckel-värdepar har ett bijektivt 1-1-förhållande mellan nycklarna och värdena. Detta tillåter oss att inte bara fråga efter nyckel och få ett värde, utan också att fråga efter värdet och få nyckeln. Låt oss se hur man implementerar en dubbelriktad karta i JavaScript och låt oss göra den senare typsäker i TypeScript

Datavetenskapen och matematiken bakom

Låt oss ta en grundläggande definition av en dubbelriktad karta:

Inom datavetenskap är en dubbelriktad karta en associativ datastruktur där nyckel-värdeparen bildar en en-till-en-korrespondens. Således är den binära relationen funktionell i varje riktning: varje värde kan också mappas till en unik nyckel.

Kredit: Dubbelriktad karta

Den dubbelriktade kartan från datavetenskap har sina rötter i en matematisk funktion som kallas bijektion. Relationen mellan komponenterna i ett par med var och en av dess komponent i olika mängder är en bijektiv funktion, även kallad en inverterbar funktion, vilket är en funktion som fungerar på båda sätten, parar ihop exakt ett element från en mängd med exakt ett element av det andra setet:

Kredit: Bijection

Med detta i åtanke kan vi veta att en bijektiv funktion för uppsättningarna ovan kommer att producera något som:

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

En annan sak som uppstår från den bijektiva funktionen är att mängderna kommer att ha exakt samma längd, annars skulle bijektionen misslyckas.

Initiera den dubbelriktade kartan

Vi modellerar detta med en JavaScript -klass som kommer att initieras med ett objekt med nyckel-värdepar:

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

Internt skapar vi två listor. En lista kommer att lagra listan med par av vad vi kallar en framåtkarta, där nyckelkartor är värdefulla och kommer att vara en kopia av objektet vi använde för att initialisera den dubbelriktade kartan. Den andra listan kommer att vara vad vi kallar en omvänd karta, och kommer att lagra en version av objektet som används för att initiera den dubbelriktade kartan där nyckel-värdeparen har vänts och "värdet" nu mappas till "nyckeln":

Observera att på grund av arten av objektet som initierar den dubbelriktade kartan kan du inte använda ett nummer för nyckeln men du kan fortfarande använda det som ett värde och du kommer senare att kunna fråga efter det:

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

En mer robust men också mer komplex version skulle kunna skrivas med kartdatatypen JavaScript och tillåta nycklar som är siffror, funktioner eller till och med NaN.

Få ett element från en dubbelriktad karta

Fram till denna punkt har vi en datastruktur som är värd för två objekt, varav det ena är en spegel av det andra när det gäller nyckelvärden. Vi behöver nu en metod för att få ut något av det. Låt oss implementera en get()funktion:

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

Det är väldigt enkelt: om det finns i den framåtriktade kartan returnerar vi det, annars returnerar vi det från den omvända kartan. Om ingen finns, undefinedkommer den att returneras.

Vi kan nu få några element som:

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

Lägg till ett element till en dubbelriktad karta

Vår karta har för närvarande inte ett sätt att lägga till fler element så låt oss lägga till en funktion för att lägga till nya element på kartan:

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

Detta kommer att ta emot en uppsättning av två element, som vi senare kommer att skriva som en tuppel med TypeScript, och kommer att tilldela dem som nyckelvärden i båda riktningarna till motsvarande objekt.

Och nu kan vi lägga till ett par och fråga efter detta nya par

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

En typsäker dubbelriktad karta i TypeScript

För att göra saker bättre och skrivsäkra kan vi skriva om detta i TypeScript och lägga till skrivkoncept som ett generiskt objekt vid initialisering av kartan och en tupel när ett nytt element läggs till.

Denna skrivning gör nu vår karta helt säker och säkerställer att vi i det här fallet alltid kommer att använda strängar för både nycklar och värden.