javascript 42 lines · 8 steps

Building an LRU cache with a JS Map

A least-recently-used cache that exploits Map's insertion-order guarantee to track and evict the stalest entry.

Explained by highlit
Intermediate lru-cache data-structures insertion-order eviction iterators
1class LRUCache {
2 constructor(capacity) {
3 if (capacity < 1) throw new RangeError('capacity must be positive');
4 this.capacity = capacity;
5 this.map = new Map();
6 }
7 
8 get(key) {
9 if (!this.map.has(key)) return undefined;
10 const value = this.map.get(key);
11 this.map.delete(key);
12 this.map.set(key, value);
13 return value;
14 }
15 
16 set(key, value) {
17 if (this.map.has(key)) {
18 this.map.delete(key);
19 } else if (this.map.size >= this.capacity) {
20 const oldest = this.map.keys().next().value;
21 this.map.delete(oldest);
22 }
23 this.map.set(key, value);
24 return this;
25 }
26 
27 has(key) {
28 return this.map.has(key);
29 }
30 
31 delete(key) {
32 return this.map.delete(key);
33 }
34 
35 get size() {
36 return this.map.size;
37 }
38 
39 *[Symbol.iterator]() {
40 for (const entry of this.map) yield entry;
41 }
42}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A JavaScript Map preserves insertion order, so re-inserting a key makes it the newest and iterating gives oldest-first for free.
  2. 2Delete-then-set is the trick that promotes a touched key to most-recently-used without a linked list.
  3. 3Implementing Symbol.iterator lets your class work with for...of and the spread operator like a built-in collection.

Related explainers

javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
rust 
use std::f64::consts::PI;
 
#[derive(Debug, Clone, Copy)]
pub struct LatLng {

Building geographic bounding boxes in Rust

geospatial value-types option
Intermediate 7 steps
javascript 
import { useState, useEffect, useCallback, useRef } from 'react';
 
const cache = new Map();
const inflight = new Map();

Building a stale-while-revalidate hook in React

caching request-deduplication custom-hooks
Advanced 10 steps
rust 
use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing
Intermediate 7 steps
javascript 
import { useEffect, useRef, useState } from 'react';
 
export function useDelayedFlag(active, delay = 300) {
  const [visible, setVisible] = useState(false);

Delaying a loading spinner with a React hook

custom-hooks debouncing cleanup
Intermediate 8 steps
javascript 
const SWIPE_THRESHOLD = 80;
const MAX_TRANSLATE = 120;
 
export function attachSwipeToDismiss(element, onDismiss) {

Building a swipe-to-dismiss gesture in JS

touch-events gesture-detection dom-manipulation
Intermediate 10 steps

Share this explainer

Here's the card — post it anywhere.

Building an LRU cache with a JS Map — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code