Javascript Shinies: Map, Set and Symbol

It’s come to my attention recently that Map, Set and set in particular are often seen as just Array and Object with… fancy. Let’s dig more into them and see why they’re more than that and also poke Symbol with a stick.

There are some language features that we use a dozen times a day and others maybe we break out once a month. But sometime we make the choices just because we’re used to an option and we really don’t consider any alternatives.

And sometimes we should be careful talking about these things as some sort of enhanced version of an existing type. It’s not like Set is just an array on steroids.

Set: Arrays on Steroids

Sigh. So a lot of people know Set for a single reason — deduping. Sets can’t have duplicate values, so converting an array to a set gives you a deduplicated equivalent.

const myArray = [1, 2, 3, 4, 2, 3, 4, 1];
const mySet = new Set(myArray); // 1, 2, 3, 4

But actually there is a lot more to sets than just that. Sets aren’t just deduplicated, they’re indexed. That’s why they can’t store duplicates in the first place.

When you store a value in a set it actually creates a hash of the value using… probably science. Maybe math. I haven’t checked. Anyway, nerd shit happens behind the scenes and a hash is created as an index, telling it what position that value is at.

That’s all well and good but what is the benefit?

Well, the difference mostly comes up when the array or set is being used to check if we have a particular value already. When you do a check on an array using array.includes, JavaScript loops through the array to look for that value. On a large array that can be a lot. If you do the same with a Set, the value is converted with the same nerd shit as before, and the engine knows exactly where to check for it.

This means the complexity of the check with Set.has is inordinately faster than Array.includes. To be specific and use the associated terminology, Set.has is a time complexity of O(1) while Array.includes has O(n). This means that the array version scales up in operation performed at the same rate as entries are added to the array, while the set version doesn’t scale up at all. It’s identical whether it’s two entries or two million.

But it’s not all gravy. There are very good reasons not to use Set, or to favour arrays. They really come down to this key benefit of set, which is that it’s indexed. Because it’s index it can’t be sorted. It can be iterated and even spread but not sorted.

You also can’t access it using a standard index, ie, and integer. So mySet[0] is meaningless. Sets really aren’t intended to be accessed. They’re intended to be compared against.

Set doesn’t support the full suite of array functions. It has forEach, but with an interesting quirk. The callback of array foreach has a signature of (value, index), which is occasionally misused in things like React map keys. But remember, Set doesn’t have an iterating index like that and its real index is under the hood secret stuff, so it actually returns the value twice instead. Neither map or reduce are supported at all.

Another interesting point is that Set is not able to be converted to JSON. The JSON.Stringify function just returns [].

When to use it

Use a Set by preference anywhere you need to do a lot of checking if a particular value is in the collection, especially if the collection is or will become very long. Use a Set by preference when you need things that can’t be duplicated.

Remember, though, you can swap between a set and an array trivially, by spreading them, or passing in the array as a constructor parameter. This interchangeability makes Set a very good candidate for initial data processing, then later conversion for other stuff. Let’s take a common algorithms puzzle.

The goal is to write a function that would be given an array and would find the smallest positive integer that ISN’T in the array. So given an array of [5, 4, 3, 2, 1, 2, 1, 3, 4, 5] it should return 6. One constraint is that the numbers are all integers, and can be anywhere from -150000 to 150000. So you could be dealing with a very large array.

Here is a solution, just to give us a starting point

function findSmallestMissingInteger(testArray) {
 for (let i = 1; i <= testArray.length; i++) {
 if(!testArray.includes(i)) return i;
 }
}

This pretty much works, right? It loops over the numbers, incrementing `i` each time, and checks to see if testArray has that entry.

But there’s a better option, using Set.

function findSmallestMissingInteger(testArray) {
  const testSet = new Set(testArray)
  for (let i = 1; i <= testSet.size; i++) {
    if(!testSet.has(i)) return i;
  }
}

At a casual glance this looks very similar, but it’s not. The real key is the difference between testArray.includes(i) vs testSet.has(i) and how they perform. In the first one, in order to determine if there is an actually an i in this array it will have to loop through the array and check. As the array gets longer it will take longer and longer to check. In the testSet, it will simply ask. If there are a thousand entries in the array, that’s one operation. A million? That’s still just one operation.

There’s a particular way we denote these difference. They reflect the relative complexity and performance of these kinds of choices, often called Big O notation. We could do a whole article on that — not a bad idea — but the core point is O(whatever) means the way a given function scales. The most obvious is O(1). This is “fixed time”, it takes the exact same amount of time regardless of inputs. The next and only other relevant one is O(n). That means that the operations scale linearly, based on the number of inputs.

In general, O(n) is not considered terrible, and that’s what our array.includes version provides. But O(1) is absolutely the gold standard.

Map: Objects on Adderol

We tend to think of Maps as some sort of fancy object, but they’re far more than that. Let’s get the terminology straight here. Everything is an object in JavaScript. Seriously, null is an object. But by “object” I am referring to what is called a POJO — Plain Old JavaScript Object.

const user = {
 name: “Matt”,
 email: “matt@example.com”
}

Advanced stuff.

So when I say “object” that’s what I’m talking about. A pojo. So how do maps differ?

Well, mostly by being not the same as that. I know. Insightful. The internal storage for a map is more like this.

