Maps and Sets in JavaScript

What are computers? Depending on the context or requirements, this question can be answered differently. But in general, for me and maybe for most other programmers out there, to be able to store, operate on, and retrieve data is what computers are all about. We use programming languages to define what and how these processes need to be done to achieve a desirable outcome. As such, in any language, the more one can master this, the more efficiently they can build a system around it. In this article, we will focus on the "storing and retrieving data" aspect of computers and on what JavaScript provides to handle it.

When we write a program, we will most likely have data that we want to store. Sometimes it may be a single value that we can store in a simple variable. But sometimes we might need to store multiple values in a specific manner. To address these needs, we use data structures. We leverage existing primitive types to define some complex data types that can store data the way we want. Two of the most common implementations include arrays and objects.

An array is a simple data structure that stores values in a continuous fashion accessible by an 'index', which defines the position of that value. Objects are used to store key-value pairs, where keys can only be strings and symbols (mostly strings). Each key maps to a value, and keys are all unique. With objects, we can make any type of data type possible in general, but this kind of storage has a limitation. To understand the limitation, we need to understand the idea of time and space complexity.

Time and Space Complexity

Since we have some data, we will surely need to perform some operations on this data. Like we might want to add, delete or modify our data store. For storing the data, we will require some space, and to perform an operation, some time will be needed. Now 'complexity' just means how much the time needed or space needed depends on the size of the data store.

For example, say your array has 1 element, and it takes x time to add and takes up y space. Now, if you have 4 elements, adding them takes 16x time and takes up 4y space. This means that your time complexity for addition is O(n^2) and Space Complexity is O(n), where n is the size of the input. This can be basically thought of as a ratio. n^2 indicates that it takes 16 times more time for 4 elements than a single element, meaning the relation between the number of elements and time is square. Also, we do not consider constants as we are more interested in just approximates and worst-case analysis.

The Problem with Traditional Data Storing Structures

Now, say you want to store 100 elements in an array randomly. It will take 100x space (considering each element takes the same amount of space), and addition at the end takes the same time no matter how many elements. But what if you need to add an element in the middle or delete an element in the middle? The time this will take will depend on the number of elements after that position, because they will need to be shifted. Similarly, if we want to check if an element exists, it will also require, in many cases, an entire array scan. But that would be too slow in many use cases. Can't we have any other options?

The Solution

There are multiple solutions to this problem, but the most common ones used, not only in JavaScript but most other languages, are Sets and Maps. These internally use a concept called hashing to provide access, deletion, addition and other such time-consuming operations in constant time. Meaning - irrespective of the number of elements stored. This optimization is not gaureanteed but the optimal behaviour is general enough to be classified as average case.

Maps

The map data structure is similar to the hash-map or dictionary in other languages and holds key-value pairs. The keys can be anything (as long as they can be hashed), and the order of insertion is preserved as well. But the question arises - objects are also the same. So why do we need maps? This is because objects only allow for strings or symbols as keys. In objects, addition and deletion might not be as fast as maps. Hence, it is always preferred to use maps over objects in cases where fast addition or deletion is required.

A map can be created in JavaScript using the Map class.

const myMap = new Map();

And we have multiple functions for performing map operations.

set(key, val) : Adds or updates an element with a specified key and value.

get(key) : Returns the value associated with the specified key.

has(key) : Returns a boolean indicating whether an element with the specified key exists.

delete(key) : Removes the element with the specified key.

clear(): Removes all elements from the Map.

size: Returns the number of key-value pairs in the Map.

The access, addition and deletion of values is extremely fast in maps, and hence they are a very frequently used as lookup tables and clever time optimizations in DSA problems.

Sets

Unlike maps, which store a key-value pair, sets are meant to store just values without any index or key to point to the value. The implementation of sets is very similar to mathematics's set . There can be no repeated values, and it also supports native mathematical set operations. Lookup, insertion and deletion all take constant time. It is frequently used to keep track of elements that have already been processed and is yet another important data structure to master for solving DSA problems efficiently.

Frequently used set operations on sets :

Set.add() :

Adds the new element with a specified value at the end of the Set object.

Set.delete() :

deletes an element with the specified value from the Set object.

Set.clear() :

The Set clear() method in JavaScript is used for the removal of all the elements from a set and making it empty.

Set.has() :

Returns true if the specified value is present in the Set object.

Difference between Objects and Maps

While objects and maps look pretty similar as data structures that store key-value pairs, their internal implementation, functionalities provided and use cases set them apart clearly. As such, we need to understand what exactly the differences are to be able to utilise them efficiently.

Feature	Objects => {}	Map => new Map()
Key Types	Limited to strings and symbols	Can be any value, including functions,objets and primitives
Key Order	No Stricy Order is maintained during insertion	Order of insertion is guaranteed to be maintained
Size	The Size has to be manually calculated using roundabout methods.	It has an innate size field to tell the number of elements present.
Iterablily	Objects are not directly iterable and need to be converted into an iterable to be traversed.	Are iterable by default and natively support for of loop of forEach() method.
Keys	Can have key conflicts with prototype keys. Not ideal as a lookup table, which needs addition or deletion.	Keys are always unque and any forceful insertion causes the already existing value for the key to be overwritten.

The above-listed are the most important differences to consider between maps and objects. Maps are made for dynamic data handling, while objects are meant for designating properties and behaviour to data. Objects are best used for data representation rather than data storage or retrieval.

Difference Between Sets and Arrays

Features	Sets => new Set()	Arrays => []
Duplicates	The most important property of a set to remember is that it never stores duplicates	Arrays can have multiple copies of the same element and many similar elements.
Ordering	Internal ordering is dependent on the order of insertion, but it is not guaranteed to be maintained.	Elements are ordered based on index and are placed in a continuous fashion.
Access	There is no direct way to get an element. We can use the has() method to check for existence or iterate over the set to get all values.	Elements can be accessed by indices, and we can iterate over the array to get all values.
Performance	For the existence check of a value, the time Complexity is O(1).	Element access from index is very fast, but the existence check takes linear time.

Sets are mostly used for storing the existence of a value or for mathematical set operations. Arrays are used for storing data in an indexed and continuous fashion. Arrays offer a variety of features like sort, filter, and map, which are used to perform data or sequence modifications.

Sets and Maps Use Cases

Sets and Maps have different use cases:

Maps: Maps are used when a key (any type of data format) needs to be looked up fast and return an associated value. It can be thought of as a dictionary. It is used for frequent addition or deletion and maintaining the order of insertion, along with fast lookups.

Sets: Sets are used when we need quick lookups for existence checks, mathematical set operations and for quickly removing duplicates (better ways exist, but this too is not bad).

Understanding the different use cases and requirements, and implementing maps and sets or any other programming feature, is what makes the difference between a coder and a programmer. Anyone can code, but few can think of what to code. And to be that thinker, we need to be the one who understands what 'fits' here rather than what 'feels good' here.