Composite Map Keys in JavaScript with Bitsets

Sometimes you need to store and retrieve information related to groups of objects.

In JavaScript, Maps seem like they should be the right tool for this, but it's trickier to do than you might think. JavaScript has very minimal object and collection interfaces. Unlike some languages, like Java, there is no built-in concept of custom equality or hashcodes.

Maps and Sets in JavaScript work based on reference equality for objects. You can use an object as a key, but you can only set and get the data for an object if you use the exact same object instance - that is, if they are === to each other. Two different object instances, even with the same values for the same properties, are always different, unique map keys. If you set a value with an array key, like map.set([1, 2, 3], 'foo'), you can not then retrieve that value with map.get([1, 2, 3]).

The Records and Tuples language proposal is supposed to help with this problem by adding objects with value semantics to the language. Then map.set(#[1, 2, 3], 'foo') and map.get(#[1, 2, 3]) would work how we want. But that proposal is taking a long time and not here yet, and it might never be.

So what do we do today?

The two main approaches that I've mainly used and nested Maps and generating composite string keys, and another interesting technique came up in the Lit Discord: using BigInts bitsets as composite keys.

Nested Maps

Nested Maps work by doing successive lookups with your keys, like map.get(o1)?.get(o2). The problem is that you need a lot of Map instances. You're building a tree of maps, so there can be reuse due to branching, but at the limit, for a set of key size of K objects and N keys you need up to N * (K - 1) Maps. That can cause a lot of memory overhead.

You also have to be able to use your keys in a stable order. You need to read and write o1 then o2 always, because o2 then o1 would be a different key.

I use nested Maps occasionally, but not usually for what I would consider the composite key use cases. It's more for when my data already has a hierarchical relationship - but then you can often use the leaf nodes as keys, or roll the data you need to store into your data model.

Composite string keys

More commonly, I've uses strings as composite keys instead. Strings work well because they have value semantics. You can create the same string contents twice and they will act as the same key for Maps and Sets (and plain objects). So if you can generate the same string for a group of objects, you have yourself a composite key.

When your keys are already strings

The simplest case is when your keys are already strings. Then you can just concatenate the strings with a separator to make a composite key:

const compositeKey = (...keys: Array<string>) => keys.join('--');

The joiner string ('--') should not appear in your keys. If if could, escape the keys.

If you need to be able to supply keys in any order, you can sort them before joining:

const compositeKey = (...keys: Array<string>) =>
    keys.toSorted().join('--');

There is a performance concern here when dealing with long string keys and/or many objects in your key sets: you may be frequently generating new string instances and causing native Map code to do full string comparisons rather than reference checks. Be aware of your data and profile as needed!

When your keys are objects

If your keys are objects, a nice pattern is to generate synthetic unique IDs for objects, then concatenate those to build the composite key.

// Stores the sequential ID we generate for each object
const ids = new WeakMap();
let nextId = 1;

const getId = (o: object) => {
  let id = ids.get(o);
  if (id === undefined) {
    ids.set(id = nextId++);
  }
  return id;
}

Then we can sort and join those IDs to build the composite key:

const compositeKey = (...keys: Array<object>) =>
    keys.map(getId).sorted().join('--');

And use the composite key in a regular Map:

const map = new Map();

const setValue = (o1, o2, o3, v) => {
  return map.set(compositeKey(o1, o2, o3), v);
};

const getValue = (o1, o2, o3) => {
  return map.get(compositeKey(o1, o2, o3));
};

BigInt Bitsets

Strings work well as composite keys because we can generate them and they have value semantics. Number also have those properties, so another technique we can use is to use bitsets represented as numbers as our composite Map keys.

Each object's presence in the key would be represented by a binary digit in the key. So instead of a composite key of 0--1--2 for the first three objects seen, you would have 0b111 or 7.

This will make for much more compact keys than strings and remove the need for sorting. The only problem is that you could run out of digits. Using bitwise operations on plain numbers in JavaScript limits you to 32 bits, so you could only store 32 objects with plain numbers.

But in modern JavaScript we now have BigInts that can store any number of bits! So we'll assign sequential IDs to objects as before, but now we'll use those as number places, generate a bitmask for each object with a single bit turned on, then combine the per-object masks with a bitwise OR to generate our bitset key.

const ids = new WeakMap();
let nextId = 1n;

const getBitMask = (o: object) => {
  let id = ids.get(o);
  if (id === undefined) {
    ids.set(id = nextId++);
  }
  // Generate a mask with a single bit set in the `id`-th place
  return 1n << id;
}

const compositeKey = (...keys: Array<object>) =>
    keys.reduce((k, o) => k | getBitMask(o), 0n);

This is a really cool technique because it got a lot simpler in ES2020 with the addition of BigInt. You could encode bitsets in strings, but it's not as easy or obvious how to do so.

Using BigInts as bitsets and Map keys was actually suggested by Claude (as relayed by our Lit teammate Steve), so I presume someone is already doing this. I couldn't find anything written up about it in a quick search though, so I hope this is useful to people out there.

You can like and discuss this post on BlueSky.

Happy hacking!