The way in which data is structured plays a vital role in our ability to efficiently perform certain operations on data, or to solve certain problems in relation to the data. For example, you can delete any item from a doubly-linked list in constant time, whereas that could take linear time if the list is represented as an array. Similarly, searching for the presence of a key in an array of keys can be done more efficiently in logarithmic time when the array is sorted, as opposed to when it is not sorted.
Some very popular programming languages like Java and Python provide lots of useful data structure implementations out of the box, whereas the ubiquitous JavaScript programming language appears to be pretty lean in that regard. However, like most programming languages, JavaScript ships with some very basic data types — such as arrays, strings, objects, sets, maps, etc.
Prior to the ECMAScript 2015 specification updates (popularly known as ES6), JavaScript provided Array objects as the only standard, inbuilt indexed collections — although there were other exotic objects such as the arguments and String objects, which behaved like arrays with special handling for integer index property keys, usually referred to as array-like objects, but were not really indexed collections.
Starting with ES2015, a handful of new standard inbuilt types have been added to JavaScript, such as:
SymbolPromiseProxyA number of typed array objects were also added, which, just like arrays, are also indexed collections themselves. In addition to these, a new category known as keyed collections has also been added to the language, with these inbuilt object types:
MapSetWeakMapWeakSetJust as the name implies, every element (known as an entry) in a keyed collection can be identified by some kind of key, such that the keys in the collection are distinct — meaning that every key maps exactly to one entry in the collection. If you are familiar with hash tables, then you may have already inferred their usefulness here in ensuring that the average access time is sublinear on the number of elements in the collection.
In this post, we’ll take a peek at how we can use JavaScript’s Map and Set objects to efficiently solve problems. Before we jump right in, let’s consider a sample problem.
Below is a sample problem:
đź’ˇ Contains Duplicates
Given an array of integersnums, returntrueif any element appears at least twice in the array, and returnfalseif every element is distinct.
Pause for a moment and try solving this problem on your own, before you proceed. If the nums array was sorted, will that simplify the solution?
Now, here is a working solution to the problem:
function hasDuplicates(nums) {
// 1. Sort the array in-place (sorting makes it easier)
nums.sort((a, b) => a - b);
if (nums.length > 1) {
// 2. Loop through the sorted array until a duplicate is found
for (let i = 1, len = nums.length; i < len; i++) {
// If a duplicate is found, return immediately
if (nums[i] == nums[i - 1]) return true;
}
}
// 3. If it ever gets here, no duplicate was found
return false;
}
There is no doubt that this solution works, for the given constraints of our problem. The reasoning behind why it should work is quite straightforward — if the array of integers is already sorted, then it is possible to check in a single pass whether or not two consecutive, equal integers exist in the array. Since there isn’t any guarantee that the array of integers will already be sorted, the solution first tries to sort the array, before checking for duplicate integers.
Let’s analyze our solution. The running time of the above solution will grow in a linearithmic fashion as the size of the input array grows. While this isn’t a bad thing, it’s not so great either because, even for a pre-sorted array, it would still take a significant amount of time to process, as a lot of time is spent trying to sort the array first.
The solution also uses Array.prototype.sort to sort the input array in-place — modifying the original input array as a result. Hence, no additional memory is required for the sort.
It is important to note that, if the problem required that the original order of the input array remain unchanged, then a copy of the input array must be made before using this solution. This is tantamount to the use of additional memory that will grow in linear fashion as the size of the input array grows.
Now, whether this is an acceptable solution or not is subject to a number of factors — including but not limited to:
If we are certain that the array of integers might not already be sorted, and we also don’t mind using some auxiliary space — provided we can get a faster running time — then this solution is not the best. As we progress, we will soon see that we can actually come up with a solution whose running time grows linearly, rather than linearithmically, with the size of the input.
Map objectsWe can summarize the ECMAScript 2015 specification definition of a Map object as follows:
That means any valid JavaScript value — both primitive values and object references, including unseemly values like NaN and undefined — can be used as a key in a Map object collection.
SameValueZeroTo determine whether a key already exists in the Map object collection — in other words, ensuring that keys are distinct — the ECMAScript SameValueZero comparison algorithm is used.
We use this comparison algorithm because, if one of the listed algorithms were used:
NaN already exists in the collection, since NaN === NaN always evaluates to falseNaN already exists in the collection, but the keys +0 and -0 are different keys and will be treated as such, despite that +0 === -0 always evaluates to trueThe SameValueZero comparison algorithm, however, behaves like the SameValue comparison algorithm, except that it considers both +0 and -0 to be the same key. If the SameValueZero comparison algorithm were to be implemented as a JavaScript function, it would look like this:
function SameValueZero(x, y) {
return x === y || (Number.isNaN(x) && Number.isNaN(y));
}
Each key/value pair contained in a Map object collection is usually referred to as an entry object, or entry. An entry object is usually represented using a two-element array — more like a tuple in most other programming languages — whose first element is the key and whose second element is the value.
The type definition for a generic Map object entry should look like this (in TypeScript):
type MapEntry<Key, Value> = [Key, Value];
That said, you can use JavaScript syntax, such as a destructuring assignment, on a Map object entry like you would with an array, as demonstrated in the following for...of loop example:
/**
* Iterating over entries of `Map` object using a
* `for...of` loop — assuming that `map` has been
* defined already as a `Map` object.
*/
for (const [key, value] of map) {
console.log(key, value);
}
Both Map and Set objects inherit an entries() method from their corresponding constructors’ prototype objects. This entries() method returns an iterator for all of the entries contained in the collection with respect to their insertion order.
For Map objects, however, the iterator returned by the entries() method also serves as the default iterator of the collection.
At the time of this article’s publication, the only way to create a Map object is by invoking the global Map constructor function. The constructor function must be invoked with the new keyword — otherwise, a TypeError will be thrown.
When the Map constructor function is invoked without arguments, an empty Map object of 0 size is returned.
// Throws a`TypeError` — when invoked without `new` keyword const throwTypeErrorMap = Map(); // Creates an empty `Map` object of 0 `size` const mapA = new Map(); // Omitting the parentheses — when invoked without arguments // Also creates an empty `Map` object of 0 `size` const mapB = new Map; console.log(mapA.size); // 0 console.log(mapB.size); // 0
The Map constructor function can also be invoked with an optional iterable argument. When specified, iterable must be a JavaScript object that:
Learn more →Array, String, and Set, as well as MapMap key, and whose second element is the value to associate with that keyIf the iterable argument does not meet these two requirements, a TypeError will be thrown — the only exception being when iterable is the value null or undefined, in which case the effect is the same as calling the Map constructor function without any argument, and an empty Map object of 0 size is created.
Let’s pay more attention to the second requirement stated above. It is obvious that a new Map object cannot be created from a string primitive, even though String objects are iterable objects themselves.
// Map from String — throws a `TypeError`
const throwTypeErrorMap = new Map("programming");
When we create a new Map object from another iterable object, an empty Map object is first created, and then the following steps are taken for each entry object produced by the iterator object, which is returned by the iterable:
key and value, respectivelykey already exists in the Map object collection using SameValueZero comparison
valueMap object collection with that key and value (if the key is 0, change it to +0 before appending a new entry to the collection)const pairs = [[1, 3], [3, 3], [4, 2], [2, 2]];
// (1) Map from Array or Set
// Here a set is created from the pairs array and
// used to create the map. However, the map can also
// be created directly from the pairs array.
const mapA = new Map(new Set(pairs));
console.log(mapA.size); // 4
console.log(…mapA); // [1, 3] [3, 3] [4, 2] [2, 2]
// (2) Map from Map
// New map contains all the items of the original map
// However, both maps are entirely different objects.
// Think of it as creating a clone of a map.
const mapB = new Map(mapA);
console.log(…mapA); // [1, 3] [3, 3] [4, 2] [2, 2]
console.log(…mapB); // [1, 3] [3, 3] [4, 2] [2, 2]
console.log(mapA === mapB); // false
console.log(mapA.size === mapB.size); // true
// (3) Map from Object
// In ES6, the Object.entries() method was added,
// and it returns an array of entries representing
// key/value pairs for every key in an object.
const mapC = new Map(Object.entries({
language: “JavaScript”,
hello: “world”
}));
console.log(mapC.size); // 2
console.log(…mapC); // [“language”, “JavaScript”] [“hello”, “world”]
Now that we are able to create new Map objects, let’s go ahead to explore their instance properties and methods.
Map object instance properties and methodsWe’ve already seen the size property in action a couple of times. Just as the name implies, sizereturns the number of entries in the Map object at any instant.
It might interest you to know that the size property is an accessor property and not a data property. Also, it only has a get accessor function, and not a set accessor function. That’s the reason why its value cannot be overridden by an assignment operation.
Whenever you access the size property of a Map object, its get accessor function will be invoked, which basically counts and returns the number of elements (entries) currently in the Map object.
There are several cases where it is sufficient to know only whether or not an entry with a particular key is present in a Map object. Every Map object will originally have a has() method — which can be called to assert whether or not an entry with a specified key is present in the Map object. The has() method returns a boolean value — true if the specified key is present, and false otherwise.
const M = new Map(Object.entries({
language: "JavaScript",
hello: "world"
}));
console.log(M.has("hello")); // true
console.log(M.has("Hello")); // false
console.log(M.has("language")); // true
console.log(M.has("world")); // false
Beyond checking whether a key exists in a Map object, being able to read the value of the entry associated with that key is also very important. As such, every Map object initially has a get() method for this purpose.
When the get() method is called with a key for which no entry exists, it returns undefined.
const M = new Map(Object.entries({
language: "JavaScript",
hello: "world"
}));
console.log(M.get("hello")); // "world"
console.log(M.get("Hello")); // undefined
console.log(M.get("language")); // "JavaScript"
console.log(M.get("world")); // undefined
Although the get() method returns undefined for nonexistent keys, it should not be relied upon when checking for the existence of a key in a Map collection because it’s also possible for a key in the collection to have a value of undefined.
The most accurate way to determine the existence of a key in the collection is to use the has() method.
The ability to add, update, or remove one or more entries from a Map object is essential, and every Map object will have set(), delete(), and clear() methods.
The set() method takes a JavaScript value as its argument and will append that value to the end of the Set object, provided it isn’t already in the Set object. If the specified value is already in the Set object, it is ignored.
The add() method returns the same Set object with the added value, making it amenable to method chaining, or the process of invoking multiple add() calls at once.
The delete() method, on the other hand, will remove the entry associated with the specified key from the Map object — provided there is such an entry in the Map object. If an entry is actually removed from the Map object as a result of this delete operation, it returns true; otherwise it returns false.
It might be useful in some cases to completely remove all of the entries in a given Map object. While this can be achieved by making multiple delete() calls to the Map object, obviously it will make more sense if this is done in a single method call.
This is exactly what the clear() method does. Calling the clear() method empties the Map object and returns undefined.
// Convert object to map
const M = new Map(Object.entries({
language: "JavaScript"
}));
console.log(M.size); // 1
console.log(...M); // ["language", "JavaScript"]
// (1) Add and update some map entries
M.set("year", 1991);
M.set("language", "Python");
console.log(M.size); // 2
console.log(...M); // \["language", "Python"\] ["year", 1991]
// (2) Add or update several values at once (using chaining)
M.set("version", 3)
.set("year", 2000)
.set("version", "2.0");
console.log(M.size); // 3
console.log(...M); // \["language", "Python"\] ["year", 2000] ["version", "2.0"]
// Delete some entries from the map
console.log(M.delete("Year")); // false
console.log(M.delete("year")); // true
console.log(M.delete("year")); // false
console.log(M.delete("version")); // true
console.log(M.size); // 1
console.log(...M); // ["language", "JavaScript"]
// Empty the map
M.clear();
console.log(M.size); // 0
One other thing we might want to do with a Map object is view the keys, values, or entries that are in it.
You can loop through each entry in a Map object (in insertion order) using the for...of loop. This is because every iterable has a Symbol.iterator() method that returns its default iterator — which is responsible for producing the sequence of values for the loop.
Besides the for...of loop we looked at earlier, the same sequence of values returned by the default iterator is what the spread operator (...), the yield* statement, and destructuring assignment are based on.
We’ve already seen the entries() method, which returns an iterator for all the entries in a Map object with respect to their insertion order. As stated earlier, the iterator returned by the entries() method also serves as the default iterator of a Map object.
That said, the two for...of loops shown in the following code snippet are the same and will produce the exact same sequence of values:
const M = new Map([[1, 3], [3, 3], [4, 2], [2, 2]]);
// (a) Iteration using the default iterator ([Symbol.iterator])
for (const [key, value] of M) {
console.log(key, value);
}
// (b) Iteration using the `entries()` iterator
for (const [key, value] of M.entries()) {
console.log(key, value);
}
It is important to note that an iterable object can provide other iterators besides the default iterator provided by its [Symbol.iterator] method. This holds true for most inbuilt iterables in JavaScript, including Map objects.
In fact, every Map object originally has three methods that return iterators, namely:
entries()keys()values()The keys() method, as the name implies, returns an iterator that yields the keys associated with each entry of the Map object (in insertion order). The values() method returns an iterator that yields the values associated with each entry of the Map object.
The following code snippet demonstrates a couple of ways we can leverage the iterable behavior of a Map object to access the values or keys of each element in it.
const M = new Map([[1, 3], [3, 3], [4, 2], [2, 2]]);
// Using the spread operator (...) to pass values
// in the Map object as function arguments.
console.log(...M.values()); // 3 3 2 2
// Using the spread operator in building an array
// with the unique keys of the Map object.
const arr = [...M.keys()];
console.log(arr); // [1, 3, 4, 2]
console.log(arr[0]); // 1
console.log(arr[3]); // 2
console.log(arr.length); // 4
// Using destructuring assignment with a `Map` object
// to extract the first, second and remaining keys.
const [first, second, ...remainingKeys] = M.keys();
console.log(first); // 1
console.log(second); // 3
console.log(remainingKeys); // [4, 2]
console.log(remainingKeys.length); // 2
// Iteration using a for...of loop
// to read all the keys in the collection.
for (const key of M.keys()) {
console.log(key);
}
// 1
// 3
// 4
// 2
Map objects with the forEach() methodWe’ve been able to explore quite a number of ways in which we can iterate over a Map object. However, there remains one more very useful iteration method — the forEach() method.
Just as with arrays, the forEach() method of a Map object accepts a callback function as its first argument, which is triggered for each entry of the Map object. The forEach() method also accepts an optional second argument, which represents the this value that will be used when executing the callback function.
The forEach() callback function is called with three arguments for every entry of the Map object:
Map object itselfconst M = new Map([[1, 4], [3, 5], [4, 0], [2, 2]]);
M.forEach(function _callback(value, key, map) {
console.log([...map]);
const replacement = this[value];
if (replacement) map.set(key, replacement);
else if (Number.isInteger(value)) map.delete(key);
}, "hello");
console.log([...M]);
// [[1, 4], [3, 5], [4, 0], [2, 2]]
// [[1, "o"], [3, 5], [4, 0], [2, 2]]
// [[1, "o"], [4, 0], [2, 2]]
// [[1, "o"], [4, "h"], [2, 2]]
// [[1, "o"], [4, "h"], [2, "l"]]
To be clear, the forEach() method call in the previous code snippet results in the following _callback() calls:
_callback.call("hello", 1, 4, M);
_callback.call("hello", 3, 5, M);
_callback.call("hello", 4, 0, M);
_callback.call("hello", 2, 2, M);
Set object?A Set object is an ordered collection of unique JavaScript values.
For every Set object, there exists the following invariants:
Any valid JavaScript value can be contained in the collection — both primitive values and object references, including unseemly values like NaN and undefined.
Since we’ve already explored Map objects in the previous section, let’s look at how they compare with Set objects before we continue.
| Set objects | Map objects |
|---|---|
| one-dimensional collections: they store only unique values | two-dimensional collections: they store records as key/value pairs, and each key is unique in the collection |
| Both key and value point to the same value or reference for every entry | Both key and value point to the same value or reference for every entry |
| The default iterator ([Symbol.iterator]) of a Set object is the one returned from its values() method | The default iterator is obtained from the entries() method |
| set() and get() methods are not defined in the Set.prototype object; the Set.prototype object defines an add () method | The set() and get() methods are defined in the Set.prototype object |
As we progress in our exploration of JavaScript Set objects, we will find out more ways in which Set objects differ from Map objects and some ways in which they are similar.
Just as with Map objects, the only way to create a Set object is by invoking the global Set constructor function. The constructor function must be invoked with the new keyword — otherwise, a TypeError will be thrown. When the Set constructor function is invoked without arguments, an empty Set object of 0 size is returned.
// Throws a `TypeError` — when invoked without `new` keyword const throwTypeErrorSet = Set(); // Creates an empty `Set` object of 0 `size` const setA = new Set(); // Omitting the parentheses — when invoked without arguments // Also creates an empty `Set` object of 0 `size` const setB = new Set; console.log(setA.size); // 0 console.log(setB.size); // 0
The Set constructor function can also be invoked with an optional iterable argument. When specified, iterable must be a JavaScript object that properly implements the iterable protocol. Many inbuilt JavaScript objects implement this protocol — such as Array, String, and Map, as well as Set — which means that these are all valid objects and can be passed to the Set constructor function as the iterable argument.
If the iterable is the value null or undefined, then the effect is the same as calling the Set constructor function without any argument — an empty Set object of 0 size will be created. Otherwise, a TypeError will be thrown for any other iterable value that does not properly implement the iterable protocol.
Unlike with Map objects, creating a new Set object from another iterable object has the effect of de-duping, i.e., eliminating redundant duplicate values from the values yielded by the internal iterator of the iterable object. This is because of one important attribute of a Set object, which is that it must contain only distinct, discrete values.
// (1) Set from String // Set contains all the unique characters of the string const testString = "programming"; const uniqueChars = new Set(testString); console.log(testString.length); // 11 console.log(uniqueChars.size); // 8 console.log(...uniqueChars); // p r o g a m i n // (2) Set from Array // Set contains all the distinct elements of the array const integers = [1,1,1,3,3,4,3,2,4,2]; const distinctIntegers = new Set(integers); console.log(integers.length); // 10 console.log(distinctIntegers.size); // 4 console.log(...distinctIntegers); // 1 3 4 2 // (3) Set from Set // New set contains all the items of the original set // However, both sets are entirely different objects. // Think of it as creating a clone of a set. const setA = new Set([1,1,1,3,3,4,3,2,4,2]); const setB = new Set(setA); console.log(...setA); // 1 3 4 2 console.log(...setB); // 1 3 4 2 console.log(setA === setB); // false console.log(setA.size === setB.size); // true
Let’s take another shot at our sample problem from earlier and employ what we’ve learned so far about Set objects. This time, we will be creating a new Set object from the nums array, containing only distinct integers (no duplicates). We can then determine whether the nums array contains duplicates by comparing the size of the Set object with the length of the nums array.
Here is what the new solution looks like:
function hasDuplicates(nums) {
// Create a new set from `nums` containing only its distinct
// integers (i.e de-duplicate the `nums` array).
const distinct = new Set(nums);
// If the size of the distinct set matches the length of the
// nums array, then there are no duplicates, and vice-versa.
return distinct.size != nums.length;
}
In using a Set object, we have been able to implement a solution whose running time is guaranteed to grow linearly with the size of the input array, even though it will require some additional memory to perform. When it comes to storing unique items in memory, a set of items with duplicates will use less space than one without duplicates.
In other words, the worst case scenario in terms of memory usage happens when the set contains only unique items and no duplicates — in that case, the amount of space used matches the number of items.
Set object instance properties and methodsJust as with Map objects, the size property returns the number of values in a Set object at any instant. Again, the size property of the Set.prototype object is an accessor property, not a data property.
Set also only has a get accessor function and not a set accessor function — hence, it cannot be overridden by an assignment operation.
Whenever you access the size property of a Set object, its get accessor function will be invoked, and it will count and return the number of elements (values) that are currently in the Set object.
Every Set object will originally have a has() method that can be called to assert whether or not an element with a specified value is present in the Set object. Like with Map objects, the has() method returns a boolean value — true if the specified value is present, and false otherwise.
const uniqueChars = new Set("programming");
console.log(...uniqueChars); // p r o g a m i n
console.log(uniqueChars.has("p")); // true
console.log(uniqueChars.has("A")); // false
console.log(uniqueChars.has("a")); // true
console.log(uniqueChars.has("t")); // false
Since Set objects are one-dimensional (storing only unique values), it is impractical for them to have a get() method, unlike with Map objects. As a result, the Set.prototype object does not define a get() method.
It is very important to be able to add or remove one or more values from a Set object, and every Set object will initially have add(), delete(), and clear() methods.
The add() method takes a JavaScript value as its argument, and will append that value to the end of the Set object, provided that it isn’t already in the Set object. If the specified value is already in the Set object, it is ignored.
The add() method returns the same Set object, with the added value, which makes it amenable to method chaining, or the familiar process of invoking multiple add() calls at once.
Just like with Map objects, the delete() method of a Set object will remove the element associated with the specified value from the Set object, provided that such an element is present in the Set object. If an element is actually removed from the Set object as a result of this delete operation, it returns true; otherwise it returns false.
Also, a call to the clear() method empties the Set object and returns undefined.
// Create new set of integers const integers = new Set([1,1,1,3,3,4,3,2,4,2]); console.log(integers.size); // 4 console.log(...integers); // 1 3 4 2 // Add some values to the set integers.add(5); integers.add(1); console.log(integers.size); // 5 console.log(...integers); // 1 3 4 2 5 // Add several values at once (using chaining) integers.add(7).add(2).add(9); console.log(integers.size); // 7 console.log(...integers); // 1 3 4 2 5 7 9 // Delete some values from the set console.log(integers.delete(3)); // true console.log(integers.delete(8)); // false console.log(integers.delete(3)); // false console.log(integers.delete(1)); // true console.log(integers.size); // 5 console.log(...integers); // 4 2 5 7 9 // Empty the set integers.clear(); console.log(integers.size); // 0
Now that we’ve learned a few more things we can do with Set objects, let’s return to our previous solution to our original sample problem and see if we can optimize it even further. (As you might have rightly guessed, we can.)
A careful examination of our previous solution will show that it’s doing a little too much. It always considers every integer in the input array, adding them to the Set object (just like using the add() method multiple times) and then checking its size, which counts and returns the number of elements in the Set object by going through each element.
The problem with this solution is that it isn’t conservative. It is very possible that a duplicate integer might be found by considering the first few integers in the array, and so the act of considering the remaining integers in the array becomes redundant.
To optimize this solution, we can decide to be lazy about adding integers to the Set object, and only continue as long as we haven’t encountered an integer that has already been added to the Set object.
Here is what the optimized solution looks like:
function hasDuplicates(nums) {
// 1. Create an empty set to hold distinct integers
const distinct = new Set();
// 2. Loop through the integers until a duplicate is found
for (const int of nums) {
// 2a. If a duplicate is found, return immediately
if (distinct.has(int)) return true;
// 2b. Otherwise, add the integer to the distinct set
distinct.add(int);
}
// 3. If it ever gets here, no duplicate was found
return false;
}
It is often necessary to have a view into the values that are contained in a Set object. This is very attainable with arrays or indexed collections — hence, we can easily access the element of an array (arr), at some index (i), using the property access bracket notation (arr[i]).
Unfortunately, this kind of element access is not directly possible with Set() objects because Set objects are keyed collections.
However, just like with arrays and other iterables, you can loop through the values for each element in a Set object (in insertion order) using the for...of loop, or you could use the sequence of values it produces with the spread operator (...), the yield* statement, or destructuring assignment.
The following code snippet demonstrates a couple of ways we can leverage the iterable behavior of a Set object to access the values of each element in it.
const integers = new Set([1,1,1,3,3,4,3,2,4,2]);
// Using the spread operator (...) to pass values
// in the Set object as function arguments.
console.log(...integers); // 1 3 4 2
// Using the spread operator in building an array
// with the unique values from the Set object.
const arr = [...integers];
console.log(arr); // [1, 3, 4, 2]
console.log(arr[0]); // 1
console.log(arr[3]); // 2
console.log(arr.length); // 4
// Using destructuring assignment with a `Set` object
const [first, second, ...remainingIntegers] = integers;
console.log(first); // 1
console.log(second); // 3
console.log(remainingIntegers); // [4, 2]
console.log(remainingIntegers.length); // 2
// Iteration using a `for...of` loop
for (const integer of integers) {
console.log(integer);
}
// 1
// 3
// 4
// 2
Just like with Map objects, every Set object originally has three methods that return iterators — values(), keys(), and entries().
The values() method, as the name implies, returns a new iterator that yields the values for each element in the Set object (in insertion order). The iterator returned by the values() method yields the exact same sequence of values as the default iterator returned by the [Symbol.iterator] method.
For iteration purposes, the keys() method of a Set object behaves exactly like the values() method, and they can be used interchangeably. In fact, the values, keys, and [Symbol.iterator] properties of a Set object all point to the same value (function) initially. Hence, the following for...of loops will log the exact same sequence of values.
const integers = new Set([1,1,1,3,3,4,3,2,4,2]);
// (a) Iteration using the default iterator (`[Symbol.iterator]`)
for (const integer of integers) {
console.log(integer);
}
// (b) Iteration using the `values()` iterator
for (const integer of integers.values()) {
console.log(integer);
}
// (c) Iteration using the `keys()` iterator
for (const integer of integers.keys()) {
console.log(integer);
}
Some basic set operations can be implemented by iterating over one or more Set objects. For example, the following code snippet shows how to implement the union and intersection set operations.
function union(setA, setB) {
const setUnion = new Set(setA);
for (const value of setB) {
setUnion.add(value);
}
return setUnion;
}
function intersection(setA, setB) {
const setIntersection = new Set();
for (const value of setB) {
if (setA.has(value)) {
setIntersection.add(value);
}
}
return setIntersection;
}
Just as with Map objects, Set objects also have a forEach() method with a similar call signature. However, to account for the one-dimensional nature of Set objects, the forEach() callback function is called with three arguments:
Set object itselfconst S = new Set([1,1,1,3,3,4,3,2,4,2]);
S.forEach(function _callback(value, _, set) {
console.log([...set]);
const replacement = this[value];
if (replacement) set.add(${value}${replacement});
if (Number.isInteger(value)) set.delete(value);
}, "hello");
// [1, 3, 4, 2]
// [3, 4, 2, '1e']
// [4, 2, '1e', '3l']
// [2, '1e', '3l', '4o']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
console.log(...S); // 1e 3l 4o 2l
To be clear, the forEach() method call in the previous code snippet results in the following _callback() calls:
_callback.call("hello", 1, 1, S);
_callback.call("hello", 3, 3, S);
_callback.call("hello", 4, 4, S);
_callback.call("hello", 2, 2, S);
_callback.call("hello", '1e', '1e', S);
_callback.call("hello", '3l', '3l', S);
_callback.call("hello", '4o', '4o', S);
_callback.call("hello", '2l', '2l', S);
undefined — what does it mean?When the Set constructor function is called without any argument, you already know that it creates an empty Set object. The same, however, does not hold true for the add() method.
When the add() method of a Set object is called without any argument, it actually adds an element to the collection with a value of undefined, if it does not already exist.
In other words, for a given Set object S, S.add() is exactly the same as S.add(undefined). This is what I’d like to refer to as an accidental undefined — because it might not be intended.
You might have already inferred the behavior of the has() and delete() methods when they’re called without any argument. As with the add() method, calling these methods without any argument is exactly the same as calling them with undefined as the first argument. Hence, for a given Set object S, S.has() checks whether undefined exists as a value in the Set object, while S.delete() removes the value undefined from the collection, if it exists.
// Creates an empty set object
const S = new Set();
// Add some items to the set object
S.add(5);
S.add("hello"); console.log(...S); // 5 'hello'
// Adds undefined to the set object
S.add(); console.log(...S); // 5 'hello' undefined
console.log(S.has(5)); // true
console.log(S.has("world")); // false
// Logs `true` because `undefined` exists in the set
console.log(S.has()); // true
// Logs `true` because `undefined` was removed from the set
console.log(S.delete()); // true
// Logs `false` because `undefined` does not exist in the set
console.log(S.has()); // false
That said, always be sure to explicitly call the add(), delete(), and has() methods of a Set object with at least one argument to avoid dealing with an accidental undefined value.
Set objectsBefore we finish this section on JavaScript Set objects, let’s see how we can solve a modified version of the sample problem from before, using all we’ve learned so far.
đź’ˇ Contains Duplicates (2) Given an array of integers
nums, return the number of elements that appear at least twice in the array, and return0if every element is distinct.
Pause for a moment and try solving this problem on your own, before you proceed. The solution could be a little tricky — how can you ensure a duplicate integer is not counted more than once?
Now, here is a working solution to the problem:
function countDuplicates(nums) {
// Create an empty set for distinct integers
// (i.e integers appearing only once)
const distinct = new Set();
// Create an empty set for duplicate integers
const duplicates = new Set();
// Create a variable to keep track of the duplicates count
let count = 0;
// Loop through the integers while counting duplicates
for (const int of nums) {
// If duplicate integer is found (it has already been counted),
// continue with the iteration to the next integer.
if (duplicates.has(int)) continue;
if (distinct.delete(int)) {
// If integer was successfully deleted from the `distinct` set,
// that means it has been seen once before. Hence add it, to
// the `duplicates` set and increment `count`.
duplicates.add(int);
count++;
} else {
// Integer is being seen for the first time and should be added
// to the `distinct` set.
distinct.add(int);
}
}
// Finally, return the duplicates count
return count;
}
Map or set?So far, we have been able to explore JavaScript Map and Set objects in detail. But in addition to that, we also need to be able to determine when it is sufficient to use one instead of the other in solving problems.
Earlier on, we saw that Set objects are one-dimensional collections, whereas Map objects are two-dimensional. That could serve as a cue in determining which one is best suited for a particular problem.
In other words, a Map object should be used over a Set object in cases where additional information is needed aside from just the key. Most times, that additional information is required to make decisions or to compute the final output of the program.
To further demonstrate this, let’s consider another popular problem.
đź’ˇTwo Sum Given an array of integers and a specific target, return
trueif two numbers exist in the array that add up to the target, andfalseotherwise.
If the array were to be sorted, then it would be possible to come up with a linear time solution to this problem without any need for auxiliary space. But since there is a possibility that the array is not already sorted, we need to use a Set object to provide some auxiliary space where we can solve the problem in linear time without taking on the expensive task of sorting the array first.
function twoSum(nums, target) {
// 1. Create an empty set for complements
// (i.e complement = target - num)
const complements = new Set();
// 2. Loop through integers until a complement is found
for (const num of nums) {
// 2a. If a complement is found, return immediately
if (complements.has(target - num)) return true;
// 2b. Otherwise, add the integer to the complements set
complements.add(num);
}
// 3. If it ever gets here, no complement was found
return false;
}
Here, we are required to return true if there are two numbers that sum up to the specified target, and false otherwise. As such, we are only interested in the numbers themselves, which is why we only need to use one Set object to solve the problem.
Now, let’s instead say we modify the problem to return the array indices of the two numbers. We would be better off using a Map object. That’s because, in addition to the numbers themselves, we are now also interested in their corresponding indices in the array — both of which cannot be contained in a singular Set object.
function twoSum(nums, target) {
// 1. Create an empty map for integers against indices
// (i.e Map<integer, index>)
const indices = new Map();
// 2. Loop through integers until a complement is found
for (let i = 0, len = nums.length; i < len; i++) {
// 2a. Compute the complement of the current integer
const complement = target - nums[i];
// 2b. If the complement already exists in the map,
// get the complement index from the indices map and
// return early ([complement index, current index])
if (indices.has(complement)) {
return [indices.get(complement), i];
}
// 2c. Otherwise, add the current integer and index
// to the indices map
indices.set(nums[i], i);
}
// 3. If it ever gets here, no complement was found
return null;
}
Map and Set usesMap and Set objects can be very useful when modeling compound data structures to solve certain kinds of problems.
In general, whenever you need to be able to look up or check for the existence of an item with an average access time that is sublinear on the number of available items (approximately constant time), you should consider using a Set or Map object.
Map objectsWhen modeling data structures for the purpose of caching data, a Map object can be used as a lookup table to check for the existence of a key in the cache before performing get() or put() operations.
Usually, cache implementations include some kind of strategy for removing items from the cache in order to free up space — the most popular cache eviction strategies being: least frequently used (LFU) and least recently used (LRU).
Consider the get() operation of an LRU cache, for example: the expectation is to be able to fetch a record from the cache using its cache key in approximately constant time, and in the process, the record gets ranked as the most recently used record because it is the most recently accessed.
In order to meet the above stated expectation, a fast lookup of the cache key is required — and that is where a Map object or any other form of hash table shines. To maintain a proper ranking of recently accessed records, a priority queue can be used.
However, most implementations use a doubly-linked list instead, since it is capable of both removing the record from its current position in the list and re-inserting it to the head position of the list, all in constant time.
A minimalist implementation blueprint of a typical LRU cache could look somewhat like this (the full implementation details have been omitted for brevity):
interface ICache<K, V> {
get: (key: K) => V;
put: (key: K, data: V) => void;
}
class LRUCache<K, V> implements ICache<K, V> {
/**
* A DLL is used to maintain the order of the items
* in the cache according to how recently they were
* used (accessed or added).
*
* Using a DLL makes it possible to remove an item
* from any position in the list (in constant time).
*/
protected list = new DoublyLinkedList<V>();
/**
* A Map object is used as a lookup table to check
* for the existence of a key in the cache with an
* average access time that is sublinear on the
* number of cache items (approximately constant
* time).
*/
protected table = new Map<K, V>();
/**
* @param size {number} The number of items that
* can be stored in the cache.
*/
constructor(protected size: number) {}
get(key: K): V {}
put(key: K, data: V): void {}
}
Most connectivity problems are better solved when the problem data is represented as a graph, using either of two forms of graph representation:
For most problems, an adjacency list representation should suffice — and for that, Map and Set objects can be used.
Most adjacency list implementations use arrays and/or linked lists, but it is also possible to use Map and Set objects. The Map object stores each vertex in the graph as its keys, with their corresponding list of neighboring vertices in Set objects as its values.
A typical implementation of an undirected graph represented as an Adjacency List (using Map and Set objects) should look somewhat like this:
interface IGraph<V> {
addVertex: (vertex: V) => void;
addEdge: (fromVertex: V, toVertex: V) => void;
removeVertex: (vertex: V) => void;
removeEdge: (fromVertex: V, toVertex: V) => void;
}
class UndirectedGraph<V> implements IGraph<V> {
/**
* A Map object is used to map each vertex in the
* graph to a set of vertices that are connected
* to it.
*/
protected list = new Map<V, Set<V>>();
addVertex(vertex: V): void {
if (!this.list.has(vertex)) {
// An array can be used to represent the set
// of vertices — but in this implementation,
// a Set object is used instead.
this.list.set(vertex, new Set<V>());
}
}
addEdge(fromVertex: V, toVertex: V): void {
this.addVertex(fromVertex);
this.addVertex(toVertex);
(this.list.get(fromVertex) as Set<V>).add(toVertex);
(this.list.get(toVertex) as Set<V>).add(fromVertex);
}
removeVertex(vertex: V): void {
if (this.list.has(vertex)) {
for (const toVertex of this.list.get(vertex) as Set<V>) {
this.removeEdge(vertex, toVertex);
}
this.list.delete(vertex);
}
}
removeEdge(fromVertex: V, toVertex: V): void {
if (this.list.has(fromVertex) && this.list.has(toVertex)) {
(this.list.get(fromVertex) as Set<V>).delete(toVertex);
(this.list.get(toVertex) as Set<V>).delete(fromVertex);
}
}
}
A niche of connectivity problems can be solved using special data structures called disjoint-sets. A disjoint-set is used to maintain a set of elements (nodes) that are partitioned into a number of non-overlapping (disjointed) subsets, also known as connected components.
Disjoint-sets are structured in such a way as to efficiently perform two operations, namely:
find: checks for the subset an element or node belongs tounion: merges two subsets into a single subset; can also be used for detecting cycles in undirected graphsThe following Disjoint-Set implementation uses a Map object to maintain its non-overlapping subsets (the implementation is detailed):
interface IDisjointSet<T> {
find: (node: T) => T;
union: (nodeA: T, nodeB: T) => void;
}
class DisjointSet<T> implements IDisjointSet<T> {
/**
* A Map object is used to link each node to the
* root of its corresponding connected component
* subset (using a disjoint-set data structure).
*/
protected subsets = new Map<T, T | number>();
addNode(node: T): void {
if (!this.subsets.has(node)) {
this.subsets.set(node, -1);
}
}
find(node: T): T {
let root = node;
while (true) {
const parent = this.subsets.get(root) as T;
if (!this.subsets.has(parent)) {
if (node !== root) {
this.subsets.set(node, root);
}
return root;
}
root = parent;
}
}
union(nodeA: T, nodeB: T): void {
const rootA = this.find(nodeA);
const rootB = this.find(nodeB);
const sizeA = this.subsets.get(rootA) as number;
const sizeB = this.subsets.get(rootB) as number;
const sizeAB = sizeA + sizeB;
if (sizeA < sizeB) {
this.subsets.set(rootB, rootA);
this.subsets.set(rootA, sizeAB);
} else {
this.subsets.set(rootA, rootB);
this.subsets.set(rootB, sizeAB);
}
}
isConnected(nodeA: T, nodeB: T): boolean {
return this.find(nodeA) === this.find(nodeB);
}
}
Maps and sets in JavaScript can come in very handy for quite a number of applications and when trying to solve a number of problems efficiently — especially when efficient lookups are required. In fact, they are specialized hash table implementations for JavaScript, akin to the HashMap and HashSet types in Java — albeit, with some subtle differences.
For safe garbage collection guarantees, consider using the even more restrictive WeakMap and WeakSet keyed collections.
Debugging code is always a tedious task. But the more you understand your errors, the easier it is to fix them.
LogRocket allows you to understand these errors in new and unique ways. Our frontend monitoring solution tracks user engagement with your JavaScript frontends to give you the ability to see exactly what the user did that led to an error.
LogRocket records console logs, page load times, stack traces, slow network requests/responses with headers + bodies, browser metadata, and custom logs. Understanding the impact of your JavaScript code will never be easier!
Would you be interested in joining LogRocket's developer community?
Join LogRocket’s Content Advisory Board. You’ll help inform the type of content we create and get access to exclusive meetups, social accreditation, and swag.
Sign up now
Image component to optimize imagesExplore automatic image optimization using Next Image, the built-in image optimization solution for Next.js.
Discover how to integrate frontend AI tools for faster, more efficient development without sacrificing quality.
Is React Hook Form still worth using? In this guide, you will learn the differences, advantages, and best use cases of React Hook Form.
Walk through the process of deploying a Create React App project to GitHub Pages, customizing your domain, and automating deployments with GitHub Actions.
