DEV Community

Cover image for Data Structures: Bidirectional Map
Maksim
Maksim

Posted on • Updated on

Data Structures: 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. Also known as bijective map. Article on Wikipedia.

It is not widely used data structure in web development, but in some cases really quite useful, for instance in encryption.

Let's describe our goal. Implement data structure, where following operations are performed in constant time:

  • Get value by key
  • Get key by value
  • Remove record by key
  • Remove record by value
  • Check for the existence of key
  • Check for the existence of value
  • Get the size of the map

Implementation below:

class BidirectionalMap<Key, Value> {
  private readonly map: Map<Key, Value>;
  private readonly inverseMap: Map<Value, Key>;

  constructor() {
    this.map = new Map();
    this.inverseMap = new Map();
  }

  clear(): void {
    this.map.clear();
    this.inverseMap.clear();
  }

  deleteKey(key: Key): boolean {
    if (!this.hasKey(key)) {
      return false;
    }

    const value = this.getValue(key)!;
    this.inverseMap.delete(value);
    return this.map.delete(key);
  }

  deleteValue(value: Value): boolean {
    if (!this.hasValue(value)) {
      return false;
    }

    const key = this.getKey(value)!;
    this.map.delete(key); 
    return this.inverseMap.delete(value);
  }

  entries(): IterableIterator<[Key, Value]> {
    return this.map.entries();
  }

  getKey(value: Value): Key | undefined {
    return this.inverseMap.get(value);
  }

  getValue(key: Key): Value | undefined {
    return this.map.get(key);
  }

  hasKey(key: Key): boolean {
    return this.map.has(key);
  }

  hasValue(value: Value): boolean {
    return this.inverseMap.has(value);
  }

  get isEmpty(): boolean {
    return this.size === 0;
  }

  keys(): IterableIterator<Key> {
    return this.map.keys();
  }

  set(key: Key, value: Value): void {
    if (this.hasKey(key) || this.hasValue(value)) {
      throw new Error('Key or Value already exists');
    }

    this.map.set(key, value);
    this.inverseMap.set(value, key);
  }

  get size(): number {
    return this.map.size;
  }

  values(): IterableIterator<Value> {
    return this.inverseMap.keys();
  }
}
Enter fullscreen mode Exit fullscreen mode

Basically we can consider this data structure as extending of Map class. Current implementation could be improved by adding forEach method and iterable protocol, which will allow to define iteration behavior of Bidirectional Map. Let me know in comments if your interesting to know, how to do it exactly.

Discussion (11)

Collapse
eikooc profile image
Jamie Neubert Pedersen

Hi @pretaporter , thanks for the article. I want to discuss a part of the class if you are willing to. I believe in the set(k, v) that you should not look at the union in the if statement, but rather the intersection (&& vs. ||) as having either of them being defined without the other should rather be an error in the implementation. If that is true you should rather throw an error or something to show that the bi-directional map is malformed. Cheers.

Collapse
pretaporter profile image
Maksim Author

Sure, thanks for your point. Why do you think we should use intersection instead?
If we will use intersection, then will be possible situation like this:

xx.set('a', 'b');
xx.set('c', 'b');
xx.getKey('b'); // returns c
Enter fullscreen mode Exit fullscreen mode

It is not correct

Collapse
varunpappu profile image
Varun Subramanian

May I know how this is bi directional as you are using two maps with no link between each other. If a key is removed from one it should be removed from the inverse map as well if I am not wrong. Where would this be an ideal use case if I may know. Thanks for the write up

Collapse
pretaporter profile image
Maksim Author

What do you mean by no link between each other? If you will have a look to implementation of deleteKey or deleteValue methods you will see, that it removes rows from both maps. The same behaviour for adding rows. I suppose the best example is encryption, when you create dictionary during encoding and later use it for decoding.

Collapse
varunpappu profile image
Varun Subramanian

What I meant was, you have mentioned one-to-one mapping and I don't see any explicit mapping between both the maps. Its two separate maps and one has {key, value} and other uses inverse of {key, value} and if updation fails in one then the data between maps are not pure.

Also what happens when the value is of non primitive type, how will this hold
good?
Also on performance wise, in what way it will improve when searching with a value?

Just curious and trying to understand it better.

Thread Thread
pretaporter profile image
Maksim Author

If you go over implementation, you will see that it is not possible that updation of one map can fail.

Should not be any issue with using non primitive values.

Complexity of searching key or value will be constant O(1);

Thread Thread
dean profile image
Dean Bassett

I think the confusion comes from how errors occur - errors do not simply happen randomly, they happen for reasons. A map update should never result in an error occurring, maybe except some kind of fatal error like an out-of-memory error, in which case the program will not be able to work properly anyway.

Updating a map is (pretty much) as safe as creating an array - we don’t need, or want, to error check it.

Collapse
yoursunny profile image
Junxiao Shi

I usually use mnemonist package for all my BiMap needs:
yomguithereal.github.io/mnemonist/...

Collapse
pretaporter profile image
Maksim Author

Yeah, really good one

Collapse
jishen73 profile image
John Shen

Thanks for the writeup. This is intriguing as I've had moments where I would've liked to use something similar where I'd look up the key by giving a value. In this Bidirectional Map, are the keys and values required to be unique? If we have two keys with the same value, would this not cause a problem if we tried to look up the keys by the value?

Collapse
pretaporter profile image
Maksim Author • Edited

Yeah, indeed keys and values required to be unique.

if (this.hasKey(key) || this.hasValue(value)) {
  throw new Error('Key or Value already exists');
}
Enter fullscreen mode Exit fullscreen mode

As you can see in current implementation, set method will throw an error in case if map already consists key or value.