Как создать двунаправленную карту в JavaScript

Двунаправленная карта — это модель из информатики, в которой пары ключ-значение имеют биективное отношение 1-1 между ключами и значениями. Это позволяет нам не только запрашивать по ключу и получать значение, но и запрашивать по значению и получать ключ. Давайте посмотрим, как реализовать двунаправленную карту в JavaScript, а позже сделаем ее безопасной для типов в TypeScript.

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

Давайте возьмем базовое определение двунаправленной карты:

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

Кредит: двунаправленная карта

Двунаправленная карта из информатики берет свое начало в математической функции, называемой биекцией. Отношение между компонентами пары с каждым из ее компонентов в разных множествах является биективной функцией, также называемой обратимой функцией, которая представляет собой функцию, которая работает в обоих направлениях, связывая ровно один элемент из одного набора ровно с одним элементом множества. другой набор:

1 кредит

Имея это в виду, мы можем знать, что биективная функция для наборов выше даст что-то вроде:

е (1) = D
е (С) = 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 и добавить концепции типизации, такие как универсальный объект при инициализации карты и кортеж при добавлении нового элемента.

Эта типизация теперь делает нашу карту совершенно безопасной и гарантирует, что в этом случае мы всегда будем использовать строки как для ключей, так и для значений.