2015-01-05

ECMAScript 6: maps and sets

Update 2015-01-14:ECMAScript 6 sets: union, intersection, difference

Among others, the following four data structures are new in ECMAScript 6: Map, WeakMap, Set and WeakSet. This blog post explains how they work.

Map

JavaScript has always had a very spartan standard library. Sorely missing was a data structure for mapping values to values. The best you can get in ECMAScript 5 is a map from strings to arbitrary values, by abusing objects. Even then there are several pitfalls that can trip you up.

The Map data structure in ECMAScript 6 lets you use arbitrary values as keys and is highly welcome.

Basic operations

Working with single entries:

    > let map = new Map();
    
    > map.set('foo', 123);
    > map.get('foo')
    123
    
    > map.has('foo')
    true
    > map.delete('foo')
    true
    > map.has('foo')
    false

Determining the size of a map and clearing it:

    > let map = new Map();
    > map.set('foo', true);
    > map.set('bar', false);
    
    > map.size
    2
    > map.clear();
    > map.size
    0

Setting up a map

You can set up a map via an iterable over key-value “pairs” (arrays with 2 elements). One possibility is to use an array (which is iterable):

    let map = new Map([
        [ 1, 'one' ],
        [ 2, 'two' ],
        [ 3, 'three' ], // trailing comma is ignored
    ]);

Alternatively, the set method is chainable:

    let map = new Map()
    .set(1, 'one')
    .set(2, 'two')
    .set(3, 'three');

Keys

Any value can be a key, even an object:

    let map = new Map();
    
    const KEY1 = {};
    map.set(KEY1, 'hello');
    console.log(map.get(KEY1)); // hello
    
    const KEY2 = {};
    map.set(KEY2, 'world');
    console.log(map.get(KEY2)); // world
What keys are considered equal?

Most map operations need to check whether a value is equal to one of the keys. They do so via the internal operation SameValueZero, which works like === [1], but considers NaN to be equal to itself.

Let’s first see how === handles NaN:

    > NaN === NaN
    false

Conversely, you can use NaN as a key in maps, just like any other value:

    > let map = new Map();
    
    > map.set(NaN, 123);
    > map.get(NaN)
    123

Like ===, -0 and +0 are considered the same value (which is normally the best way to handle the two zeros [3]).

    > map.set(-0, 123);
    > map.get(+0)
    123

Different objects are always considered different. That is something that can’t be configured (yet), as explained later, in the FAQ.

    > new Map().set({}, 1).set({}, 2).size
    2

Getting an unknown key produces undefined:

    > new Map().get('asfddfsasadf')
    undefined

Iterating

Let’s set up a map to demonstrate how one can iterate over it.

    let map = new Map([
        [false, 'no'],
        [true,  'yes'],
    ]);

Maps record the order in which elements are inserted and honor that order when iterating over keys, values or entries.

Iterables for keys and values

keys() returns an iterable [4] over the keys in the map:

    for (let key of map.keys()) {
        console.log(key);
    }
    // Output:
    // false
    // true

values() returns an iterable over the values in the map:

    for (let value of map.values()) {
        console.log(value);
    }
    // Output:
    // no
    // yes
Iterables for entries

entries() returns the entries of the map as an iterable over [key,value] pairs (arrays).

    for (let entry of map.entries()) {
        console.log(entry[0], entry[1]);
    }
    // Output:
    // false no
    // true yes

Destructuring enables you to access the keys and values directly:

    for (let [key, value] of map.entries()) {
        console.log(key, value);
    }

The default way of iterating over a map is entries():

    > map[Symbol.iterator] === map.entries
    true

Thus, you can make the previous code snippet even shorter:

    for (let [key, value] of map) {
        console.log(key, value);
    }
Spreading iterables

The spread operator (...) turns an iterable into the arguments of a function or parameter call. For example, Math.max() accepts a variable amount of parameters. With the spread operator, you can apply that method to iterables.

    > let arr = [2, 11, -1];
    > Math.max(...arr)
    11

Spread also turns an iterable into the elements of an array. That lets us convert the result of Map.prototype.keys() (an iterable) into an array:

    let map = new Map([
        [1, 'one'],
        [2, 'two'],
        [3, 'three'],
    ]);
    let arr = [...map.keys()]; // [1, 2, 3]

Looping over entries

The Map method forEach has the following signature:

    Map.prototype.forEach((value, key, map) => void, thisArg?) : void

The signature of the first parameter mirrors the signature of the callback of Array.prototype.forEach, which is why the value comes first.

    let map = new Map([
        [false, 'no'],
        [true,  'yes'],
    ]);
    map.forEach((value, key) => {
        console.log(key, value);
    });
    // Output:
    // false no
    // true yes

Mapping and filtering

You can map() and filter() arrays, but there are no such operations for maps. The solution:

  1. Convert the map into an array of [key,value] pairs.
  2. Map or filter the array.
  3. Convert the result back to a map.

