The data structure that you are looking for is a bidirectional map. Description from Wikipedia:
In computer science, a bidirectional map, or hash bag, 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: value can also act as a key to key. A pair (a, b) thus provides a unique coupling between a and b so that b can be found when a is used as a key and a can be found when b is used as a key.
Mathematically, a bidirectional map between keys and values is equivalent to a pair of functions:
- A function
f from keys to values (i.e. a -> b).
- A function
g from values to keys (i.e. b -> a).
In addition, there are two constraints imposed on bidirectional maps:
- Given any key
x the constraint g (f x) = x must be satisfied.
- Given any value
y the constraint f (g y) = y must be satisfied.
Therefore, Bimap(a, b) = (a -> b, b -> a).
Alternatively, a bidirectional map can be represented as a pair of maps or associative arrays:
Since Map(a, b) = a -> b, therefore Bimap(a, b) = (Map(a, b), Map(b, a)).
Internally, an associative array could be represented as either a pair of lists (i.e. ([a], [b])) or a list of pairs (i.e. [(a, b)]) or hash tables or any other suitable data structure.
Let's implement a bidirectional map data structure using hash tables internally for efficiency:
function Bimap(keys, vals) {
var length = Math.min(keys.length, vals.length);
var valMap = this.lookupVal = Object.create(null);
var keyMap = this.lookupKey = Object.create(null);
for (var i = 0; i < length; i++) {
var key = keys[i];
var val = vals[i];
valMap[key] = val;
keyMap[val] = key;
}
}
You can use it as follows:
var bimap = new Bimap(["Earl", "John", "Shelia", "Lenny"], [85, 92, 87, 99]);
bimap.lookupVal["Lenny"]; // 99
bimap.lookupKey[99]; // "Lenny"
You can also add new key value pairs to the bidirectional map as follows:
Bimap.prototype.insert = function (keys, vals) {
var length = Math.min(keys.length, vals.length);
var valMap = this.lookupVal;
var keyMap = this.lookupKey;
for (var i = 0; i < length; i++) {
var key = keys[i];
var val = vals[i];
valMap[key] = val;
keyMap[val] = key;
}
};
You would use it as follows:
bimap.insert(["Jane"], [96]);
bimap.lookupVal["Jane"]; // 96
bimap.lookupKey[96]; // "Jane"
You can summarize bidirectional maps (such as finding min/max values, etc.) using reduce:
Bimap.prototype.reduceVals = function (inductive, basis) {
var valMap = this.lookupVal, undefined;
return basis === undefined ?
Object.keys(valMap).reduce(callback) :
Object.keys(valMap).reduce(callback, basis);
function callback(proof, key) {
return inductive(proof, valMap[key]);
}
};
For example:
bimap.lookupKey[bimap.reduceVals(Math.min)]; // "Earl"
bimap.lookupKey[bimap.reduceVals(Math.max)]; // "Lenny"
Finally, most JavaScript engines now natively support the Map data structure. Hence, you can implement Bimap in terms of that instead.