Memoization with Map

Remember expensive results

Lesson 3 of 20 · 10 min · Module 1: Functions, deeper

Some functions take a long time but always return the same result for the same input. Remembering past results, called memoization, can make them almost instant the second time.

Start this lesson →

Free. No installation: you write and run the code in your browser, and it is checked automatically.

By the end, you’ll be able to…

Store results in a Map
Build a cache key from arguments
Know when memoization is safe

The idea

A Map stores key–value pairs and accepts any value as a key. For functions with several arguments, a simple key is JSON.stringify(args). Check the cache with map.has(key) before calculating.

const cache = new Map();
cache.set("a", 1);
console.log(cache.has("a"), cache.get("a"), cache.size);

01Map versus plain objects

A Map keeps keys of any type, has a size property, and never confuses your keys with inherited properties such as toString. It is the right tool for caches and lookups.

02Keys from arguments

JSON.stringify([1, "1"]) gives "[1,\"1\"]", so the number 1 and the string "1" get different keys. That keeps results for different inputs apart.

console.log(JSON.stringify([1]), JSON.stringify(["1"]));

Output

[1] ["1"]

03Only for pure functions

Memoize functions whose result depends only on their arguments. Caching a function that reads the current time or random numbers would freeze its first answer forever.

Your turn

Write memoize(fn). The returned function caches results by its arguments (use JSON.stringify(args) as the key), calls fn at most once per distinct argument list, and exposes the cache as a cache property that is a Map.

What the checks look for

Returns the right results
Calls the original once per argument list
Exposes the cache as a Map
Caches falsy results too

Try it in the editor →

Take this with you

Memoization trades memory for speed on pure functions.

Go a little further

Add a limit: when the cache has more than 100 entries, delete the oldest one (Maps remember insertion order).