That’s what happens in the following example:

    let map0 = new Map()
    .set(1, 'a')
    .set(2, 'b')
    .set(3, 'c');
    
    let map1 = new Map(
        [...map0] // step 1
        .filter(([k, v]) => k < 3) // step 2
    ); // step 3
    // Resulting map: {1 => 'a', 2 => 'b'}
    
    let map2 = new Map(
        [...map0] // step 1
        .map(([k, v]) => [k * 2, '_' + v]) // step 2
    ); // step 3
    // Resulting map: {2 => '_a', 4 => '_b', 6 => '_c'}

Step 1 is performed by the spread operator (...) which I have explained previously.

Map API

Handling single entries:

  • Map.prototype.get(key) : any
    Returns the value that key is mapped to in this map. If there is no key key in this map, undefined is returned.

  • Map.prototype.set(key, value) : this
    Maps the given key to the given value. If there is already an entry whose key is key, it is updated. Otherwise, a new entry is created.

  • Map.prototype.has(key) : boolean
    Returns whether the given key exists in this map.

  • Map.prototype.delete(key) : boolean
    If there is an entry whose key is key, it is removed and true is returned. Otherwise, nothing happens and false is returned.

Handling all entries:

  • get Map.prototype.size : number
    Returns how many entries there are in this map.

  • Map.prototype.clear() : void
    Removes all entries from this map.

Iterating and looping: happens in the order in which entries were added to a map.

  • Map.prototype.entries() : Iterable<[any,any]>
    Returns an iterable with one [key,value] pair for each entry in this map. The pairs are arrays of length 2.

  • Map.prototype.forEach((value, key, collection) => void, thisArg?) : void
    The first parameter is a callback that is invoked once for each entry in this map. If thisArg is provided, this is set to it for each invocation. Otherwise, this is set to undefined.

  • Map.prototype.keys() : Iterable<any>
    Returns an iterable over all keys in this map.

  • Map.prototype.values() : Iterable<any>
    Returns an iterable over all values in this map.

  • Map.prototype[Symbol.iterator]() : Iterable<[any,any]>
    The default way of iterating over maps. Refers to Map.prototype.entries.

WeakMap

A WeakMap is a map that doesn’t prevent its keys from being garbage-collected. That means that you can associate data with objects without having to worry about memory leaks.

A WeakMap is a data structure whose keys must be objects and whose values can be arbitrary values. It has the same API as Map, with one significant difference: you can’t iterate over the contents – neither the keys, nor the values, nor the entries. You can’t clear a WeakMap, either.

The rationales for these restrictions are:

  • The volatility of WeakMaps makes iteration difficult.

  • Not having clear() provides a security property. Quoting Mark Miller: “The mapping from weakmap/key pair value can only be observed or affected by someone who has both the weakmap and the key. With clear(), someone with only the WeakMap would’ve been able to affect the WeakMap-and-key-to-value mapping.”

Using WeakMaps for private data

The following code uses the WeakMaps _counter and _action to store private data.

    let _counter = new WeakMap();
    let _action = new WeakMap();
    class Countdown {
        constructor(counter, action) {
            _counter.set(this, counter);
            _action.set(this, action);
        }
        dec() {
            let counter = _counter.get(this);
            if (counter < 1) return;
            counter--;
            _counter.set(this, counter);
            if (counter === 0) {
                _action.get(this)();
            }
        }
    }

Let’s use Countdown:

    > let c = new Countdown(2, () => console.log('DONE'));
    > c.dec();
    > c.dec();
    DONE

Because Countdown keeps instance-specific data elsewhere, its instance c has no own property keys:

    > Reflect.ownKeys(c)
    []

WeakMap API

WeakMaps have only four methods, all of them work the same as the Map methods.

  • WeakMap.prototype.get(key) : any
  • WeakMap.prototype.set(key, value) : this
  • WeakMap.prototype.has(key) : boolean
  • WeakMap.prototype.delete(key) : boolean

Set

ECMAScript 5 doesn’t have a set data structure, either. There are two possible work-arounds:

  • Use the keys of an object to store the elements of a set of strings.
  • Store (arbitrary) set elements in an array: Check whether it contains an element via indexOf(), remove elements via filter(), etc. This is not a very fast solution, but it’s easy to implement. One issue to be aware of is that indexOf() can’t find the value NaN.

ECMAScript 6 has the data structure Set which works for arbitrary values, is fast and handles NaN correctly.

Basic operations

Managing single elements:

    > let set = new Set();
    > set.add('red')
    
    > set.has('red')
    true
    > set.delete('red')
    true
    > set.has('red')
    false

Determining the size of a set and clearing it:

    > let set = new Set();
    > set.add('red')
    > set.add('green')
    
    > set.size
    2
    > set.clear();
    > set.size
    0

Setting up a set

