A concrete example showcasing the performance of JavaScript Maps.
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:
Let’s also add a removeFromBasket function to remove put back an item from the shopping basket to the shop items list:
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:
Let’s also refactor theremoveFromBasket function:
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:
The implementation of removeFromBasket would look as follows:
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)!
To wrap it up 🙌
I hope you find this article useful enough to understand the performance benefits of JavaScript Maps. Hopefully, this will motivate you to use them in similar use cases.
I will also love to hear your feedback or questions if you have any.
P.S: you can find me over on twitter @seif_ghezala :)