1st November 2018 • 5 min read

JavaScript’s Maps For Better Performance

Seif Ghezala

This article is not intended to explore the API of the Map object in details. If you’re looking for such a source, please check out MDN.

In general, the Map data structure is useful when we want to retrieve/add/delete values through a set of unique keys.

One of the characteristics that make JavaScript Map data structure unique compared to its implementation in other languages, is the fact that it remembers the insertion order of its keys.

In this article, we will take a close look at what makes this specific feature very useful and why you should use Maps over other data structures in some cases. To do so, we will look at a concrete example by building a shopping basket.

Problem: Building Shopping Basket

Initially, we have a list of shop items and an empty shopping basket as follows:

json
1// initial shop_items2shop_items: [3    { value: "👕", stock: 10 },4    { value: "👖", stock: 10 },5    { value: "👞", stock: 10}6]7
8// initial empty shopping_basket9shopping_basket: empty

We want to make it possible to add items to our shopping basket and to put them back.

Adding an item to the shopping basket should:

  • Decrement the stock for that particular item.
  • If the item was never added to the basket, it should add it to the basket with a count of 1
  • If the item already exists in the basket, it should increment its count in the basket.

Putting back an item to the shop items should:

  • Increment the stock for that particular item.
  • If the item has a count bigger than 1 in the basket, it should decrement its count.
  • If the item has a count of 1 in the basket, it should remove it from the basket.

Extra requirement: we need to make sure that items in the shopping basket are kept in the order they were inserted.

Solution Using Arrays

First, let’s see how we can solve it using the shopping basket as an array.

Initially, we have the following:

javascript
1// initial shop_items2let shop_items = [3  { value: "👕", stock: 10 },4  { value: "👖", stock: 10 },5  { value: "👞", stock: 10 },6];7
8// initial empty shopping_basket9let shopping_basket = [];

Let’s then create a function addToBasket that adds a specific item from the shop items to the shopping basket:

