DEV Community

Cover image for What data structure is best for caching? An experiment 🧪
eitanwaxman
eitanwaxman

Posted on

What data structure is best for caching? An experiment 🧪

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

Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

And run time:

storeWithArray(myArray, 9999999)
storeWithSet(myArray, 9999999)
storeWithObject(myArray, 9999999)
storeWithMap(myArray, 9999999)
Enter fullscreen mode Exit fullscreen mode

Here are the results:
results of experiment

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?

Top comments (0)