How to create a Bidirectional Map in JavaScript

A bidirectional map is a model from computer science where key – value pairs have a bijective 1-1 relationship between the keys and the values. This allows us not only to query by key and get a value, but also to query by the value and get the key. Let’s see how to implement a bidirectional map in JavaScript and let’s make it later type safe in TypeScript

  1. The computer science and math behind
  2. Initialize the bidirectional map
  3. Get an element from the bidirectional map
  4. Add an element to the bidirectional map
  5. A type safe bidirectional map in TypeScript

The computer science and math behind

Let’s grab a basic definition of a bidirectional map:

In computer science, a bidirectional map is an associative data structure in which the key – value pairs form a one-to-one correspondence. Thus the binary relation is functional in each direction: each value can also be mapped to a unique key.

Bidirectional map definition as a mathematical bijection
Credit: Bidirectional Map

The bidirectional map from computer science has its roots in a mathematical function called a bijection. The relation between the components of a pair with each one of its component in different sets is a bijective function, also called an invertible function, which is a function that works in both ways, pairing exactly one element from one set with exactly one element of the other set:

bijective function mapping elements from one set to the other
Credit: Bijection

With this in mind we can know that a bijective function for the sets above will produce something like:

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

Another thing that arises from the bijective function is that the sets will have the exact same length, otherwise the bijection would fail.

Initialize the bidirectional map

We’ll model this with a JavaScript class that will be initialized with an object of key – value pairs:

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

Internally, we’ll create two lists. One list will store the list of pairs of what we’ll call a forward map, where key maps to value and will be a copy of the object we used to initialize the bidirectional map. The second list will be what we’ll call a reverse map, and will store a version of the object used to initialize the bidirectional map where the key – value pairs have been flipped and the “value” now maps to the “key”:

class BidirectionalMap {
  fwdMap = {}
  revMap = {}

  constructor(map) {
      this.fwdMap = { ...map }
      this.revMap = Object.keys(map).reduce(
          (acc, cur) => ({
              ...acc,
              [map[cur]]: cur,
          }),
          {}
      )
  }
}

Note that due to the nature of the object that initializes the bidirectional map you can’t use a number for the key but you can still use it as a value and you’ll be later able to query by it:

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

A more robust although also more complex version could be written with the Map data type of JavaScript and allow keys that are numbers, functions, or even NaN.

Get an element from a bidirectional map

Up to this point, we’ve a data structure that hosts two objects, one of them being a mirror of the other in terms of key – values. We now need a method to get something out of it. Let’s implement a get() function:

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

It’s very straightforward: if it exists in the forward map, we return it, otherwise we return it from the reversed map. If none exists, undefined will be returned.

We can now get some elements like:

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

Add an element to a bidirectional map

Our map doesn’t currently have a way to add more elements so let’s add a function to add new elements to the map:

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

This will receive an array of two elements, which we’ll later type as a tuple with TypeScript, and will assign them as key – values in both directions to the corresponding objects.

And now we can add a pair and query this new pair

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

A type safe bidirectional map in TypeScript

To make things better and type safe we can rewrite this in TypeScript and add typing concepts like a generic object when initializing the map and a tuple when adding a new element.

class BidirectionalMap {
  fwdMap = {}
  revMap = {}

  constructor(map: { [key: string]: string }) {
      this.fwdMap = { ...map }
      this.revMap = Object.keys(map).reduce(
          (acc, cur) => ({
              ...acc,
              [map[cur]]: cur,
          }),
          {}
      )
  }

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

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

This typing now makes our map perfectly safe and ensures, in this case, we’ll always use strings for both keys and values.

Leave a Reply