How to use Data Structures in javascript

Following data structures are covered in this post:

  • Map
  • Set
  • WeakMap
  • WeakSet

Map

The Map object is a simple key/value map. Any value both objects and primitive values may be used as either a key or a value. Map that is a map of an object, especially a dictionary of dictionaries, will only map to the object’s insertion order – which is random and not ordered.

new Map([iterable])

where, iterable is an Array or other iterable object whose elements are key-value pairs (2-element Arrays). Each key-value pair is added to the new Map. null is treated as undefined.

var myMap = new Map();

var keyString = "a string",
    keyObj = {},
    keyFunc = function () {};

// setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");

myMap.size; // 3

// getting the values
myMap.get(keyString);    // "value associated with 'a string'"
myMap.get(keyObj);       // "value associated with keyObj"
myMap.get(keyFunc);      // "value associated with keyFunc"

myMap.get("a string");   // "value associated with 'a string'"
                            // because keyString === 'a string'
myMap.get({});           // undefined, because keyObj !== {}
myMap.get(function() {}) // undefined, because keyFunc !== function () {}

Key Equality

Key equality is based on the "same-value" algorithm. NaN is considered the same as NaN (even though NaN !== NaN) and all other values are considered equal according to the semantics of the === operator.

var myMap = new Map();
myMap.set(NaN, "not a number");

myMap.get(NaN); // "not a number"

var otherNaN = Number("foo");
myMap.get(otherNaN); // "not a number"

Objects and maps compared

Objects are similar to Maps in that both

  • let you set keys to values
  • retrieve those values
  • delete keys
  • detect whether something is stored at a key

The keys of an Object are Strings and Symbols. You can get the size of a Map easily while you have to manually keep track of size for an Object.

Iterating Maps with for..of

var myMap = new Map();
myMap.set(0, "zero");
myMap.set(1, "one");
for (var [key, value] of myMap) {
    console.log(key + " = " + value);
}
// 0 = zero
// 1 = one

for (var key of myMap.keys()) {
    console.log(key);
}
// 0
// 1

for (var value of myMap.values()) {
    console.log(value);
}
// zero
// one

for (var [key, value] of myMap.entries()) {
    console.log(key + " = " + value);
}
// 0 = zero
// 1 = one

Set

The Set object lets you store unique values of any type, whether primitive values or object references.

new Set([iterable]);

Where, if an iterable object is passed, all of its elements will be added to the new Set. null is treated as undefined.

var mySet = new Set();

mySet.add(1);
mySet.add(5);
mySet.add("some text");
var o = {a: 1, b: 2};
mySet.add(o);

mySet.has(1);           // true
mySet.has(3);           // false
mySet.has(5);           // true
mySet.has("some text"); // true
mySet.has(o);           // true

mySet.size;             // 4

mySet.delete(5);        // removes 5 from the set
mySet.has(5);           // false, 5 has been removed

mySet.size;             // 3, we just removed one value

Value Equality

Because each value in the Set has to be unique, the value equality will be checked and is NOT based on the same algorithm as the one used in the === operator.

Also, NaN and undefined can also be stored in a Set. NaN is considered the same as NaN (even though NaN !== NaN).

Iterating sets

var mySet = new Set();

mySet.add(1);
mySet.add(5);
mySet.add("some text");
var o = {a: 1, b: 2};
mySet.add(o);

for (let item of mySet) console.log(item);
// 1 
// 5
// "some text"
// Object {a: 1, b: 2}}

for (let item of mySet.keys()) console.log(item);
// 1 
// 5
// "some text"
// Object {a: 1, b: 2}}

for (let item of mySet.values()) console.log(item);
// 1 
// 5
// "some text"
// Object {a: 1, b: 2}}

for (let item of mySet.entries()) console.log(key);
// [1, 1]
// [5, 5]
// ["some text", "some text"]
// [{a: 1, b: 2}, {a: 1, b: 2}]

Use the spread operator to transform a set into an Array.

console.log([...mySet]); 
// [1, 5, "some text", Object]

WeakMap

The WeakMap object is a collection of key/value pairs in which the keys are weakly referenced.

new WeakMap([iterable])

where, Iterable is an Array or other iterable object whose elements are key-value pairs (2-element Arrays). Each key-value pair will be added to the new WeakMap. null is treated as undefined.

In native WeakMaps, references to key objects are held “weakly”, which means that they do not prevent garbage collection in case there would be no other reference to the object.

var wm1 = new WeakMap(),
    wm2 = new WeakMap(),
    wm3 = new WeakMap();
var o1 = {},
    o2 = function(){},
    o3 = window;

wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm1.get(o2); // "azerty"

wm2.set(o1, o2); // a value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // keys and values can be any objects. Even WeakMaps!
wm2.get(o2); // undefined, because there is no key for o2 on wm2
wm2.get(o3); // undefined, because that is the set value

Why WeakMap?

Custom implementation would have two main inconveniences. The first one is an O(n) search (n being the number of keys in the map). The second one is a memory leak issue. With manually written maps, the array of keys would keep references to key objects, preventing them from being garbage collected.

WeakSet

The WeakSet object lets you store weakly held objects in a collection.

new WeakSet([iterable]);

Where,
If an iterable object is passed, all of its elements will be added to the new WeakSet. null is treated as undefined.

WeakSet objects are collections of objects. An object in the WeakSet may only occur once; it is unique in the WeakSet’s collection.

var ws = new WeakSet();
var obj = {};
var foo = {};

ws.add(window);
ws.add(obj);

ws.has(window); // true
ws.has(foo);    // false, foo has not been added to the set

ws.delete(window); // removes window from the set
ws.has(window);    // false, window has been removed

Set vs WeakSet

The main differences to the Set object are:

  • In contrast to Sets, WeakSets are collections of objects only and not of arbitrary values of any type.
  • The WeakSet is weak: References to objects in the collection are held weakly. If there is no other reference to an object stored in the WeakSet, they can be garbage collected. That also means that there is no list of current objects stored in the collection. WeakSets are not enumerable.