What data structure is best for caching? An experiment 🧪
Tags: javascript, caching, experiment, discuss
Published: 2022-07-24 14:12:51

While trying to broaden my horizons about data structures, I learned about two native JavaScript structures I had never heard of - Sets and Maps.

Now why had I never heard of them? Is it because I am a complete noob? Or maybe they are just not so common? (my nice way of saying useless).

To figure it out I decided to run a small experiment to test the build and retrieval times for each of the big 4 - Arrays, Objects, Sets, and Maps. 

**Here's what I did:**

1. First I tested **Arrays**- constructing it with a for loop and retrieving using the indexOf method (for a worst case scenario item).

```
const myArray = []

function storeWithArray(array, itemToFind) {
    const startTime = Date.now()

    for (let i = 0; i < 10000000; i++) {
        array.push(i)
    }

    const buildTime = Date.now()
    console.log("Array Build Time: ", buildTime - startTime)

    console.log(array.indexOf(itemToFind) === itemToFind)

    const retrievalTime = Date.now()
    console.log("Array Retrieval Time: ", retrievalTime - buildTime)
}

```

Then I used the array I built to test the other three structures:

**Sets**

```
function storeWithSet(array, itemToFind) {
    const startTime = Date.now()

    const mySet = new Set();

    array.forEach((item) => {
        mySet.add(item)
    })

    const buildTime = Date.now()
    console.log("Set Build Time: ", buildTime - startTime)

    console.log(mySet.has(itemToFind))

    const retrievalTime = Date.now()
    console.log("Set Retrieval Time: ", retrievalTime - buildTime)
}
```

**Objects**

```
function storeWithObject(array, itemToFind) {
    const startTime = Date.now()

    const myObject = new Object();

    array.forEach((item) => {
        myObject[item] = item;
    })
    const buildTime = Date.now()
    console.log("Object Build Time: ", buildTime - startTime)

    console.log(myObject[itemToFind] === itemToFind)

    const retrievalTime = Date.now()
    console.log("Object Retrieval Time: ", retrievalTime - buildTime)
}
```

**Maps**

```
function storeWithMap(array, itemToFind) {
    const startTime = Date.now()

    const myMap = new Map();

    array.forEach((item) => {
        myMap.set(item, item)
    })
    const buildTime = Date.now()
    console.log("Map Build Time: ", buildTime - startTime)

    console.log(myMap.get(itemToFind) === itemToFind)

    const retrievalTime = Date.now()
    console.log("Map Retrieval Time: ", retrievalTime - buildTime)
}
```

And run time:

```
storeWithArray(myArray, 9999999)
storeWithSet(myArray, 9999999)
storeWithObject(myArray, 9999999)
storeWithMap(myArray, 9999999)
```

Here are the results:
![results of experiment ](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w1otudh4tckgpg05ern2.png)

Unsurprisingly Array retrieval time was the longest, _but_ the build time was much shorter than Sets and Maps!

Objects seem to be the clear winner with the shortest build time and marginally longer retrieval time than Maps and Sets (sometimes it even beat them).

So basically if you need to store and retrieve information - objects are your best bet.

Then what are Maps and Sets good for?
I know they poses unique qualities - they are ordered like Arrays and can prevent duplicate values etc. But what is the use case that warrants their apparent inefficiency?