JavaScript’s Maps For Better Performance

Seif Ghezala's photo
Seif Ghezala
Updated 2023-11-13 · 5 min
#tutorial#javascript#performance
Table of contents
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:

// initial shop_items
shop_items: [
    { value: "👕", stock: 10 },
    { value: "👖", stock: 10 },
    { value: "👞", stock: 10}
]


// initial empty shopping_basket
shopping_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:

// initial shop_items
let shop_items = [
  { value: "👕", stock: 10 },
  { value: "👖", stock: 10 },
  { value: "👞", stock: 10 },
];


// initial empty shopping_basket
let shopping_basket = [];

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

/**
 * Adds an item from the shop items to the shopping basket
 * @param {string} value: value of the item to add
 */
function addToBasket(value) {
  // decrement the stock of the corresponding shop item
  const shop_item_idx = shop_items.findIndex((item) => item.value === value);
  shop_items[shop_item_idx].stock--;


  // update basket
  const existingIndex = shopping_basket.findIndex(
    (item) => item.value === value
  );
  // (1) if the item was never added to the basket, it should be added to
  // the basket with a count of 1
  // (2) othwerwise, its count should be incremented
  if (existingIndex === -1) {
    shopping_basket.push({ value, count: 1 });
  } else {
    shopping_basket[existingIndex].count++;
  }
}

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

/**
 * Puts back an item from the shopping basket to the shop items
 * @param {string} value: value of the item to add
 */
function removeFromBasket(value) {
  // increment the stock of the corresponding shop item
  const shop_item_idx = shop_items.findIndex((item) => item.value === value);
  shop_items[shop_item_idx].stock++;


  // update basket
  const existingIndex = shopping_basket.findIndex(
    (item) => item.value === value
  );
  // (1) if the item has a count bigger than 1 in the basket,
  // its count should be decrement
  // (2) othwerwise, it should be removed from the basket
  if (shopping_basket[existingIndex].count > 1) {
    shopping_basket[existingIndex].count--;
  } else {
    shopping_basket[existingIndex].splice(existingIndex);
  }
}

Testing our implementation gives the following:

// (1)
addToBasket("👕");
addToBasket("👕");


// Output:
shop_items: [
  { value: "👕", stock: 8},
  { value: "👖", stock: 10 },
  { value: "👞", stock: 10}
]


shopping_basket: [ { value: "👕", count: 2 } ]


// (2)
addToBasket("👞");


// Output:
shop_items: [
  { value: "👕", stock: 8},
  { value: "👖", stock: 10 },
  { value: "👞", stock: }
]


shopping_basket: [
  { value: "👕", count: 2},
  { value: "👞", count: 1}
]


// ------------------------------------ //


// (3)
removeFromBasket("👕");


// Output:
shop_items: [
  { value: "👕", stock: 9},
  { value: "👖", stock: 10 },
  { value: "👞", stock: 9}
]


shopping_basket: [
  { value: "👕", count: 1},
  { value: "👞", count: 1}
]


// ------------------------------------ //


// (4)
removeFromBasket("👞");


// Output:
shop_items: [
  { value: "👕", stock: 9},
  { value: "👖", stock: 10 },
  { value: "👞", stock: 10}
]


// initial empty shopping_basket
shopping_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:

// initial shop_items


let shop_items = [
  { value: "👕", stock: 10 },
  { value: "👖", stock: 10 },
  { value: "👞", stock: 10 },
];


// initial empty shopping_basket


let shopping_basket = new Map();

Let’s then refactor the addToBasket function:

function addToBasket(value) {
  // decrement the stock of the corresponding shop item
  const shop_item_idx = shop_items.findIndex((item) => item.value === value);
  shop_items[shop_item_idx].stock--;


  // update basket
  // (1) if the item was never added to the basket,
  // it should be added to the basket with a count of 1
  // (2) othwerwise, its count should be incremented
  const existingItem = shopping_basket.get(value);
  const count = !existingItem ? 1 : existingItem.count + 1;
  shopping_basket.set(value, { value, count });
}

Let’s also refactor theremoveFromBasket function:

function removeFromBasket(value) {
  // increment the stock of the corresponding shop item
  const shop_item_idx = shop_items.findIndex((item) => item.value === value);
  shop_items[shop_item_idx].stock++;


  // update basket
  const existingItem = shopping_basket.get(value);
  // (1) if the item has a count bigger than 1 in the basket,
  // its count should be decrement
  // (2) othwerwise, it should be removed from the basket
  if (existingItem.count > 1) {
    shopping_basket.set(value, { value, count: existingItem.count - 1 });
  } else {
    shopping_basket.delete(value);
  }
}

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:

function addToBasket(value) {
  // decrement the stock of the corresponding shop item
  const shop_item_idx = shop_items.findIndex((item) => item.value === value);
  shop_items[shop_item_idx].stock--;


  // update basket
  // (1) if the item was never added to the basket,
  // it should be added to the basket with a count of 1
  // (2) othwerwise, its count should be incremented
  const existingItem = shopping_basket[value];
  const count = !existingItem ? 1 : existingItem.count + 1;
  shopping_basket[value] = { value, count };
}

The implementation of removeFromBasket would look as follows:

function removeFromBasket(value) {
  // increment the stock of the corresponding shop item
  const shop_item_idx = shop_items.findIndex((item) => item.value === value);
  shop_items[shop_item_idx].stock++;


  // update basket
  const existingItem = shopping_basket[value];
  // (1) if the item has a count bigger than 1 in the basket,
  // its count should be decrement
  // (2) othwerwise, it should be removed from the basket
  if (existingItem.count > 1) {
    shopping_basket[value] = { value, count: existingItem.count - 1 };
  } else {
    delete shopping_basket[value];
  }
}

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)!

Recent articles

Guide to fast Next.js

Insights into how Tinloof measures website speed with best practices to make faster websites.
Seif Ghezala's photo
Seif Ghezala
2024-01-15 · 13 min

Contact

hi@tinloof.com