ECMAScript 6: maps and sets
Check out my book (free online): “Exploring ES6”. Updated version of this blog post: chapter “Maps and Sets”.
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:
- Convert the map into an array of [key,value] pairs.
- Map or filter the array.
- 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 thevaluethatkeyis mapped to in this map. If there is no keykeyin this map,undefinedis returned.Map.prototype.set(key, value) : this
Maps the given key to the given value. If there is already an entry whose key iskey, 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 iskey, it is removed andtrueis returned. Otherwise, nothing happens andfalseis 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. IfthisArgis provided,thisis set to it for each invocation. Otherwise,thisis set toundefined.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 toMap.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. Withclear(), 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) : anyWeakMap.prototype.set(key, value) : thisWeakMap.prototype.has(key) : booleanWeakMap.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 viafilter(), etc. This is not a very fast solution, but it’s easy to implement. One issue to be aware of is thatindexOf()can’t find the valueNaN.
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
Addsvalueto this set.Set.prototype.has(value) : boolean
Checks whethervalueis in this set.Set.prototype.delete(value) : boolean
Removesvaluefrom 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 toSet.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.valueandkeyare both set to the element, so that this method works similarly toMap.prototype.forEach. IfthisArgis provided,thisis set to it for each call. Otherwise,thisis set toundefined.
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
- “Equality Operators: === Versus ==” in “Speaking JavaScript”
- “NaN” in “Speaking JavaScript”
- “Two Zeros” in “Speaking JavaScript”
- Iterators and generators in ECMAScript 6
Comments
Post a Comment