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();
}
}
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.
Top comments (11)
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 theifstatement, 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.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:
It is not correct
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
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.
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.
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);
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.
I usually use mnemonist package for all my BiMap needs:
yomguithereal.github.io/mnemonist/...
Yeah, really good one
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?
Yeah, indeed keys and values required to be unique.
As you can see in current implementation,
setmethod will throw an error in case if map already consists key or value.