javascript - 如何以对数时间检查具有相等值的对象是否在容器中

Question

我想以对数时间查看具有相等值的对象是否在容器中。

我想拥有以下功能:

const a = [];

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};
const b = {name: 'name1', directive: 'directive1'};

a.push(el1);
a.push(el2);
a.push(el3);


if(a.some(el => (el.name === b.name && el.directive === b.directive ))) {
  console.log("YES!");
} else {
  console.log("NO!");
}

这给了我想要的结果。然而，这是 O(N) 时间。

const s = new Set();

const el1 = {name: 'name1', directive: 'directive1'};
const el2 = {name: 'name2', directive: 'directive2'};
const el3 = {name: 'name3', directive: 'directive3'};
const b = {name: 'name1', directive: 'directive1'};

s.add(el1);
s.add(el2);
s.add(el3);

if(s.has(b)) {
  console.log("YES!");
} else {
  console.log("NO!");
}

这是O(logN)，但结果不是我想要的。

那么我可以使用哪种 Javascript 数据结构来在上面的代码中打印 YES 并且复杂度为 O(logN)？ (我不想自己实现一个数据结构)

Answer 1

您可以使用按名称键控的 Map，其中对应的值是一组指令:

const elements = [
    {name: 'name1', directive: 'directive1'},
    {name: 'name2', directive: 'directive2'},
    {name: 'name3', directive: 'directive3'}
];

const map = new Map(elements.map(({name}) => [name, new Set]));
elements.forEach(({name, directive}) => map.get(name).add(directive));

const b = {name: 'name1', directive: 'directive1'};

if (map.has(b.name) && map.get(b.name).has(b.directive)) {
    console.log("YES!");
} else {
    console.log("NO!");
}