September 19, 2020

Thoughts on Array vs Set vs Map using Javascript

Array, map, and set: 3 of the most important data structures in Javascript and on the surface, these 3 look more similar than different in terms of what they do and what they are used for. But when you look closely at each data structure, as we are going to do in this article, you will see that each data structure has different use cases that they are optimal for. Without scrambling out a solution using many familiar arrays for every problem you come across, understanding the differences and use cases of each of these data structures will give you the ability to come up with optimal solutions by using the best data structure for that particular case.

First, let’s see what each of these data structures is.

Arrays

Arrays are a data structure that stores data of any type in a list-like Javascript object. You can create an array by explicitly declaring it as in the example below.

let arr = [1, 2, 'fruit', { id: 1, name: 'charlie' }, ['a', 'b']]

Each item in an array has an index starting from 0. You can access each item using its index.

arr[0] // 1
arr[4] // ['a', 'b']

You can change the value of an item at a certain index.

arr[3] = 9 // arr = [1, 2, 'fruit', 9, ['a', 'b']]

Get the index of the array item by the value

arr.indexOf('fruit') // 2

You can add items to an empty or non-empty array using either of the following methods.

//add item to the end of the array
arr.push('vegetable') // arr = [1, 2, 'fruit', 9, ['a', 'b'], 'vegetable']
arr[6] = 2 // arr = [1, 2, "fruit", 9, ['a', 'b'], 'vegetable', 2]

Map

Maps are objects that store items as key-value pairs. The keys can be of any data type as long as each key is unique. Values can also be of any data type, but not necessarily unique. To create a new map object, you need to call its constructor.

let mapObj = new Map()

Use Map.prototype.set(key, value) to add a new key-value pair to the map object.

//mapObj.set(key, value)
mapObj.set(1, "cat")
mapObj.set('name', 'smith')

You can access a value stored in the map using its key and Map.prototype.get(key) method.

//mapObj.get(key)
mapObj.get('name') // 'smith'

You can use the previous set method to change the value of a stored item.

mapObj.set(1, 'dog')
mapObj.get(1)  // 'dog'

Set

Sets are objects that store a collection of values. Each value stored in a set is unique and can be of any data type. A set is created using the set constructor.

let setObj = new Set()

Adding values to a set is done using Set.prototype.add(value) method.

setObj.add(1) //Set [1]
setObj.add(5) //Set [1, 5]
setObj.add(5) //Set [1, 5]
setObj.add('nevermind') //Set [1, 5, 'nevermind']
setObj.add([1, 2, 4]) //Set [1, 5, 'nevermind', [1,2, 4]]

Now you have had a proper introduction to each of the 3 data structures, let’s see how array vs map vs set fair up in different scenarios.

Arrays are Not Dense Objects

Consider the following example.


let arr = [1, 2, 5, 3]
arr[6] = 10 // arr = [1, 2, 5, 3, empty, empty, 10]

In the above scenario, even though the final index of the initial arr object is 3, assigning a value to index 6 can be implemented without throwing an error. Two indices between 3 and 6, which were not assigned a value, appear as empty in the resulting array. This is because arrays are not necessarily dense. You can increase the length of an array by a value assignment like in the above case, while still having empty slots in between the first and final indices.

let arr = [1, 2, 5, 3]
arr.length // 4
arr[100] = 9
arr.length // 101

Whether the array is kept dense or not is ultimately the choice of the programmer and the use case that it is being used for.

You can consider both sets and maps to be dense by default because their structures don’t allow a scenario like above to happen. Their sizes are equal to the number of items stored in the objects.

let mapObj = new Map()
mapObj.set(1, 1)
mapObj.set(2, 4)
mapObj.set(3, 7)
mapObj.size // 3

let setObj = new Set()
setObj.add(1)
setObj.add(3)
setObj.size // 2

Retrieving Single Items

While both maps and arrays provide a method to directly retrieve single items using key, index, or value, such a method is not available for sets.

//retrieve value of array item using array index
arr[0] //1 
arr[2] //5
//retrive index of array item using value
arr.indexOf(5) //2
arr.indexOf(3) //3

//retrieve value of map item using key
mapObj.get(3) //7
mapObj.get(2) //4

//Sets??

The only way to retrieve the values in a set is by iterating through it. For use cases that require direct and easy access to its values, sets are not a good fit.

Using Arrays to Create Maps and Sets

