在 javascript 中，
Maplet m = new Map();
m.set('a', 'my value');
let v = m.get('a'); // v === 'my value'
我们如何实现一个使用多个无序键来检索关联值的数据结构？在这种情况下，“键”值将始终是一个数组。我们称其为“CompoundMap”。让我们允许使用“宽度”值实例化
CompoundMapMapCompoundMaplet 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
我能想到的一种方法是使用
Mapclass 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)}`);
}
}
}但是，如果您遵循上述逻辑，您会发现运行时间非常糟糕 - 我认为它至少是指数级的（
O(2^n)CompoundMap如果我们可以通过像
getUniqueIntForlet compoundKey = [ 1, 2, 'j', /my regex/u, { arr: [] }, new HttpServer() ];
let uniqueString = compoundKey
.map(anyValue => getUniqueIntFor(anyValue).toString(36))
.sort()
.join('.');
鉴于这种能力，实现它是任意的
CompoundMapgetUniqueIntFor这个想法值得吗？
不然如何更高效地实现
CompoundMap您可以将键保存为集合并将其用作值映射的键。还创建映射到创建的集合的每个键的映射，这样您可以轻松检查是否存在具有给定关键项的集合，然后您可以检查该集合是否包含所有关键项：
class CompoundMap{
#sets = new Map;
#map = new Map;
constructor(entries){
for(const entry of entries) this.set(...entry);
}
get(keys){
for(const key of keys){
const sets = this.#sets.get(key);
if(!sets) return;
for(const set of sets){
if(keys.length === set.size && keys.every(key => set.has(key))){
return this.#map.get(set);
}
}
}
}
set(keys,val){
const set = new Set(keys);
this.#map.set(set, val);
for(const key of keys){
let sets = this.#sets.get(key);
if(!sets) this.#sets.set(key, sets = []);
sets.push(set);
}
}
}
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.map(({ cmpKey, val }) => [ cmpKey, val ]) );
for (let { cmpKey, expected } of lookups) {
debugger;
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)}`);
}
}
}