Question posted in 
In javascript a Map allows uniquely retrieving a "value" based on a single associated "key" – like so:
let m = new Map();
m.set('a', 'my value');
let v = m.get('a'); // v === 'my value'
How can we implement a data structure which uses multiple unordered keys to retrieve an associated value? In such a case the "key" value would always be an array. Let’s call this a "CompoundMap". Let’s allow a CompoundMap to be instantiated with a "width" value, giving a fixed-size for its compound keys. Like Map, the values used in CompoundMap keys should be able to be anything (e.g. String, Number, Object, Regex, ClientRequest… whatever) E.g.:
let cm = new CompoundMap({ width: 2 });
cm.set([ 'a', 1 ], 'my value');
let v1 = cm.get([ 'a', 1 ]); // v1 === 'my value'
let v2 = cm.get([ 1, 'a' ]); // v2 === 'my value'
let v3 = cm.get([ 'a', 2 ]); // v3 === undefined
let v4 = cm.get([ 'b', 1 ]); // v4 === undefined
let v5 = cm.get([ 2, 'a' ]); // v5 === undefined
let v6 = cm.get([ 1, 'b' ]); // v6 === undefined
One way I can think of is to use a nested trees of Maps:
class CompoundMap {
constructor({ width, entries }) {
if (!width && entries) width = entries[0]?.[0]?.length;
if (!width) throw Error('Must provide "width"');
Object.assign(this, { width, tree: new Map() });
for (let [ cmpKey, val ] of entries ?? []) this.set(cmpKey, val);
}
* treeSearch(tree, cmpKey) {
if (cmpKey.length === 0) throw Error('Compound key should have at least one item');
// A `cmpKey` with length 1 is our "base case"; return the "tree" we reached, and the final key
if (cmpKey.length === 1) return yield { tree, finalKey: cmpKey[0] };
for (let [ n, key ] of cmpKey.entries()) {
let subtree = tree.get(key);
// If no `subtree`, `key` doesn't apply at this current depth
if (!subtree) continue;
// We found a `subtree` - we still need to process the remaining key, which is `cmpKey` with `key` removed
let cmpKeyMinusKey = (() => {
let copy = [ ...cmpKey ];
copy.splice(n, 1); // `n` is the index of `key` in `copy`
return copy;
})();
// Now recursively search for the rest of the key! Note `yield*` helps us implement backtracking - a
// search down some specific chain of subtrees may not succeed, but the overall search could still
// succeed when another chain of subtrees is able to fully consume the `cmpKey`
// (This is also why the runtime for this approach will be horrible...)
yield* this.treeSearch(subtree, cmpKeyMinusKey);
}
}
set(cmpKey, val) {
if (cmpKey.length !== this.width) throw Error(`Compound key must have exactly ${this.width} item(s)`);
let preexisting = this.treeSearch(this.tree, cmpKey).next().value;
if (preexisting) {
// Overwrite existing item
// `this.treeSearch` yields `{ tree, finalKey }`, so overwriting is very simple
let { tree, finalKey } = preexisting;
tree.set(finalKey, val);
} else {
// Write new item
let tree = this.tree;
for (let k of cmpKey.slice(0, -1)) {
if (!tree.has(k)) tree.set(k, new Map());
tree = tree.get(k);
}
tree.set(cmpKey.at(-1), val);
}
return this;
}
get(cmpKey) {
if (cmpKey.length !== this.width) throw Error(`Compound key must have exactly ${this.width} item(s)`);
let preexisting = this.treeSearch(this.tree, cmpKey).next().value;
if (!preexisting) return undefined;
let { tree, finalKey } = preexisting;
return tree.get(finalKey);
}
}
let obj1 = { desc: 'obj' };
let obj2 = { desc: 'obj' };
let tests = [
{
entries: [
{ cmpKey: [ 'a', 1 ], val: 'my value' },
],
lookups: [
{ cmpKey: [ 'a', 1 ], expected: 'my value' },
{ cmpKey: [ 1, 'a' ], expected: 'my value' },
{ cmpKey: [ 'a', 2 ], expected: undefined },
{ cmpKey: [ 'b', 1 ], expected: undefined },
{ cmpKey: [ 2, 'a' ], expected: undefined },
{ cmpKey: [ 1, 'b' ], expected: undefined }
]
},
{
entries: [
{ cmpKey: [ 'a', 'b', 'c' ], val: obj1 },
{ cmpKey: [ 'c', 'd', 'e' ], val: obj2 }
],
lookups: [
{ cmpKey: [ 'a', 'd', 'e' ], expected: undefined },
{ cmpKey: [ 'c', 'b', 'a' ], expected: obj1 },
{ cmpKey: [ 'd', 'e', 'c' ], expected: obj2 }
]
}
];
for (let { entries, lookups } of tests) {
let cm = new CompoundMap({ entries: entries.map(({ cmpKey, val }) => [ cmpKey, val ]) });
for (let { cmpKey, expected } of lookups) {
let received = cm.get(cmpKey);
if (received !== expected) {
console.log(`Test Failed! Expected [ ${cmpKey.join(', ')} ] -> ${JSON.stringify(expected)} ... BUT GOT ${JSON.stringify(received)}`);
} else {
console.log(`Test Passed! [ ${cmpKey.join(', ')} ] -> ${JSON.stringify(expected)}`);
}
}
}If you follow the above logic, however, you will see that the runtime is horrible – I think it’s at least exponential (O(2^n)). Can a CompoundMap be implemented more efficiently?
If we could somehow map arbitrary values to BigInts, through a function like getUniqueIntFor, we could map compound keys to single unique Strings:
let compoundKey = [ 1, 2, 'j', /my regex/u, { arr: [] }, new HttpServer() ];
let uniqueString = compoundKey
.map(anyValue => getUniqueIntFor(anyValue).toString(36))
.sort()
.join('.');
Given this ability, it’s arbitrary to implement CompoundMap. But how to implement getUniqueIntFor?
Is this idea worthwhile?
Otherwise, how can I implement CompoundMap more efficiently?
2
Answers
I implemented this and pushed it to github and npm - I decided to reference-count the
WeakMapentries; this allows entries to be removed earlier, when the user hasdeleted keys, but not yet dropped all references to the items in those keys.You can easily sort the keys (the sorting could be optimized of course), that makes working with the tree very simple.