javascript
1/**2 * Adds an item from the shop items to the shopping basket3 * @param {string} value: value of the item to add4 */5function addToBasket(value) {6  // decrement the stock of the corresponding shop item7  const shop_item_idx = shop_items.findIndex((item) => item.value === value);8  shop_items[shop_item_idx].stock--;9
10  // update basket11  const existingIndex = shopping_basket.findIndex(12    (item) => item.value === value13  );14  // (1) if the item was never added to the basket, it should be added to15  // the basket with a count of 116  // (2) othwerwise, its count should be incremented17  if (existingIndex === -1) {18    shopping_basket.push({ value, count: 1 });19  } else {20    shopping_basket[existingIndex].count++;21  }22}

Let’s also add a removeFromBasket function to remove put back an item from the shopping basket to the shop items list:

javascript
1/**2 * Puts back an item from the shopping basket to the shop items3 * @param {string} value: value of the item to add4 */5function removeFromBasket(value) {6  // increment the stock of the corresponding shop item7  const shop_item_idx = shop_items.findIndex((item) => item.value === value);8  shop_items[shop_item_idx].stock++;9
10  // update basket11  const existingIndex = shopping_basket.findIndex(12    (item) => item.value === value13  );14  // (1) if the item has a count bigger than 1 in the basket,15  // its count should be decrement16  // (2) othwerwise, it should be removed from the basket17  if (shopping_basket[existingIndex].count > 1) {18    shopping_basket[existingIndex].count--;19  } else {20    shopping_basket[existingIndex].splice(existingIndex);21  }22}

Testing our implementation gives the following:

text
1// (1)2addToBasket("👕");3addToBasket("👕");4
5// Output:6shop_items: [7  { value: "👕", stock: 8},8  { value: "👖", stock: 10 },9  { value: "👞", stock: 10}10]11
12shopping_basket: [ { value: "👕", count: 2 } ]13
14// (2)15addToBasket("👞");16
17// Output:18shop_items: [19  { value: "👕", stock: 8},20  { value: "👖", stock: 10 },21  { value: "👞", stock: }22]23
24shopping_basket: [25  { value: "👕", count: 2},26  { value: "👞", count: 1}27]28
29// ------------------------------------ //30
31// (3)32removeFromBasket("👕");33
34// Output:35shop_items: [36  { value: "👕", stock: 9},37  { value: "👖", stock: 10 },38  { value: "👞", stock: 9}39]40
41shopping_basket: [42  { value: "👕", count: 1},43  { value: "👞", count: 1}44]45
46// ------------------------------------ //47
48// (4)49removeFromBasket("👞");50
51// Output:52shop_items: [53  { value: "👕", stock: 9},54  { value: "👖", stock: 10 },55  { value: "👞", stock: 10}56]57
58// initial empty shopping_basket59shopping_basket: [ { value: "👕", count: 1} ]

So, our implementation works ?! What’s the problem then? 🤔

If we give a closer look at both our update functions, we will notice that we are using findIndex when searching for an item in the basket. This results in a linear time complexity of O(N). In other words, in the worst case, we will iterate through the entire shop items list and shopping basket twice in the same function.

In the current context, where both sizes are very small and the use of both functions is pretty simple, this doesn’t really cause any performance issue. However, this does not always scale. The complexity can easily grow to O(n²) if we ever nest our functions in another loop.

Here’s why Map can solve our issues:

  • The complexity for adding/retrieving/removing items is constant O(1).
  • It has more readable and suited functions for adding/retrieving/removing items.

Initially, we have the following:

javascript
1// initial shop_items2
3let shop_items = [4  { value: "👕", stock: 10 },5  { value: "👖", stock: 10 },6  { value: "👞", stock: 10 },7];8
9// initial empty shopping_basket10
11let shopping_basket = new Map();

Let’s then refactor the addToBasket function:

javascript
1function addToBasket(value) {2  // decrement the stock of the corresponding shop item3  const shop_item_idx = shop_items.findIndex((item) => item.value === value);4  shop_items[shop_item_idx].stock--;5
6  // update basket7  // (1) if the item was never added to the basket,8  // it should be added to the basket with a count of 19  // (2) othwerwise, its count should be incremented10  const existingItem = shopping_basket.get(value);11  const count = !existingItem ? 1 : existingItem.count + 1;12  shopping_basket.set(value, { value, count });13}

Let’s also refactor theremoveFromBasket function:

javascript
1function removeFromBasket(value) {2  // increment the stock of the corresponding shop item3  const shop_item_idx = shop_items.findIndex((item) => item.value === value);4  shop_items[shop_item_idx].stock++;5
6  // update basket7  const existingItem = shopping_basket.get(value);8  // (1) if the item has a count bigger than 1 in the basket,9  // its count should be decrement10  // (2) othwerwise, it should be removed from the basket11  if (existingItem.count > 1) {12    shopping_basket.set(value, { value, count: existingItem.count - 1 });13  } else {14    shopping_basket.delete(value);15  }16}17

If we run the test again, we should see the same results.

Why not just use Objects?

One might think that the previous performance can also be achieved if we use objects instead of maps.

The implementation of addToBasket would look as follows:

javascript
1function addToBasket(value) {2  // decrement the stock of the corresponding shop item3  const shop_item_idx = shop_items.findIndex((item) => item.value === value);4  shop_items[shop_item_idx].stock--;5
6  // update basket7  // (1) if the item was never added to the basket,8  // it should be added to the basket with a count of 19  // (2) othwerwise, its count should be incremented10  const existingItem = shopping_basket[value];11  const count = !existingItem ? 1 : existingItem.count + 1;12  shopping_basket[value] = { value, count };13}

The implementation of removeFromBasket would look as follows:

javascript
1function removeFromBasket(value) {2  // increment the stock of the corresponding shop item3  const shop_item_idx = shop_items.findIndex((item) => item.value === value);4  shop_items[shop_item_idx].stock++;5
6  // update basket7  const existingItem = shopping_basket[value];8  // (1) if the item has a count bigger than 1 in the basket,9  // its count should be decrement10  // (2) othwerwise, it should be removed from the basket11  if (existingItem.count > 1) {12    shopping_basket[value] = { value, count: existingItem.count - 1 };13  } else {14    delete shopping_basket[value];15  }16}17

Although this implementation works as well, it has the following problems:

  • According to MDN, objects keys are not necessarily ordered.
  • The delete operation does not have a constant complexity O(1)!

Recommended reads

How to build a waitlist with Supabase and Next.js

How to build a waitlist with Supabase and Next.js

Mohammed Elhadi Baci

Guide to fast websites with Next.js

Insights into how Tinloof measures website speed with best practices to make faster websites.

Seif Ghezala