在 JavaScript 地图中查找其他地图中不存在的所有项目的最便宜方法是什么？

Question

我在 javascript 中经常使用地图。我需要计算效率最高的方法来查找地图 a 中不存在于地图 b 中的所有项目。例如，

const a = new Map();
a.set('item1', 'item1value');
a.set('item2', 'item2value');


const b = new Map();
b.set('item1', 'item1value');

我要编写的函数的结果将是另一个 Map，其中包含一个键条目：item2，值：item2value.

我很清楚使用数组和对象执行此操作的大量问题/答案/方法，但是我还没有看到对映射的这样的解释。我需要绝对最有效的方法来做到这一点，因为我需要快速调用此函数多达数千次。转换为数组并返回 Map 是最好的方法吗？是否有任何可能有用的地图技巧？

Answer 1

您可以迭代第一个地图并检查第二个地图。

const
    a = new Map([['item1', 'item1'], ['item2', 'item2']]),
    b = new Map([['item1', 'item1']]),
    difference = (a, b) => {
        const d = new Map;

        a.forEach((v, k) => {
            if (!b.has(k) || b.get(k) !== v) d.set(v, k);
        });
        return d;
    }

console.log([...difference(a, b)])

Answer 2

不，不要将地图转换为数组并返回。计算数组之间的差异很慢，在地图中你有 O(1) 查找。如果在 b 中找不到等效条目，只需循环遍历 a 的条目并将它们放入结果中。这将具有最佳时间复杂度 O(n)（其中 n 是地图的大小 a）。

const result = new Map();
for (const [k, v] of a) {
    if (v === undefined && !b.has(k) || b.get(k) !== v) {
        result.set(k, v);
    }
}

如果您知道您的地图不包含 undefined 值，则可以完全省略 v === undefined && !b.has(k) || 并可能获得一些加速。另外，请注意，如果您的地图可以包含 NaN 值，则您需要使用 Object.is 而不是 ===。

如果你想把它写成一个单一的花式表达式，考虑一个生成器：

const result = new Map(function*() {
    for (const e of a) {
        const [k, v] = e;
        if (v === undefined && !b.has(k) || b.get(k) !== v) {
            yield e;
        }
    }
}());

Answer 3

也许这样通过维护 a;

var a = new Map(),
    b = new Map(),
    c;

a.set('item1', 'item1value');
a.set('item2', 'item2value');
b.set('item1', 'item1value');

c = new Map(a);
b.forEach((_,k) => c.delete(k));

console.log(c); // try in dev tools to see result

在 JavaScript 地图中查找其他地图中不存在的所有项目的最便宜方法是什么？

What's the cheapest method to find all items in a JavaScript map not present in another map?

javascript

performance

set

set-difference

ecmascript-6