Arrays can be used in creating maps and sets. Constructors of both Map and Set classes accept Iterable objects (like arrays) as arguments.

First, let’s see how to create a set using an array.

let setObj = new Set([1, 3, 4, 6, 2, 3, 1]) // Set [1, 3, 4, 6]

To create a Map, we need a 2-dimensional array (array of arrays). If each array in the 2nd dimension is of length 2, the value at index 0 of each array becomes the key and the value at index 1 becomes the value. If they are not, a new map is still created, with some odd key-value pairs. If the values at two zero indices in the 2nd level arrays are equal, the array that comes 2nd replaces the value stored under that key.


let mapObj = new Map([1, 2], [3, 4], [5, 6])
mapObj.length // 3
mapObj.get(1) //2
mapObj.get(5) //6

new Map([[1, 2], [6], [3, 5, 6], []]) // Map {1=>2, 6=>undefined, 3=>5, undefined=>undefined}
new Map([[1, 2], [3, 5], [5, 0], [3, 90]]) // Map {1=>2, 3=>90, 5=>0}

Storing Duplicates

By default, sets do not store duplicate values. Since each key in a map is unique, it can’t store duplicate keys as well. However, arrays are prone to storing duplicates. Of course, it depends on the use case whether storing duplicates is a good thing or a bad thing, and that should help you decide which data structure to use for the occasion.

Iteration Using for…in and forEach

Arrays, maps, and sets can be iterated using for…of loops. In arrays and sets, the loop iterates over the values stored, and in maps, the loop iterates over each key-value pair. In sets and maps, the iteration happens in the insertion order. In arrays, iteration happens in the order of indices.

let arr = [1, 45, 21, 9]
let mapObj = new Map([1, 2], [3, 4], [5, 6])
let setObj = new Set([1, 3, 4, 6, 2])

for (let value of arr) {
    console.log(value)
}
//1, 45, 21, 9

for (let value of setObj) {
    console.log(value)
}
//1, 3, 4, 6, 2

for (let [key, value] of mapObj) {
    console.log(`${key}=>${value}`)
}
//1=>2, 3=>4, 5=>6

You can also iterate over only keys or values of a map with a for…of loop.

for (let key of mapObj.keys()) {
    console.log(key)
}
//1, 3, 5

for (let value of mapObj.values()) {
    console.log(value)
}
//2, 4, 6
for (let [key, value] of mapObj.entries()) {
    console.log(`${key}=>${value}`)
}
//1=>2, 3=>4, 5=>6

forEach can also be used to iterate over these 3 data structures.


arr.forEach((value, index) => {
    console.log(`${index}:${value}`)
})
//0:1, 1:45, 2:21, 3:9

setObj.forEach(value => {
    console.log(value)
})
//1, 3, 4, 6, 2

mapObj.forEach((key, value)=> {
    console.log(`${key}=>${value}`)
})
//1=>2, 3=>4, 5=>6

Removing Elements

Arrays, maps, and sets have methods to remove stored items from the object. Method of removing is somewhat similar in maps and sets


//mapObj.delete(key)
mapObj.delete(3) // mapObj = Map {1=>2, 5=>6}

//setObj.delete(value)
setObj.delete(6) // setObj = Set [1, 3, 4, 2]

Arrays use Array.prototype.splice() method to remove items from an array

//using array index
arr.splice(2, 1) //arr = [1, 45, 9]
arr.splice(0, 2) //arr = [9]

//using item value
arr.splice(arr.indexOf(9), 1) //arr = []

In the above code, the first parameter of the splice method is the index of the position to start removing items. The second parameter says how many items from the start should be removed.

Removing an item from an array using the item value is quite slow compared to the delete operation of set or map.

Use of NaN

In Javascript, NaN !== NaN is a true statement. However, in sets and maps, the algorithms used to determine value equality and key equality, respectively, considers NaN to be the same as NaN (sounds weird, I know). Because of this, NaN can be used as a unique key in maps and a unique value in sets (where the uniqueness of keys or values are checked). Arrays can store NaN as a value without equality considerations because arrays’ values need not be unique.

Conclusion

Now you know what arrays, maps, and sets are and their differences, it’s in your hand to use this knowledge appropriately when programming. When you encounter a problem that requires the use of a data structure, take a moment to think which of these 3, or any other data structure you know, best suits the task at hand. It will make your program faster, cleaner, and more optimal than before. 

Leave a Reply

Your email address will not be published. Required fields are marked *