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

Question

I am working quite a bit with Maps in javascript. I need the most computationally efficient way to find all items that are in Map a that are not present in Map b. For example,

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


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

The result of the function I'm looking to write would be another Map, with a single entry of key: item2, value: item2value.

I am well aware of the multitude of questions / answers / methods to do this with arrays and objects, however I have not seen such an explanation for maps. I need the absolute most efficient way to do so, as I will need to be call this function up to thousands of times quickly. Is conversion to an array and back to a Map the best way? Are there any tricks with Maps that may help?

Answer 1

No, don't convert the maps to arrays and back. Computing the difference between arrays is slow, in a map you have O(1) lookup. Just loop through the entries of a and put them into the result if you don't find an equivalent entry in b. This will have the optimal time complexity O(n) (where n is the size of the map 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);
    }
}

If you know that your map doesn't contain undefined values, you can omit the v === undefined && !b.has(k) || entirely and might get some speedup. Also, notice that if your map can contain NaN values, you'll want to use Object.is instead of ===.

If you want to write it as a single fancy expression, consider a generator:

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 2

You could iterate the first map and check against the second.

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 3

Perhaps like this by maintaining 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