const user = [
  [“name”, “Matt”],
  [“email”, “matt@example.com”]
];

Ultimately all the values are stored as a list of tuples, with a key and a value. Tuples aren’t really a thing in JavaScript, but they’re essentially an array of a specific length where the positions have defined values. Here, for example, the first one is the key, it doesn’t have to be defined so, it just is. A lot of languages support tuples, such as Elixir, Rust and Python.

Anyway, these tuples are stored in order, and their keys are also hashed in the same way as the set, for optimal lookup.

By the way, if your thought about the above code is that it looks exactly the same as Object.entries(myObject) you are 100% correct. Gold star!

So what can map do that an object can’t? Well, for one, you can use pretty much anything as a key. Number? Done. Whole-ass object? No problem!

It might seem like you can do this in an object. And you kind of can, but it doesn’t work like you might think.

const user = {
  name: “Matt”,
  email: “matt@example.com”
}

const userWithMetadata = {
  [user]: someMetadata
}

That’s making using the object as a key. Great job!

Well actually it’s not. That object is being converted into the string [object Object] and that string is the new key. What we actually have is an object like this.

const userWithMetadata = {
 "[object Object]": someMetadata
}

And it really is that dumb and it really is the actual string listed there. So this will work: userWithMetadata[‘[object Object]’].

The same applies to anything passed as an object key, it will be stringified. Your number? A string. Your date object? A big long string.

The same doesn’t apply to map. Because it’s stored in those entry tuples it can be a lot more flexible about what the key is. Because it isn’t really a key. Just entry position 0. This makes it possible to store an actual object as the real key.

const userMatt = {
  name: “Matt”,
  email: “matt@example.com”
}

const userWithMetadata = new Map();

map.add(userMatt, someMetadata);

const mattadata = userWithMetadata[userMatt];

There’s a big “catch” with this. It’s not really a catch. It’s the point. When you store an object as the key like this you are not storing it by the contents of the object, but by its reference. So anything that clones or rebuilds the object will lose that reference. It’s important to be clear that the contents of the object are irrelevant. Query the same exact data from the database? Different object. The same applies to something like a date. The exact same date, down to the same nanosecond is not the same object.

This means is you’re doing something like this you’re going to have to keep track of and maintain the object references. There’s actually a pretty good chance you don’t want to do any such thing. Still, it’s pretty neat that you can. It’s also worth noting that 1 and "1" are different keys, and would be consistently honoured.

There are a few other benefits of Map, all of which stem largely from its “entries” based internal structure. Because it’s just a list of entries it’s trivial to get a size: myMap.size. Determining the presence of a field is also very easy: myMap.has(“penguin”). Map respects the insertion order, unlike an object, which gives you no guarantees at all of the order of the properties. This is rarely that important, but just occasionally can be critical. Last but not least, maps are iterable. To iterate an object you need to use Object.entries but that format is already what the Map uses internally. Note that it’s not an array, so you can do forEach but you can’t do map or reduce.

When to use it

A Map has a fairly limited usecase compared to a standard object, but it’s useful to know as an option — specifically when you need or want to key by something unusual. An object, a date, or an integer.

Symbol: I have no idea what these are on but it’s good stuff

Symbols get sort of obscure. Essentially a Symbol is a way of wrapping an instance of a primitive so that it becomes a reference, and each instance is unique.

const matt1 = Symbol(“matt”);
const matt2 = Symbol(“matt”);

console.assert(matt1 === matt2, “Not equal”)

The above will display “Not equal”, because matt1 and matt2 are not the same.

Symbols are probably not something that you’ll use often but they’re used in the background of various libraries.

Where symbols get more interesting is that these symbols can be combined with maps and even standard objects. This is where they can be surprisingly useful.

You can store symbols as an object key and you can update it or read it out.

const sym = Symbol(‘secret’);
const obj = {
  visible: ‘hi’,
  [sym]: ‘hidden’,
};

If you do that you can access this easily. obj[sym] will work and give you back the value hidden.

You can update this as you want, retrieve it, etc. So what’s the benefit. It’s surprising. This value doesn’t exist. If you spread that object, there’s only visible: ‘hi’, if you do Object.entries there is only that one entry. If you try JSON.stringify(obj) it won’t have that hidden property. Absolutely nothing you do will make Symbol keys visible later on.

This makes it possible to add things like metadata or temporary information onto an object. You can add it, modify it, access it at will. You can use it to set some kind of state like that this object has been seen or actioned, but then as soon as you return or use the object the fields get stripped. Let’s make a random NestJS get controller method with a Prisma call.

@Get()
async getUser() {
  const approved = Symbol(‘approved’);
  const user = await this.prisma.user.findFirst();
  user[approved] = true;
  return user;
}

That approved key won’t be included in the user. It will be stripped out before being sent. This is obviously a trivial and contrived example, but you could see something where you loop over users and filter by the users that are approved, then returning the object clean. I can think myself of times I’ve added a temporary property to an object for some housekeeping, then had to strip it out later.

In Conclusion

These tools aren’t your daily drivers, but it’s useful to have them in your back pocket, to mix a metaphor.

Set is by far the most useful, and well worth considering if you’re looking up an array for the presence of its values. The others are a bit more occasional usage, but they remain valuable to know.