You can set up a set via an iterable over the elements that make up the set. For example, via an array:

    let set = new Set(['red', 'green', 'blue']);

Alternatively, the add method is chainable:

    let set = new Set().add('red').add('green').add('blue');

Values

Like maps, elements are compared similarly to ===, with the exception of NaN being like any other value.

    > let set = new Set([NaN]);
    > set.size
    1
    > set.has(NaN)
    true

Adding an element a second time has no effect:

    > let set = new Set();
    
    > set.add('foo');
    > set.size
    1
    
    > set.add('foo');
    > set.size
    1

Similarly to ===, two different objects are never considered equal (which can’t currently be customized, as explained in the FAQ, later):

    > let set = new Set();
    
    > set.add({});
    > set.size
    1
    
    > set.add({});
    > set.size
    2

Iterating

Sets are iterable and the for-of loop works as you’d expect:

    let set = new Set(['red', 'green', 'blue']);
    for (let x of set) {
        console.log(x);
    }
    // Output:
    // red
    // green
    // blue

As you can see, sets preserve iteration order. That is, elements are always iterated over in the order in which they were inserted.

The previously explained spread operator (...) works with iterables and thus lets you convert a set to an array:

    let set = new Set(['red', 'green', 'blue']);
    let arr = [...set]; // ['red', 'green', 'blue']

We now have a concise way to convert an array to a set and back, which has the effect of eliminating duplicates from the array:

    let arr = [3, 5, 2, 2, 5, 5];
    let unique = [...new Set(arr)]; // [3, 5, 2]

Mapping and filtering

In contrast to arrays, sets don’t have the methods map() and filter(). A work-around is to convert them to arrays and back.

Mapping:

    let set = new Set([1, 2, 3]);
    set = new Set([...set].map(x => x * 2));
    // Resulting set: {2, 4, 6}

Filtering:

    let set = new Set([1, 2, 3, 4, 5]);
    set = new Set([...set].filter(x => (x % 2) == 0));
    // Resulting set: {2, 4}

API

Single set elements:

  • Set.prototype.add(value) : this
    Adds value to this set.

  • Set.prototype.has(value) : boolean
    Checks whether value is in this set.

  • Set.prototype.delete(value) : boolean
    Removes value from this set.

All set elements:

  • get Set.prototype.size : number
    Returns how many elements there are in this set.

  • Set.prototype.clear() : void
    Removes all elements from this set.

Iterating and looping:

  • Set.prototype.values() : Iterable<any>
    Returns an iterable over all elements of this set.

  • Set.prototype[Symbol.iterator]() : Iterable<any>
    The default way of iterating over sets. Points to Set.prototype.values.

  • Set.prototype.forEach((value, key, collection) => void, thisArg?)
    Loops over the elements of this set and invokes the callback (first parameter) for each one. value and key are both set to the element, so that this method works similarly to Map.prototype.forEach. If thisArg is provided, this is set to it for each call. Otherwise, this is set to undefined.

Symmetry with Map: The following two methods only exist so that the interface of sets is similar to the interface of maps. Each set element is handled as if it were a map entry whose key and value are the element.

  • Set.prototype.entries() : Iterable<[any,any]>
  • Set.prototype.keys() : Iterable<any>

WeakSet

A WeakSet is a set that doesn’t prevent its elements from being garbage-collected. Consult the section on WeakMap for an explanation of why WeakSets don’t allow iteration, looping and clearing.

Given that you can’t iterate over their elements, there are not that many use cases for WeakSets. They enable you to mark objects, to associate them with boolean values.

API

WeakSets have only three methods, all of them work the same as the Set methods.

  • WeakSet.prototype.add(value)
  • WeakSet.prototype.has(value)
  • WeakSet.prototype.delete(value)

FAQ

Why size and not length?

Question: Arrays have the property length to count the number of entries. Why do maps and set have a different property, size, for this purpose?

Answer: length is for sequences, data structures that are indexable – like arrays. size is for collections that are primarily unordered – like maps and sets.

Why can’t I configure how maps and sets compare keys and values?

Question: It would be nice if there were a way to configure what map keys and what set elements are considered equal. Why isn’t there?

Answer: That feature has been postponed, as it is difficult to implement properly and efficiently. One option is to hand callbacks to collections that specify equality.

Another option, available in Java, is to specify equality via a method that object implement (equals() in Java). However, this approach is problematic for mutable objects: In general, if an object changes, its “location” inside a collection has to change, as well. But that’s not what happens in Java. JavaScript will probably go the safer route of only enabling comparison by value for special immutable objects (so-called value objects). Comparison by value means that two values are considered equal if their contents are equal. Primitive values are compared by value in JavaScript.

References

  1. Equality Operators: === Versus ==” in “Speaking JavaScript”
  2. NaN” in “Speaking JavaScript”
  3. Two Zeros” in “Speaking JavaScript”
  4. Iterators and generators in ECMAScript 6

No comments: