Shirsh Zibbu

@zhirzh

A mental model for “Weak” structures

The idea behind weak data structures is pretty far fetched for most developers who have strong, rigid mental models of how maps and key/value pairs and references work.

In this article, I try to explore the workings of weak structures by observing their behaviour, without being bothered about their implementation.

Concept Refreshers

References and cloning

In the code below, we create a variable x that holds a reference to value 111 that is stored somewhere in the memory. We then create another variable y that is a clone of x. Since x holds a primitive value, it is deep cloned into y.

var x = 111;
var y = x;
y *= 2;
console.log(x, y);
// 111 222

In the following snippet, we do everything exactly the same as before, except for the first assignment — assigning x an object instead of a primitive.

As a result, y holds a new reference to the same object that x references. This is shallow cloning.

var x = {a: 111};
var y = x;
y.a *= 2;
console.log(x.a, y.a);
// 222 222

Garbage Collection

The basic principle of garbage collection is that if some memory location can’t be accessed then it must be removed from the memory.

Consider the following snippet:

x = {...};
y = x;
delete x;
y = ...;

When we created x and y, we were holding 2 references to the same thing. When we delete x, we lose one reference but we can still access the object from y. However, when we reassign y, we lose all references to the object and it can’t be accessed anymore, but it still occupies some memory.

This is where a GC comes in handy. A garbage collector will notice this anomaly and will quickly “free” the occupied inaccessible memory. You can read more about this here on MDN.

Map vs WeakMap

Map

First, let’s observe how a Map behaves in the wild. When we add a new key/value pair to a map, the map stores the mapping. Primitives will get deep cloned and object types will get a new reference pointing to them.

obj = {};
map = new Map();
map.set(obj, 123);
console.log(map.get(obj)); // 123
console.log(map.size); // 1
console.log(map.keys());
// [ {} ]

If we now delete obj or re-assign it, it will no lose its reference to {}. But the map still holds the key/value pair. This so happens because when a map stores a key/value pair, it creates references to objects (for both items).

obj = {};
map = new Map();
map.set(obj, 123);
// de-reference `obj` from {}
obj = ...
console.log(map.get(obj)); // undefined
console.log(map.size); // 1
console.log(map.keys());
// [ {} ]

WeakMap

In contrast, we can say that a WeakMap creates reference to a reference — meta reference. Here’s the same code with a WeakMap.

obj = {};
wMap = new WeakMap();
wMap.set(obj, 123);
console.log(wMap.get(obj)); // 123

If we now delete/reassign the obj, we will lose the key in a key/value pair. Without the a key, the key/pair record in the map is marked for GC and then the value meets the same fate.

Set and WeakSet

A set is a collection of unique entities — just like the keys in a map. So if we ignore the “value” part of a map, we end up with a set. Similarly, if we ignore the second columns in the map diagram, we get our Set and WeakSet.

Conclusion

Now that we “know” that weak structures create meta-references, it makes perfect sense why we can’t iterate over them or check their size.

If you were to now ask the question why primitives can’t be keys, I’d say that
“I can’t answer that”. This question is related to what happens under the hood. You can read more about them here and here.

In contrast, we can say that a WeakMap creates reference to a reference.

More by Shirsh Zibbu

Topics of interest

More Related Stories